如何使用scipy.optimize.linprog获取整数解？

Question

当我解决线性规划问题时,如下面的公式,我希望x all的结果是int类型

请考虑以下问题:

最小化: f = -1*x[0] + 4*x[1]

受制于:

-3*x[0] + 1*x[1] <= 6    
1*x[0] + 2*x[1] <= 4    
x[1] >= -3

哪里: -inf <= x[0] <= inf

接下来是python编码器

>>> c = [-1, 4]
>>> A = [[-3, 1], [1, 2]]
>>> b = [6, 4]
>>> x0_bounds = (None, None)
>>> x1_bounds = (-3, None)
>>> res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds),
...               options={"disp": True})
>>> print(res)
Optimization terminated successfully.
Current function value: -11.428571
Iterations: 2
status: 0
success: True
fun: -11.428571428571429
x: array([-1.14285714,  2.57142857])
message: 'Optimization terminated successfully.'
nit: 2

Answer 1

来自文档:

method:str,可选的求解器类型.目前只支持'simplex'.

Simplex无法处理完整性约束,因此您无法使用scipy.optimize.linprog解决整数编程问题.您可以尝试其他库,如PuLP,Pyomo或CVXOPT.

Answer 2

Scipy 最近在 1.9.0 版本中添加了 scipy.optimize.milp。

它还向现有的 linprog 添加了积分=参数。所以你的代码可以更新如下

import scipy.optimize
import numpy as np

c = [-1, 4]
A = [[-3, 1.], [1, 2]]
b = [6, 4]
x0_bounds = (None, None)
x1_bounds = (-3.5, None)
res = scipy.optimize.linprog(
    c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds),
    integrality=[1, 1],
    options={"disp": True})

res.x

array([10., -3.])

其中integrality=[1, 1]指定变量x ₀和x ₁均为整数。

（我将界限从 -3 更改为 -3.5，这样整数和实数之间的解实际上有一个有趣的差异。）