linprog(method=’highs-ipm’)#

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-D array: 要最小化的線性目標函數的係數。
A_ub2-D array, optional: 不等式約束矩陣。 A_ub 的每一列指定 x 上的線性不等式約束的係數。
b_ub1-D array, optional: 不等式約束向量。每個元素表示 A_ub @ x 相應值的上限。
A_eq2-D array, optional: 等式約束矩陣。 A_eq 的每一列指定 x 上的線性等式約束的係數。
b_eq1-D array, optional: 等式約束向量。 A_eq @ x 的每個元素必須等於 b_eq 的相應元素。
boundssequence, optional: 每個 x 元素的一系列 (min, max) 對，定義該決策變數的最小值和最大值。使用 None 表示沒有邊界。預設情況下，邊界為 (0, None) （所有決策變數均為非負數）。如果提供單個元組 (min, max)，則 min 和 max 將作為所有決策變數的邊界。
methodstr: 這是 ‘highs-ipm’ 的方法特定文件。 ‘highs-ipm’、 ‘highs-ds’、 ‘interior-point’ (預設)、 ‘revised simplex’ 和 ‘simplex’ (傳統) 也可用。

返回:

resOptimizeResult

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

x1D array

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

funfloat

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

slack1D array

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

con1D array

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

successbool

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

statusint

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

0 : 最佳化成功終止。

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

2 : 問題似乎不可行。

3 : 問題似乎無界。

4 : HiGHS 求解器遇到問題。

messagestr

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

nitint

執行的總迭代次數。對於 HiGHS 內點法，這不包括交叉迭代。

crossover_nitint

HiGHS 內點法交叉常式期間執行的原始/對偶推進次數。

ineqlinOptimizeResult

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

residualnp.ndnarray: 鬆弛變數的（名義上為正值）值，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 (lower) 或 ub - x (upper) 的（名義上為正值）值。
marginalsnp.ndarray: 目標函數對於下限和上限 bounds 的靈敏度（偏導數）。

另請參閱

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

選項:

——-
maxiterint: 在任一階段執行的最大迭代次數。對於 ‘highs-ipm’，這不包括交叉迭代的次數。預設值是平台上 int 的最大可能值。
dispbool (預設值: False): 如果要在最佳化期間將最佳化狀態的指標列印到控制台，請設定為 True。
presolvebool (預設值: True): Presolve 嘗試識別微不足道的可行性問題、識別微不足道的無界性，並在將問題發送到主求解器之前簡化問題。通常建議保留預設設定 True；如果要停用 presolve，請設定為 False。
time_limitfloat: 分配用於解決問題的最長時間（秒）；預設值是平台上 double 的最大可能值。
dual_feasibility_tolerancedouble (預設值: 1e-07): 此值和 primal_feasibility_tolerance 的最小值用於 ‘highs-ipm’ 的可行性容差。
primal_feasibility_tolerancedouble (預設值: 1e-07): 此值和 dual_feasibility_tolerance 的最小值用於 ‘highs-ipm’ 的可行性容差。
ipm_optimality_tolerancedouble (預設值: 1e-08): ‘highs-ipm’ 的最佳性容差。最小允許值為 1e-12。
unknown_optionsdict: 此特定求解器未使用的可選參數。如果 unknown_options 為非空，則會發出警告，列出所有未使用的選項。

註解

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

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

參考文獻

[13] (1,2)

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

[14]

Huangfu, Q. 和 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