CODEWITHSUNDEEP
pythonoptimizationintegerlinear-programmingpulp
hkbgner
hkbgner

Reputation: 331

Python Pulp Linear Programming Constraint

I am totally new to pulp, and am wondering that if I need to optimize the following:

x = pulp.LpVariable.dicts("Volume", range(0, 7), cat='Binary')

where whenever there is a 0, it needs to be at least 3 of them.

so the solution can be [0,0,0,0,0,0,1], [0,0,0,1,0,0,0], [1,1,1,0,0,0,1] but not [1,0,1,0,1,0,0].

I tried to add a constraint as follows:

prob += min([len(list(g)) for k, g in itertools.groupby(x.values()) if k == 0]) >= 3

but it didn't work.

How can I formulate that?

Upvotes: 2

Views: 743

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16782

No. PuLP is for linear programming, so all constraints need to be linear. So it is not allowed to use if statements and similar programming constructs.

The requirement to have at least three consecutive zeros can be expressed in different ways. One rather interesting way is to forbid patterns 101 and 1001. This can be stated as:

 x[i] - x[i+1] + x[i+2] <= 1             for i=0,1,2,....
 x[i] - x[i+1] - x[i+2] + x[i+3] <= 1    for i=0,1,2,....

These constraints very precisely exclude the patterns 101 and 1001 but allow any other bit pattern. In addition, they don't require any additional variables (some other approaches do).

As mentioned in the comments, what happens near the boundaries needs some attention. The precise implementation of this depends a bit on the details of the problem. Like is 01 or 001 allowed at the beginning and whether 10,100 is allowed at the end. So it is a bit difficult to show how this must be done (I would have to enumerate several possible scenarios).

In any case, this is easily expressed in Pulp.

Upvotes: 5

Related Questions