Beaten by a naive method solving MILP

Ongoing

Comments

4 comments

  • Eli Towle

    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
    Comment actions Permalink
  • Zohar Levi

    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
    Comment actions Permalink
  • Eli Towle

    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
    Comment actions Permalink
  • Zohar Levi

    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
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk