About the MIPgap

Answered

jiaze ma

• August 25, 2021 02:42

Hello:

I set the MIPgap to be 1% as follows (using julia):
m_l = Model(with_optimizer(Gurobi.Optimizer,MIPGap=1e-2)).

However, when I check the log, gurobi solved the problem to within 0.01%.
I wish gurobi could stop when reaches 1% of optimality gap, but it keeps giving me better solutions.

Can i ask why gurobi ignored the parameter i set?

Here is the log: 

0

• 

  Jaromił Najman

  Gurobi Staff

  • August 25, 2021 08:40

  Hi,

  The MIPGap value refers to at least the gap value that Gurobi has to reach before declaring optimality. This does not mean that Gurobi will always terminate with the exact MIPGap set by the user. In your case, Gurobi found a feasible point through a heuristic, which with the given lower bound is already within 0.01% optimality gap. This does not mean that the parameter MIPGap=1e-2 is ignored or that Gurobi takes more time than actually required. This just means that Gurobi overshoots the requirements by finding a very good feasible point. In other words, Gurobi does not search for feasible points that are exactly in the 1% gap set by the user but rather tries to find the best point it can get and terminates when the MIPGap requirement is met.

  You can see that your setting is respected by the line

  Optimal solution found (tolerance 1.00e-02)

  Best regards,
  Jaromił

  0
• 

  jiaze ma

  • August 25, 2021 17:34

  

  

  

  Hi,

  Thanks for your response.

  "The MIPGap value refers to at least the gap value that Gurobi has to reach before declaring optimality"

  Does this mean that as long as I set MIPgap>=0.01% (default), it does not affect the final result? Only when I set the MIPgap<0.01%, Gurobi will give me some better solution?

  Do we have a feature that allows me to stop Gurobi at exactly 1% of optimality? Or can I stop Gurobi at 0.1%~1% of optimality?

  Thanks much!

  0
• 

  Jaromił Najman

  Gurobi Staff

  • August 25, 2021 17:53
  • Edited

  Hi,

  Does this mean that as long as I set MIPgap>=0.01% (default), it does not affect the final result?

  No, setting a MIPGap \(X\) guarantees that the relative difference between the final feasible solution and the best proven bound is \(\leq X\) (cf. the documentation of MIPGap). If you set a MIPGap of 1% then it is guaranteed that Gurobi will return an optimal solution with a final MIPGap \(\leq 1\%\) and it is possible that this optimal solution has a MIPGap of  \(<0.001\%\) or even \(0\%\). There is no guarantee and (in most cases) it cannot be said a priori how good the final solution will be.

  Only when I set the MIPgap<0.01%, Gurobi will give me some better solution?

  While setting a MIPGap of \(\geq 0.01\%\) can provide you an optimal solution with a final MIPGap \(< 0.01\%\). Setting a MIPGap to a value \(<0.01\%\) will guarantee that the final solution is below the gap of \(0.01\%\).

  Do we have a feature that allows me to stop Gurobi at exactly 1% of optimality? Or can I stop Gurobi at 0.1%~1% of optimality?

  There is no feature which allows you to stop Gurobi at exactly 1% or any other MIPGap value. Gurobi will stop whenever it reaches a gap of  \(\leq\)MIPGap.

  Best regards,
  Jaromił

  0

Please sign in to leave a comment.