The MIPGap parameter controls the minimal quality of the returned solution. It is an upper bound on the actual MIP gap of the final solution. It can happen that Gurobi runs until finding a solution that is significantly better than the MIP gap because it is not always possible to terminate with the given MIP gap requirement. One reason is that the gap improvement is happening in jumps rather than a continuous progression:
Please note that the MIPGap parameter is not just a termination criterion but also influences the algorithm in other parts. It may happen that the solver takes a different path and behaves differently when using a different MIPGap.
Recall that the gap in Gurobi is computed using the following formula:
\[\frac{\left| \text{ObjBound} - \text{ObjVal} \right|}{\left| \text{ObjVal} \right|}\]
Some decision-makers worry that they could leave money on the table by setting a positive MIP Gap tolerance ε. To alleviate that concern, please note there could be different scenarios in the optimization process:
- Sometimes, Gurobi finds the global optimal solution early on while the current MIP gap is bigger than the allowed tolerance (e.g. current MIP gap of 40% vs an ε of 0.01%), so the rest of the optimization time is spent trying to get the certificate of optimality by pushing the dual bound towards the objective value of the incumbent solution.
- Sometimes, however, Gurobi finishes the optimization run (because the current MIP Gap is already within tolerances as defined by ε) and reports a solution that may not be the optimal solution. In this case, we say the incumbent solution is ε-suboptimal, as the objective value it attains is at most ε (e.g. 0.01%) worse from the value attained by other solutions that could be found if we continue to explore the branch-and-bound tree (although there's no guarantee that such solutions exist, as already explained in the bullet point above).
In any case, for a given MIP Gap tolerance ε, once Gurobi is finished, you are guaranteed that the optimal solution is in the ε-neighborhood of the solution found by the solver. Moreover, for real-world applications, it is always sensible to set a positive MIP Gap tolerance since:
- Numerical Precision: Solvers use finite precision arithmetic. A zero gap can cause problems due to numerical limits.
-
Computational Time: Achieving an exact zero gap is often time-consuming and resource-intensive. That's why Gurobi by default uses a small, non-zero value for
MIPGapto balance solution quality and solve time, providing near-optimal results without excessive computation. - Diminishing Returns: Smaller gaps lead to marginal solution improvements but require exponentially more effort.
- Solver Limitations: Forcing a zero gap can interfere with solver heuristics, thus reducing performance.
Comments
0 comments
Article is closed for comments.