Skip to main content

Comments

4 comments

Date Votes
  • David Torres Sanchez
    Gurobi Staff Gurobi Staff

    Hi Zohar,

    If your matrix is totally unimodular you should be able to relax integrality restrictions (binary variables are just continuous between 0 and 1) and still have an integer solution.

    Cheers, 
    David

    0
  • Zohar Levi
    • Edited

    Interesting. I quoted this in the math link.

    I did a preliminary check, relaxing the binary vars to real in [0,1], and rounding the solution. For 20 iterations (I'm solving this problem repeatedly), the constraints held, but then they failed. I haven't looked into it yet (or checked for unimodularity).

    However, the time it took to solve the relaxed problem was the same as the binary one. I suspected that I might have an easy, special case here since it found an optimal solution (to the binary problem) so quickly (under a second for a moderate size problem).

    I noticed that it "Found heuristic solution," which is returned as optimal. How can I find details on this heuristic?

     

     

    0
  • David Torres Sanchez
    Gurobi Staff Gurobi Staff
    • Edited

    I did a preliminary check, relaxing the binary vars to real in [0,1], and rounding the solution. For 20 iterations (I'm solving this problem repeatedly), the constraints held, but then they failed. I haven't looked into it yet (or checked for unimodularity).

    You need to ensure that indeed the matrix is totally unimodular after every iteration (not sure whether the changes you are making will affect this) to use this approach.

    However, the time it took to solve the relaxed problem was the same as the binary one. I suspected that I might have an easy, special case here since it found an optimal solution (to the binary problem) so quickly (under a second for a moderate size problem).

    Of course, this can be the case for small problems, you will see a benefit for larger cases.
    You could try solving the problem normally with binary variables for now and revisit this if it becomes a performance issue. Gurobi will make some deductions.

    I noticed that it "Found heuristic solution," which is returned as optimal. How can I find details on this heuristic?

    This only happens for easy + small models. Gurobi uses several heuristics and one cannot find out which one produced this solution.
    Not sure how useful this would be but you can try playing around with the heuristic-related parameters (e.g. set Heuristics to 0).

    Cheers, 
    David

    0
  • Zohar Levi

    Unimodularity: of course, I just haven't got to it yet.

    What I meant was since the problem is solved so quickly, then perhaps there's a special case here, where I can achieve a faster solution using a specific method. One thing that you suggested was unimodularity. In my other thread, I suggest other things such as Smith normal form. I assume you don't deal with those, but only with unimodularity.

    I set heuristics=0, and it didn't affect the run time. So it isn't something special that you do, but the usual branch and bound is effective enough.

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post