MIP Gap and Solver Termination Criteria

Branch-and-bound rarely runs all the way to a provably optimal solution. The cost of closing the very last fraction of a percent of optimality can be enormous, so solvers stop as soon as the current solution is provably within a small margin of optimal. To make this precise, we track two quantities throughout the search.

At any point in the search, a solver maintains:

• The incumbent $\bar{z}$: the objective value of the best integer-feasible solution found so far.
• The best bound $\underline{z}$: the best LP-relaxation objective across all open (unpruned, unexplored) nodes.

For a minimization MIP, every integer-feasible objective is at least $\underline{z}$ and the current incumbent is no worse than $\bar{z}$, so the optimal value $z^*$ is sandwiched as

$$\underline{z} \le z^* \le \bar{z}.$$

The absolute MIP gap is the width of this interval:

$$\text{gap}_{\text{abs}} = \bar{z} - \underline{z}.$$

The relative MIP gap scales the absolute gap by the size of the incumbent:

$$\text{gap}_{\text{rel}} = \dfrac{\bar{z} - \underline{z}}{|\bar{z}|}.$$

This is what Gurobi and CPLEX report as "MIPGap".

Illustration: if $\bar{z} = 50$ and $\underline{z} = 45,$ then

$$\text{gap}_{\text{abs}} = 50 - 45 = 5, \qquad \text{gap}_{\text{rel}} = \dfrac{5}{50} = 0.10 = 10\%.$$

The incumbent is guaranteed to be within $10\%$ of the true optimum.