线性规划中布尔值之间的乘法（python，Pulp 库）

Question

我正在寻找线性规划问题的解决方案，我需要定义以下约束条件：

gji = 1 if guest j is seated at table i, 0 otherwise 
gki = 1 if guest k is seated at table i, 0 otherwise  
pjik = gij * gik = 1 if guest j AND guest k are seated at table i, 0 otherwise

我写了前两个costrains（使用Pulp库），但我不知道如何表示gji*gki

的乘法

我的代码：

Gji = LpVariable.matrix("Gji",(range(0,number_guest),range(0,number_table)),lowBound=0, upBound=1, cat='binary')

Gki = LpVariable.matrix("Gki",(range(0,number_guest),range(0,number_table)),lowBound=0, upBound=1, cat='binary')

for row in range (0,number_guest):
    prob += lpSum(Gji[row])<=1
    prob += lpSum(Gji[row])>=1

for columns in range (0,number_table):
    prob += lpSum(np.matrix(Gji).T[columns].tolist()) <= a

如何为 Pjki 编写协程？

Answer 1

总是先制定一个合适的数学模型，然后再在 PuLp 中实现它。

让

g(i,k) = 1 if guest i sits at table k
         0 otherwise

和

p(i,j,k) = 1 if guests i and j sit at table k
           0 otherwise

首先你需要一些赋值约束：

sum(i, g(i,k)) <= capacity(k)  for all k
sum(k, g(i,k)) = 1             for all i

二进制乘法

p(i,j,k) = g(i,k) * g(j,k)

可以线性化为

p(i,j,k) <= g(i,k)
p(i,j,k) <= g(j,k)
p(i,j,k) >= g(i,k)+g(j,k)-1
p(i,j,k) ∈ {0,1}

通常我们不需要所有这些变量和方程，但这取决于模型的细节。当然，我们应该只考虑 i<j。有趣的是，这个公式非常紧凑，我们可以放松 p(i,j,k) 在 0 和 1 之间连续：它们将自动为整数。

这个数学描述很容易被转录成 Python/Pulp。你可能应该重做你的 Python 代码，因为它有一些荒谬的东西。一些提示：

二进制变量已经有边界 0 和 1
Pulp 可以做等式约束（写 <= 和 >= 约束是愚蠢的）
尝试使事情更具可读性（更接近数学表示）
有关不同的方法，请参阅 wedding.py

线性规划中布尔值之间的乘法（python，Pulp 库）

Multiplication between booleans in linear programming (python, Pulp library)

python

optimization

linear-programming

pulp