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?