Skip to content
Advertisement

Extreme low performance when using a high number of integer & binary variables in Pulp

when modelling a lp production problem, I use a high number of integer.

First the problem was being solved in a reasonable time but when I added a big number of binary values (y) due to big M method, it takes hours and hours and the program doesn’t appear to be working at all. This is because Pulp is quite slow with binary variables.

The reason I did big M is because I wanted to seperate the variable bounds, in order to get

x(i,t) = 0 or x(i,t) >= 10 (which means either produce nothing or at least 10 pieces of product i in every time period t):

x(i,t) – 1 <= e + M * y(i,t)

x(i,t) – 9 >= -e – (1 – y(i,t) ) * M

(e is a very small constant number and M a very big constant number)

Is there any other way than using the method shown above? I could define the bounds of x(i,t) like [10, inf] but I still need the value 0, since producing nothing is also a very valid important solution.

Thanks in advance!

Advertisement

Answer

I’m not sure why you are formulating like that with big M and the small constant for integer/binary variables.

If x is integer and y is corresponding binary variable, re-formulate to this:

x <= y * M
x >= y * 10

Where M is a logical upper bound on x

This is similar to what you had, but the small constant e is unnecessary and M should not be overly huge.

All solvers (including the one pre-packaged in pulp slow significantly with the introduction of large numbers of binary or integer variables, under most conditions.

Have you tried setting a mip-gap or such to convince yourself that it is working?

User contributions licensed under: CC BY-SA
10 People found this is helpful
Advertisement