scipy.optimize.

milp#

scipy.optimize.milp(c, *, integrality=None, bounds=None, constraints=None, options=None)[原始碼]#

混合整數線性規劃

解決以下形式的問題

\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & b_l \leq A x \leq b_u,\\ & l \leq x \leq u, \\ & x_i \in \mathbb{Z}, i \in X_i\end{split}\]

其中 \(x\) 是決策變數的向量；\(c\)、\(b_l\)、\(b_u\)、\(l\) 和 \(u\) 是向量；\(A\) 是一個矩陣，而 \(X_i\) 是必須為整數的決策變數的索引集合。（在此上下文中，可以僅採用整數值的變數被稱為“整數”；它具有“整數性”約束。）

或者，那是

最小化

c @ x

使得

b_l <= A @ x <= b_u
l <= x <= u
Specified elements of x must be integers

預設情況下，l = 0 且 u = np.inf，除非使用 bounds 指定。

參數:

c1D 密集陣列型別

要最小化的線性目標函數的係數。c 在問題解決前會轉換為雙精度陣列。

integrality1D 密集陣列型別，選用

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

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

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

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

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

預設情況下，所有變數都是連續的。integrality 在問題解決前會轉換為整數陣列。

boundsscipy.optimize.Bounds，選用

決策變數的邊界。下限和上限在問題解決前會轉換為雙精度陣列。Bounds 物件的 keep_feasible 參數會被忽略。如果未指定，所有決策變數都會被約束為非負數。

constraintsscipy.optimize.LinearConstraint 的序列，選用

最佳化問題的線性約束。引數可以是下列其中之一

單個 LinearConstraint 物件
可以轉換為 LinearConstraint 物件的單個元組，如 LinearConstraint(*constraints)
完全由類型 1 和 2 的物件組成的序列。

在問題解決之前，所有值都會轉換為雙精度，並且約束係數矩陣會轉換為 scipy.sparse.csc_array 的實例。LinearConstraint 物件的 keep_feasible 參數會被忽略。

optionsdict，選用

求解器選項的字典。以下鍵被識別。

dispbool (預設值：False): 如果要在最佳化期間將最佳化狀態的指標列印到控制台，請設定為 True。
node_limitint，選用: 在停止之前要解決的最大節點數（線性規劃鬆弛）。預設值為無最大節點數。
presolvebool (預設值：True): Presolve 嘗試在將問題發送到主求解器之前，識別微不足道的可行性問題、識別微不足道的無界性並簡化問題。
time_limitfloat，選用: 分配用於解決問題的最大秒數。預設值為無時間限制。
mip_rel_gapfloat，選用: MIP 求解器的終止準則：當原始目標值和對偶目標邊界之間的差距（按原始目標值縮放）小於或等於 mip_rel_gap 時，求解器將終止。

返回:

resOptimizeResult

scipy.optimize.OptimizeResult 的實例。物件保證具有以下屬性。

statusint

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

0 : 找到最佳解。

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

2 : 問題不可行。

3 : 問題無界。

4 : 其他；請參閱訊息以瞭解詳細資訊。

successbool

當找到最佳解時為 True，否則為 False。

messagestr

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

以下屬性也將存在，但值可能為 None，具體取決於解決方案狀態。

xndarray: 在滿足約束條件的同時，最小化目標函數的決策變數的值。
funfloat: 目標函數 c @ x 的最佳值。
mip_node_countint: MILP 求解器解決的子問題或「節點」的數量。
mip_dual_boundfloat: MILP 求解器對最佳解的下限的最終估計。
mip_gapfloat: 原始目標值與對偶目標邊界之間的差異，按原始目標值縮放。

註解

milp 是 HiGHS 線性最佳化軟體 [1] 的包裝器。該演算法是確定性的，並且通常會找到適度具有挑戰性的混合整數線性規劃的全域最佳解（如果存在）。

參考文獻

[1]

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

[2]

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

範例

考慮 https://en.wikipedia.org/wiki/Integer_programming#Example 中的問題，該問題表示為兩個變數的最大化問題。由於 milp 要求問題表示為最小化問題，因此決策變數上的目標函數係數為

>>> import numpy as np
>>> c = -np.array([0, 1])

請注意負號：我們透過最小化目標函數的負數來最大化原始目標函數。

我們將約束的係數收集到如下陣列中

>>> A = np.array([[-1, 1], [3, 2], [2, 3]])
>>> b_u = np.array([1, 12, 12])
>>> b_l = np.full_like(b_u, -np.inf, dtype=float)

由於這些約束沒有下限，因此我們定義了一個充滿表示負無限大值的變數 b_l。對於 scipy.optimize.linprog 的使用者來說，這可能不熟悉，它僅接受 A_ub @ x <= b_u 形式的「小於」（或「上限」）不等式約束。透過接受約束 b_l <= A_ub @ x <= b_u 的 b_l 和 b_u，milp 可以輕鬆簡潔地指定「大於」不等式約束、「小於」不等式約束和等式約束。

這些陣列被收集到單個 LinearConstraint 物件中，如下所示

>>> from scipy.optimize import LinearConstraint
>>> constraints = LinearConstraint(A, b_l, b_u)

預設情況下，決策變數的非負性邊界是強制執行的，因此我們不需要為 bounds 提供引數。

最後，問題陳述兩個決策變數都必須是整數

>>> integrality = np.ones_like(c)

我們像這樣解決問題

>>> from scipy.optimize import milp
>>> res = milp(c=c, constraints=constraints, integrality=integrality)
>>> res.x
[2.0, 2.0]

請注意，如果我們解決了鬆弛問題（沒有整數性約束）

>>> res = milp(c=c, constraints=constraints)  # OR:
>>> # from scipy.optimize import linprog; res = linprog(c, A, b_u)
>>> res.x
[1.8, 2.8]

我們將無法透過四捨五入到最接近的整數來獲得正確的解。

其他範例在教學課程中給出。