Scipy 最小化：如何将 x 限制为 0 和 1？

Question

我想使用 Scipy.optimize.minimize:

最小化具有多个参数和约束的函数

def f(x):
    return -1*(0.9*x[0] + 0.8*x[1] + 0.85*x[2])*(0.95*x[3] + 0.8*x[4] + 0.7*x[5])*(0.98*x[6] + 0.94*x[7])

x0 = [0, 0, 1, 0, 0, 1, 0, 1]

cons=({'type': 'eq',
   'fun': lambda x: x[0] + x[1] + x[2] - 1},
  {'type': 'eq',
   'fun': lambda x: x[3] + x[4] + x[5] - 1},
  {'type': 'eq',
   'fun': lambda x: x[6] + x[7] - 1},
  {'type': 'ineq',
   'fun': lambda x: -1*(3*x[0] + x[1] + 2*x[2] + 3*x[3] + 2*x[4] + x[5] + 3*x[6] + 2*x[7] - 6)})

如何告诉 python x[i] 只能是 0 和 1？

Answer 1

理论上你可以添加等式约束：

x[i] * (x[i]-1) = 0

在实践中效果不是很好，因为这给模型增加了讨厌的非凸性。看起来您有非线性 objective 和线性约束以及二进制变量，因此这表明我们需要查看 MINLP（混合整数非线性规划）求解器。这样的求解器很容易获得（例如 Bonmin, Couenne, Baron, Antigone）。

不过我们可以做点什么。我们可以扩展你的objective，写成

maximize 0.9*0.95*0.98*x[0]*x[3]*x[6] + 0.9*0.95*0.94*x[0]*x[3]*x[7] + ...

或

maximize c1*(x[0]*x[3]*x[6]) + c2*(x[0]*x[3]*x[7]) + ...

像x[0]*x[3]*x[6]这样的乘积，其中所有的x[i]都是0-1或者二进制变量可以线性化如下：

maximize c1*y1 + c2*y2 + ....
y1 <= x[0]
y1 <= x[3]
y1 <= x[6]
y2 <= x[0]
y2 <= x[3]
y2 <= x[7]
...
y1,y2,... binary variables

如果需要，我们可以在 0 和 1 之间创建 y1,y2,... 个连续变量。它们将自动为零或一。更多详情 here.

我们现在拥有的是线性 objective 以及线性约束和二进制变量 x[i], y[j]。这可以使用现成的 MIP（混合整数规划）求解器来解决。非常好的是 Cplex and Gurobi, but there are also public domain ones such as CBC and GLPK。他们中的许多人都有 Python 绑定。

Scipy 最小化：如何将 x 限制为 0 和 1？

Scipy minimize: how to restrict x only to 0 and 1?

python

optimization

mathematical-optimization

scipy