Beaten by a naive method solving MILP
Ongoing
I have an MILP (mixed int linear prog).
There is the comiso library
https://www.graphics.rwth-aachen.de/software/comiso/
which does something super naive:
- Solve the problem treating all vars as continuous.
- Pick an int var.
- Round it to the closest int, and keep its value fixed for the next iterations.
- Iterate until all int vars are fixed.
Somehow, this naive method beats gurobi by something like seconds vs minutes. Yes, it doesn't have any guarantees, and sometimes it fails (it doesn't go over all the tree like gurobi), but for my problem it's enough.
I was wondering if gurobi has a similar option that could perform similarly.
-
By default, Gurobi solves models to global optimality. Finding a globally optimal solution can be much more difficult than finding a feasible solution. If your goal is to find a feasible solution without any quality guarantees, you could try setting the SolutionLimit parameter to 1.
0 -
I'm familiar with the SolutionLimit param, and it's not about the difference between feasible and globally optimal (I never have enough time for that). The naive algorithm doesn't guarantee anything, not even feasibility. Often, though, it can be effective enough.
0 -
The algorithm you describe sounds like the fix-and-dive heuristic. Gurobi has its own internal implementation of this heuristic that it might use when solving a MIP. You can also write your own implementation - this is done in the fixanddive code examples (e.g., fixanddive.py).
0 -
Cute, you suggest that I implement it myself, and since it's a linear program, I don't really need gurobi for that :)
The thing is that I use matlab, and loops are kind of a no-no (same for python or any other interpreted language by the way). I was hoping for some flag to tell gurobi to do that (I'm using it through yalmip). But yeah, otherwise I can do my own thing or write a .mex for comiso that I mentioned earlier. It's about performance: you need to pre-factor the matrix and iterate with back substitution or something.
To be fair, the heuristic is naive, and gurobi does so much more. One can say that it's not even its job to go there but my responsibility to check as a user(?).
0
Please sign in to leave a comment.
Comments
4 comments