PuLP：如何编写多变量约束？

Question

我正在尝试解决 Python 中的 this optimization problem。我使用 PuLP 编写了以下代码：

import pulp
D = range(0, 10)
F = range(0, 10)
x = pulp.LpVariable.dicts("x", (D), 0, 1, pulp.LpInteger)
y = pulp.LpVariable.dicts("y", (F, D), 0, 1, pulp.LpInteger)
model = pulp.LpProblem("Scheduling", pulp.LpMaximize)
model += pulp.lpSum(x[d] for d in D)
for f in F:
    model += pulp.lpSum(y[f][d] for d in D) == 1
for d in D:
    model += x[d]*pulp.lpSum(y[f][d] for f in F) == 0
model.solve()

此处的最后一行 returns：TypeError: Non-constant expressions cannot be multiplied。我知道它正在返回它，因为它无法解决非线性优化问题。是否可以将此问题表述为适当的线性问题，以便可以使用 PuLP 求解？

Answer 1

从数学模型入手总是一个好主意。你有：

  min sum(d, x[d])
  sum(d,y[f,d]) = 1   ∀f
  x[d]*sum(f,y[f,d]) = 0 ∀d
  x[d],y[f,d] ∈ {0,1}

最后一个约束是非线性的（它是二次的）。这不能由 PuLP 处理。约束可以解释为：

  x[d] = 0 or sum(f,y[f,d]) = 0 ∀d

或

  x[d] = 1 ==> sum(f,y[f,d]) = 0 ∀d

这可以线性化为：

  sum(f,y[f,d]) <= (1-x[d])*M

其中 M = |F|（F 中的元素数，即 |F|=10）。您可以检查：

 x[d]=0 => sum(f,y[f,d]) <= M (i.e. non-binding)
 x[d]=1 => sum(f,y[f,d]) <= 0 (i.e. zero)

所以你需要用这个线性约束替换你的二次约束。

请注意，这不是唯一的表述。您还可以线性化各个项 z[f,d]=x[d]*y[f,d]。我会把它留作练习。

PuLP：如何编写多变量约束？

PuLP: How to write a multi variable constraint?

python

math

linear-programming

pulp