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

Question

I'm looking for a solution to a linear programming problem and I need to define the following constraints:

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

I wrote the first two costrains (using the Pulp library), but I don't know how to represent the multiplication of gji*gki

My code:

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

How can I write the costrain for Pjki?

Erwin Kalvelagen Erwin Kalvelagen · Accepted Answer · 2019-04-24T03:18:18

Always first formulate a proper mathematical model, before implementing it in PuLp.

Let

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

and

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

First you need some assignment constraints:

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

The binary multiplication

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

can be linearized as

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}

Usually we don't need all of these variables and equations, but that depends on the details of the model. For sure we should only consider i<j. Interestingly, this formulation is so tight, we can relax p(i,j,k) to be continuous between 0 and 1: they will be integer automatically.

This mathematical description is easily transcribed into Python/Pulp. You probably should redo your Python code as it has some nonsensical things. Some hints:

binary variables already have bounds 0 and 1
Pulp can do equality constraints (writing <= and >= constraints is silly)
try to make things more readable (closer to the mathematical representation)
for a different approach see wedding.py

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

1 Answers