Is there any benefit to providing multiple MIP starts?

Answered

Rasmus Mikkelsen

• May 03, 2019 12:16

Hello

I was wondering if there is any benefit to providing multiple (and perhaps very different) start solutions to Gurobi? Is Gurobi able to use and combine information from different initial solutions or is it only the best MIP start that matters?

0

• 

  Jakob Schelbert

  • May 04, 2019 09:58

  

  

  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
• 

  Daniel Espinoza

  • May 06, 2019 12:45

  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
• 

  Rasmus Mikkelsen

  • May 07, 2019 09:40

  

  

  

  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
• 

  Tobias Achterberg

  Gurobi Staff

  • May 07, 2019 12:09

  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
• 

  Rasmus Mikkelsen

  • May 07, 2019 12:17

  

  

  

  Thank you Tobias for clearing that up.

   

  0

Please sign in to leave a comment.