linprog(method=’highs’)#

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)

線性規劃：使用 HiGHS 求解器之一，最小化受線性等式和不等式約束的線性目標函數。

線性規劃解決以下形式的問題

\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

其中 \(x\) 是決策變數的向量； \(c\), \(b_{ub}\), \(b_{eq}\), \(l\), 和 \(u\) 是向量；並且 \(A_{ub}\) 和 \(A_{eq}\) 是矩陣。

或者，也就是說

最小化

c @ x

使得

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

請注意，除非使用 bounds 指定，否則預設 lb = 0 且 ub = None。

參數:

c1 維陣列

要最小化的線性目標函數的係數。

A_ub2 維陣列，選用

不等式約束矩陣。A_ub 的每一列指定 x 上線性不等式約束的係數。

b_ub1 維陣列，選用

不等式約束向量。每個元素代表 A_ub @ x 相應值的上限。

A_eq2 維陣列，選用

等式約束矩陣。A_eq 的每一列指定 x 上線性等式約束的係數。

b_eq1 維陣列，選用

等式約束向量。A_eq @ x 的每個元素必須等於 b_eq 的相應元素。

bounds序列，選用

一個 (min, max) 對的序列，對應 x 中的每個元素，定義該決策變數的最小值和最大值。使用 None 表示沒有邊界。預設情況下，邊界為 (0, None) (所有決策變數均為非負數)。如果提供單個元組 (min, max)，則 min 和 max 將作為所有決策變數的邊界。

method字串

這是 ‘highs’ 方法的特定文件，它會自動在 ‘highs-ds’ 和 ‘highs-ipm’ 之間選擇。‘interior-point’ (預設)、‘revised simplex’ 和 ‘simplex’ (舊版) 也可用。

integrality1 維陣列或整數，選用

指示每個決策變數的完整性約束類型。

0 : 連續變數；無完整性約束。

1 : 整數變數；決策變數必須是 bounds 範圍內的整數。

2 : 半連續變數；決策變數必須在 bounds 範圍內或取值 0。

3 : 半整數變數；決策變數必須是 bounds 範圍內的整數或取值 0。

預設情況下，所有變數都是連續的。

對於混合完整性約束，請提供形狀為 c.shape 的陣列。為了從較短的輸入推斷每個決策變數的約束，參數將使用 np.broadcast_to 廣播到 c.shape。

此參數目前僅由 'highs' 方法使用，否則將被忽略。

回傳值:

resOptimizeResult

一個 scipy.optimize.OptimizeResult，包含以下欄位

x1 維陣列

最小化目標函數並滿足約束的決策變數值。

fun浮點數

目標函數 c @ x 的最佳值。

slack1 維陣列

鬆弛變數的（名義上為正值）值，b_ub - A_ub @ x。

con1 維陣列

等式約束的（名義上為零）殘差，b_eq - A_eq @ x。

success布林值

當演算法成功找到最佳解時，為 True。

status整數

表示演算法退出狀態的整數。

0 : 最佳化成功終止。

1 : 達到迭代或時間限制。

2 : 問題似乎不可行。

3 : 問題似乎無界。

4 : HiGHS 求解器遇到問題。

message字串

演算法退出狀態的字串描述。

nit整數

執行的總迭代次數。對於 HiGHS 單純形法，這包括所有階段的迭代。對於 HiGHS 內點法，這不包括交叉迭代。

crossover_nit整數

在 HiGHS 內點法的交叉常式期間執行的原始/對偶推送次數。對於 HiGHS 單純形法，這為 0。

ineqlinOptimizeResult

對應於不等式約束 b_ub 的解和靈敏度資訊。一個包含以下欄位的字典

residualnp.ndarray: 鬆弛變數的（名義上為正值）值，b_ub - A_ub @ x。此數量通常也稱為“鬆弛變數”。
marginalsnp.ndarray: 目標函數相對於不等式約束 b_ub 右側的靈敏度（偏導數）。

eqlinOptimizeResult

對應於等式約束 b_eq 的解和靈敏度資訊。一個包含以下欄位的字典

residualnp.ndarray: 等式約束的（名義上為零）殘差，b_eq - A_eq @ x。
marginalsnp.ndarray: 目標函數相對於等式約束 b_eq 右側的靈敏度（偏導數）。

