Skip to main content

Can I get optimal solution by tuning MIPGap?

Answered

Comments

2 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Bahar,

    Setting the MIPGap to 0.1 means that Gurobi will declare any solution within this gap as optimal. For a minimization problem, if you have a feasible point \(x\) with objective value 100 and Gurobi proves a lower bound of 90, then the algorithm terminates and declares \(x\) as optimal because \(\frac{100-90}{100}\leq 0.1\). It is true that there can be a better feasible solution point with value strictly lower than 100. However, by setting the MIPGap parameter to 0.1, you tell the solver, that for you any feasible point with a proven optimality gap of 10% is good enough (optimal). If you want the truly optimal solution, then you have to set MIPGap=0. In most applications very low MIPGap values are not required and also not practical. This has multiple reasons. One reason is that the algorithm requires more time to reach a lower MIPGap, often reaching a MIPGap of 0 is not possible within days or weeks. Additionally, you have to consider the tradeoff between solver runtime and the best possible improvement. Another reason is that most mathematical models in practice do not perfectly depict the reality. Thus, even if Gurobi would give you the best solution available, you would still have to (slightly) adjust some solution point values due to numerical precision and/or model inaccuracies to ultimately use the solution in your application.

    For more details and a better understanding of Integer programming, I recommend having a look at Laurence Wolsey's Integer Programming book. You can find additional books and blogs of interest on our Resources website.

    Best regards, 
    Jaromił

    0
  • Bahar NASIRIAN
    Conversationalist
    Curious
    Gurobi-versary

    Thank you so much for your detailed explanation .

    Regards,

    Bahar

    0

Please sign in to leave a comment.