Is there any benefit to providing multiple MIP starts?

Answered

Comments

5 comments

  • Jakob Schelbert

    Hi Rasmus,

    To the best of my knowledge the best solution is used to cut off parts of the branch-and-bound-tree that cannot yield better solutions that the one provided. If I understand your question correctly, you have several solutions and are wondering if only the one with the best objective value is beneficial?

    I'd say it does not hurt to also provide other solutions, gurobi will not use them if they are not helpful in the solving process, but I'd love to hear from one of the developers whether there are some benefits...

    0
    Comment actions Permalink
  • Daniel Espinoza

    Hi Rasmus,

     

    If you provide several (fully defined) feasible solutions, then the behavior is equivalent as just providing the best one. Now, if you provide several **partial** mip starts, the story is different, as the solver will try to complete each of them (within some limits), this can be very powerful in some applications. 

    1
    Comment actions Permalink
  • Rasmus Mikkelsen

    Hi Jakob and Daniel

    Thank you both for your responses!

    @Daniel: Are you suggesting I remove information from my complete solutions and feed the resulting partial solutions to Gurobi as MIP starts, in the hopes that the Gurobi repair heuristic findes something beneficial? Or am I misunderstanding? You say that this approach can be very powerful in some applications. Would you mind giving an example?

    0
    Comment actions Permalink
  • Tobias Achterberg

    No, the point is that in some cases the user does not have a complete solution at hand, but is just speculating that a certain combination of variable assignments can be extended to a full solution. In such situations, it is often beneficial to provide multiple such assignments so that Gurobi can try to complete different start vectors in the hope that at least one of them yields a solution of good quality.

    If you have full start vectors available that are feasible solutions, there is usually no need to provide multiple of them. Just providing the one that leads to the best objective value should be good enough.

    Regards,

    Tobias

     

    0
    Comment actions Permalink
  • Rasmus Mikkelsen

    Thank you Tobias for clearing that up.

     

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk