Mixed integer programming
AnsweredHello everyone. I am solving a mixed integer programming model in Python with Gurobi package. Recently, I came across sth that is not logical to me. I have continuous and binary decision variables. Continuous ones can be defined integer instead, but I avoid this to relax the problem. I mean I prefer continuous ones to decrease the computational time. Theoretically, this is correct, too. There is no need to use integer variables as the optimal solution will be integer (because of discrete characteristic of parameters). However, this does not happen in Gurobi, and by this relaxation, the solving time will increase as well. There is also no guarantee to find the optimal solution in integer format.
Moreover, the solving process is dependent on big M as well, which is very confusing to be determined sometimes. Could you please help me to justify what is happening? I really appreciate your comments in advance!
-
Hi Vida,
Do the two models produce the same objective value when solved?
I mean I prefer continuous ones to decrease the computational time.
If you have a model whose feasible region is given by an integral polyhedron then relaxing all variables to be continuous can result in a faster solve - but this is due to the model doing a LP presolve rather than a MIP presolve (which is more computationally expensive). It sounds like your models do not have this property - i.e. there will always be some variables which be defined as integer. I would not expect the model to solve faster by setting these variables to continuous - if anything I'd expect the model where they are integer to be faster because you are encoding more information into the model that can be used in the presolve routine.
Moreover, the solving process is dependent on big M as well, which is very confusing to be determined sometimes.
I'm sorry I don't understand this sentence, could you give some more explanation?
- Riley
0 -
Hi Riley,
Thank you for your comment and apologize for my late response.
Regarding your first question, no, they do not produce the same objective function within a predetermined time limit (e.g., 100000).
As for my second issue, my model contains linear Big-M constraints, and the solving time is highly dependent on the choice M value, which is tricky.
- Vida0 -
Hi Vida,
The smaller the M values the better. As the M values become larger you are more likely to experience trickle flow. For example, if you have a constraint y <= 1000000 * x, where x is binary and y >= 0. With the default value of IntFeasTol (1e-5), x = 0.0000099999, y = 9.9999 is integer feasible, implying that y can be positive even when x is zero. Such behaviour can lead to unexpected results. Try to use the smallest possible values of Big-M. See Dealing with big-M constraints.
Also, please be aware that to make accurate conclusions regarding the solve time and choice of M values you need to run the model across several values of Seed and compare distributions - see How can I make accurate comparisons?
- Riley
0 -
Hi Riley,
Thank you for your time. I will go through them.
- Vida
0
Please sign in to leave a comment.
Comments
4 comments