scipy.optimize.

混合整数线性规划

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\) 是必须为整数的决策变量的索引集合。（在这种情况下，只能取整数值的变量被称为“整数”；它有一个“整数性”约束。）

或者，那是：

minimize:

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 在问题求解之前被转换为双精度数组。

完整性1D 密集数组类，可选

指示每个决策变量的完整性约束类型。

0 : 连续变量；无整数约束。

1 : 整数变量；决策变量必须是 bounds 范围内的整数。

2 : 半连续变量；决策变量必须在 bounds 范围内或取值 0。

3 : 半整数变量；决策变量必须是 bounds 范围内的整数或取值为 0。

默认情况下，所有变量都是连续的。integrality 在问题求解之前被转换为一个整数数组。

边界scipy.optimize.Bounds, 可选

决策变量的边界。下限和上限在问题求解之前被转换为双精度数组。Bounds 对象的 keep_feasible 参数被忽略。如果未指定，所有决策变量都被约束为非负。

约束scipy.optimize.LinearConstraint 的序列，可选

优化问题的线性约束。参数可以是以下之一：

1. 一个单独的 LinearConstraint 对象

2. 一个可以转换为 LinearConstraint 对象的元组，如 LinearConstraint(*constraints)

3. 完全由类型 1. 和 2. 的对象组成的序列。

在问题解决之前，所有值都被转换为双精度，约束系数的矩阵被转换为 scipy.sparse.csc_array 的实例。LinearConstraint 对象的 keep_feasible 参数被忽略。

选项dict, 可选

求解器选项的字典。以下键被识别。

disp : bool (默认: False)bool (默认:)

如果在优化过程中需要将优化状态的指示符打印到控制台，请设置为 True。

node_limitint, 可选

在停止之前要解决的最大节点数（线性规划松弛）。默认是没有最大节点数。

presolve : bool (默认: True)bool (默认:)

预处理尝试识别明显的不可行性、识别明显的无界性，并在将问题发送给主求解器之前简化问题。

时间限制float, 可选

解决问题的最大秒数。默认是没有时间限制。

mip_rel_gapfloat, 可选

MIP 求解器的终止准则：当原始目标值与对偶目标边界之间的差距，按原始目标值缩放后，小于等于 mip_rel_gap 时，求解器将终止。

返回:

res优化结果

一个 scipy.optimize.OptimizeResult 的实例。该对象保证具有以下属性。

状态整数

表示算法退出状态的整数。

0 : 找到最优解。

1 : 达到迭代或时间限制。

2 : 问题不可行。

3 : 问题是无界的。

4 : 其他；详见消息内容。

成功布尔

True 表示找到最优解，False 表示未找到。

消息str

算法退出状态的字符串描述符。

以下属性也将存在，但值可能为 None，这取决于解决方案的状态。

xndarray

在满足约束条件的同时，使目标函数最小化的决策变量的值。

乐趣浮动

目标函数 c @ x 的最优值。

mip_node_count整数

MILP 求解器解决的子问题或“节点”的数量。

mip_dual_bound浮动

MILP 求解器对最优解下限的最终估计。

mip_gap浮动

原始目标值与对偶目标界之间的差异，按原始目标值进行缩放。

注释

milp 是 HiGHS 线性优化软件 [1] 的一个封装。该算法是确定性的，并且通常能找到中等难度混合整数线性规划的全局最优解（当其存在时）。

参考文献

[1]

Huangfu, Q., Galabova, I., Feldmeier, M., 和 Hall, J. A. J. “HiGHS - 高性能线性优化软件。” https://highs.dev/

[2]

Huangfu, Q. 和 Hall, J. A. J. “并行化对偶修正单纯形法。” 《数学规划计算》, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

示例

Try it in your browser!

考虑 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]

如果我们四舍五入到最接近的整数，我们将无法得到正确的解决方案。

其他示例在 教程 中给出。

Go BackOpen In Tab