Pulp add constraint that at least one LpAffineExpr

问题:

Say I have a PuLP model defined as thus: model = pulp.LpProblem('',pulp.LpMaximize)

And I have added an objective function (it does not matter)

Now I have a list of LpAffineExpression objects: lps = [l1, l2, l3, ...]

I want to add to the model the constraint that one of these LpAffineExpression evaluates to 1. How would I do so?

Essentially what I'm looking for is the syntactically correct way to do the following:

model += (l1 == 1 OR l2 == 1 OR l3 == 1 OR ...)

Note that I do not know how many how many LpAffineExpression objects are in the lps list, so I cannot hardcode it in.

In other words, I am looking for a way to group a set of LpAffineExpression in the model, such that only one has to be fulfilled.

回答1:

There is no "OR" in linear or integer programming. However, you can use binary variables to simulate such an OR construct. (Or SOS1 variables if big-M's are undesirable; I am not sure to what extend Pulp supports SOS1 variables).

The idea is:

1 - M * (1-δ(i)) <= L(i) <= 1 + M * (1-δ(i)) 
sum(i, δ(i)) >= 1 
δ(i) ∈ {0,1}

• Obviously the L(i) are your l1,l2,l3,...
• δ(i) is a binary variable indicating if L(i)=1. We have δ(i)=1 ⇒ L(i)=1.
• The constants M can be set to lower and upper bounds of L(i).