Difference between two-step and single-step optimization

Answered

Mohammadamin Edrisi

• July 02, 2020 12:11

Hi, 

I have a model for which I have done two experiments to investigate the performance of Gurobi. First, I used a time limit of 3600 seconds to optimize the model with MIPGap=0.01, and it finished optimization because of reaching the time limit without a gap below 0.01. Secondly, I set the MIPGap to 0.02 and time limit=300 seconds. After it reached below this gap, I continued optimization with MIPGap=0.01 with a time limit of 2000 seconds, this time, the model reached a gap equal to 0.073. Overall, it used less time in the second experiment and it reached a better solution.
My question is that whether optimizing the model in two steps can affect the runtime and the optimal solution compared to a direct/single-step optimization with more/even time limit?
I appreciate it if you answer my question.

Best,
Mohammad

0

• Official comment

  

  Simranjit Kaur

  Gurobi Staff

  • December 06, 2024 00:44

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Eli Towle

  Gurobi Staff

  • July 02, 2020 23:25

  Hi Mohammad,

  Yes, optimizing a model in two steps like this can affect the solution returned by Gurobi. With the first approach, Gurobi performs a single solve with a time limit of one hour and optimality tolerance of 1%. With the second approach, Gurobi uses a different time limit and optimality tolerance, then warm-starts the second solve with the best solution it found. You are really solving the problem in two different ways, so it could happen that you obtain different solutions at different times.

  I'll note that optimizing in this way does not affect the optimal solution(s) to your problem. Gurobi may return different solutions (even with the same value of MIPGap), because there may be multiple feasible solutions that satisfy your optimality tolerances, as small as they might be.

  Also, this two-step approach might sometimes produce high-quality solutions faster, but this of course will not always be the case.

  Thanks,

  Eli

  0
• 

  Mohammadamin Edrisi

  • July 21, 2020 06:58

  

  

  

  Hi Eli, 
  
  Thanks for your comprehensive response! 

  Best,

  Mohammad

  0

Post is closed for comments.