lower, upperOptimizeResult

對應於決策變數的下限和上限 bounds 的解和靈敏度資訊。

residualnp.ndarray: 數量 x - lb (下限) 或 ub - x (上限) 的（名義上為正值）值。
marginalsnp.ndarray: 目標函數相對於下限和上限 bounds 的靈敏度（偏導數）。

另請參閱

有關其餘參數的文件，請參閱 scipy.optimize.linprog

選項:

——-

maxiter整數

在任一階段要執行的最大迭代次數。對於 ‘highs-ipm’，這不包括交叉迭代的次數。預設值是平台上 int 的最大可能值。

disp布林值 (預設值: False)

如果要在最佳化期間將最佳化狀態的指示器列印到控制台，則設定為 True。

presolve布林值 (預設值: True)

預先求解嘗試識別微不足道的可行性問題、識別微不足道的無界性，並在將問題發送給主求解器之前簡化問題。通常建議保持預設設定 True；如果要停用預先求解，則設定為 False。

time_limit浮點數

分配用於解決問題的最長時間（秒）；預設值是平台上 double 的最大可能值。

dual_feasibility_tolerance雙精度浮點數 (預設值: 1e-07)

‘highs-ds’ 的對偶可行性容差。此值和 primal_feasibility_tolerance 的最小值用於 ‘highs-ipm’ 的可行性容差。

primal_feasibility_tolerance雙精度浮點數 (預設值: 1e-07)

‘highs-ds’ 的原始可行性容差。此值和 dual_feasibility_tolerance 的最小值用於 ‘highs-ipm’ 的可行性容差。

ipm_optimality_tolerance雙精度浮點數 (預設值: 1e-08)

‘highs-ipm’ 的最佳性容差。最小允許值為 1e-12。

simplex_dual_edge_weight_strategy字串 (預設值: None)

單純形對偶邊權重的策略。預設值 None 會自動選擇以下其中一項。

'dantzig' 使用 Dantzig 的原始策略，選擇最負的 reduced cost。

'devex' 使用 [15] 中描述的策略。

steepest 使用 [16] 中描述的精確 steepest edge 策略。

'steepest-devex' 從精確 steepest edge 策略開始，直到計算成本過高或不精確，然後切換到 devex 方法。

目前，None 始終選擇 'steepest-devex'，但隨著新選項的推出，這可能會改變。

mip_rel_gap雙精度浮點數 (預設值: None)

MIP 求解器的終止準則：當原始目標值與對偶目標邊界之間的差距（按原始目標值縮放）小於或等於 mip_rel_gap 時，求解器將終止。

unknown_options字典

此特定求解器未使用的選用參數。如果 unknown_options 為非空，則會發出警告，列出所有未使用的選項。

注意事項

方法 ‘highs-ds’ 是 C++ 高效能對偶修正單純形實作 (HSOL) 的封裝器 [13], [14]。方法 ‘highs-ipm’ 是 interior-point method 的 C++ 實作的封裝器 [13]；它具有交叉常式，因此它與單純形求解器一樣精確。方法 ‘highs’ 會自動在兩者之間選擇。對於涉及 linprog 的新程式碼，我們建議明確選擇這三種方法值之一，而不是 ‘interior-point’ (預設)、‘revised simplex’ 和 ‘simplex’ (舊版)。

結果欄位 ineqlin、eqlin、lower 和 upper 都包含 marginals，即目標函數相對於每個約束右側的偏導數。這些偏導數也稱為“拉格朗日乘數”、“對偶值”和“影子價格”。marginals 的符號慣例與許多非線性求解器產生的拉格朗日乘數相反。

參考文獻

[13] (1,2)

Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. “HiGHS - high performance software for linear optimization.” https://highs.dev/

[14]

Huangfu, Q. and Hall, J. A. J. “Parallelizing the dual revised simplex method.” Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

[15]

Harris, Paula MJ. “Pivot selection methods of the Devex LP code.” Mathematical programming 5.1 (1973): 1-28.

[16]

Goldfarb, Donald, and John Ker Reid. “A practicable steepest-edge simplex algorithm.” Mathematical Programming 12.1 (1977): 361-371.