# Connections between Bounds in MIPs

we are currently learning about MIP/MILP minimization at university and have become familiar with the branch-and-bound algorithm. Unfortunately, the relationship between upper bound, lower bound and dual bound (as shown here) is not clear to me, nor what the optimality gap is, or when a MIP can be solved optimally.

The definition of optimality gap varies by solver and can be confusing to interpret when the bounds have opposite sign, but the general metric is a nonnegative ratio: $$\frac{\text{upper bound} - \text{lower bound}}{\epsilon+\text{absolute value of either lower bound or upper bound}},$$ where $$\epsilon$$ is a small positive constant to avoid division by $$0$$. The idea is that the gap decreases to $$0$$ as the solver finds better bounds, so it is a measure of progress toward optimally solving the problem. Most solvers allow you to set an optimality tolerance as a termination criterion so the solver will stop when it finds a feasible solution that is provably within that optimality gap.