milp#
- scipy.optimize.milp(c, *, integrality=None, bounds=None, constraints=None, options=None)[source]#
混合整数线性规划
解决以下形式的问题
\[\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
默认情况下,除非通过
bounds
指定,否则l = 0
且u = np.inf
。- 参数:
- c一维密集数组类型
要最小化的线性目标函数的系数。c 在问题求解之前会被转换为双精度数组。
- integrality一维密集数组类型,可选
指示每个决策变量的整数性约束类型。
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
参数被忽略。- options字典,可选
求解器选项的字典。识别以下键。
- disp布尔值(默认:
False
) 如果要在优化期间将优化状态指示器打印到控制台,则设置为
True
。- node_limit整数,可选
停止前要解决的最大节点数(线性规划松弛)。默认没有最大节点数。
- presolve布尔值(默认:
True
) 预处理尝试在将问题发送到主求解器之前识别平凡不可行性、平凡无界性并简化问题。
- time_limit浮点数,可选
解决问题所允许的最大秒数。默认没有时间限制。
- mip_rel_gap浮点数,可选
MIP 求解器的终止准则:当原始目标值与对偶目标界限之间的差距(按原始目标值缩放)小于或等于 mip_rel_gap 时,求解器将终止。
- disp布尔值(默认:
- 返回:
- resOptimizeResult
scipy.optimize.OptimizeResult
的一个实例。该对象保证具有以下属性。- status整数
表示算法退出状态的整数。
0
: 找到最优解。1
: 达到迭代或时间限制。2
: 问题不可行。3
: 问题无界。4
: 其他;详情请参见消息。- success布尔值
当找到最优解时为
True
,否则为False
。- message字符串
算法退出状态的字符串描述。
以下属性也将存在,但其值可能为
None
,具体取决于解决方案状态。- xndarray
在满足约束条件下,使目标函数最小化的决策变量的值。
- fun浮点数
目标函数
c @ x
的最优值。- mip_node_count整数
MILP 求解器解决的子问题或“节点”数量。
- mip_dual_bound浮点数
MILP 求解器对最优解下界的最终估计。
- mip_gap浮点数
原始目标值与对偶目标界限之间的差值,按原始目标值缩放。
备注
milp
是 HiGHS 线性优化软件 [1] 的一个包装器。该算法是确定性的,并且通常能找到中等难度的混合整数线性规划问题的全局最优解(如果存在)。参考文献
[1]Huangfu, Q., Galabova, I., Feldmeier, M., and Hall, J. A. J. “HiGHS - high performance software for linear optimization.” https://highs.dev/
[2]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
示例
考虑 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]
我们将无法通过四舍五入到最近的整数来获得正确的解决方案。
其他示例请参见教程。