Optimizing partial warm start mip solution

Ongoing

Ramin Fakhimi

• July 23, 2024 14:37

Hi there,

I have an assignment problem with extra functionality (i.e., extra variables and constraints in the model). Having the assignment variable values (partial solution), I need to optimize and figure out the rest of the variables.

I set the StartNodeLimit parameter to a large number (200) to let Gurobi spend more time optimizing the partial solution. I passed a partial optimal solution to Gurobi. However, the warm start-generated solution had a large optimality gap (about 5%-10%). 
Then, I used the partial optimal solution as a hard constraint. Gurobi solved the partially fixed model quickly. My questions are:

• How can I replicate the same behavior in Gurobi?
• Why does Gurobi stop optimizing the warm start model?

 

Related to

• MIPStart

1

• 

  Aron Zingler

  • July 29, 2024 10:57

  

  

  

  When you mention that the solution generated by warm starting has a large optimality gap, are you referring to the intermediate output from Gurobi while it is running, or is this based on a test case where you already know the optimal solution and can thus compute the optimality gap against this known solution?

  In the first scenario, I can think of two potential causes:

  1. The partial solution provided to Gurobi might be suboptimal, meaning that a better solution exists where some variables take different values than those in your warm start.

  2. Gurobi cannot definitively rule out that a better solution exists (with changes compared to the partial solution). Therefore, even if the warm-started solution appears to be optimal (i.e., the upper bound has converged), Gurobi may need additional time to tighten the lower bound and prove its optimality.

  If you are confident that your partial solution is indeed optimal, fixing these values as hard constraints is the way to go. Otherwise, if an optimality gap of 5-10% is unacceptable, you should allow Gurobi to continue its search. Additionally, you might experiment with different values for the MIPFocus parameter depending on your specific goals.

   

  0
• 

  Ramin Fakhimi

  • August 07, 2024 14:43

  

  

  Hi Aron Zingler
  Thanks for your response. I wanted to test something and then get back to you. I calculate the optimality gap manually using the best-obtained bound (at the end of the optimization process) and the incumbent generated by the warm start algorithm.
  
  My issue with Gurobi's behavior isn't its inability to prove the optimality of the warm start solution. It is the way that Gurobi optimizes the partial solution. Gurobi does not optimize the reduced warm start model as I expected, and the StartNodeLimit is not helpful in my case.
  
  I also deactivated the extra functionality in the model, and it extracted an optimal solution for the assignment problem. I am using Gurobi 9.5.2 through Pyomo 6.4.1.

  0
• 

  Aron Zingler

  • August 07, 2024 15:25
  • Edited

  

  

  

  I am still a bit unsure that I understand exatly what you are doing.
  If I understand correctly, you give Gurobi a partial start (for example by using a MST file). You increase the StartNodeLimit parameter so that Gurobi spends more effort investigating these partial starts. You would like Gurbi to investigate the partial start more, because you know that this would lead to a good (the correct?) result (as you have seen when adding the partial start as constraints). 
  
  Intuitively, I can see two reasons for why you do not obtain the solution you get when fixing the partial solution:
  More nodes than 200 are needed to obtain the solution. So StartNodeLimit is still too small.
  The other reason could be that Gurobi internally has another criterion for stoping the completion process of partial solutions. For this, you have to wait for an anwer from the Gurobi experts. Maybe this was your question all along.
  
  Still, if you are confident that your partial solution is indeed optimal, I see no reason against fixing these values as hard constraints. This already seems to work for you. If you are not confident, there is a risk that increasing the effort spend completing the partial solution will not be beneficial enought to offset the time spent.
  
  
  
  

  0
• 

  Ramin Fakhimi

  • August 07, 2024 15:56

  

  

  Thanks. Yes, your understanding is correct.
  
  The issue with my approach is that removing constraints from the model is very time-consuming (even more than creating the model from scratch). Also, creating the model from scratch means I need to keep the used memory longer, which is not ideal since my model takes a few GB of memory. That's why I am looking for another solution.

  0
• 

  Ramin Fakhimi

  • August 07, 2024 17:37

  

  

  Hi Maliheh Aramon and Jaromił Najman
  Could you check this thread?

  0

Please sign in to leave a comment.