PuLP: How to write a multi variable constraint?

Question

I am trying to solve this optimization problem in Python. I have written the following code using 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()

The one-but-last line here returns: TypeError: Non-constant expressions cannot be multiplied. I understand it is returning this since it cannot solve non-linear optimization problems. Is it possible to formulate this problem as a proper linear problem, such that it can be solved using PuLP?

Answer 1

It is always a good idea to start with a mathematical model. You have:

  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} 

The last constraint is non-linear (it is quadratic). This can not be handled by PuLP. The constraint can be interpreted as:

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

or

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

This can be linearized as:

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

where M = |F| (number of elements in F, i.e. |F|=10). You can check that:

 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)

So you need to replace your quadratic constraint with this linear one.

Note that this is not the only formulation. You could also linearize the individual terms z[f,d]=x[d]*y[f,d]. I'll leave that as an exercise.