Optimality Gap

The optimality gap quantifies the distance between the value of the best feasible solution found (upper bound UB, under minimization) and the best dual bound obtained so far (lower bound LB); two standard definitions exist. Absolute gap = |UB - LB|. Relative gap (the canonical MILP variant) = |UB - LB| / max(ε, |UB|), or in some solvers |UB - LB| / max(ε, |LB|) — the denominator choice differs by vendor, with ε guarding against division by zero. A zero gap certifies the incumbent as optimal and terminates the algorithm; in practice solvers stop with a 'near-optimal' flag once the gap falls below a user-specified tolerance (often 0.01-1%). The logical foundation is duality: in LP, weak duality gives UB ≥ LB for any primal-dual feasible pair, and strong duality turns this inequality into equality for any feasible bounded LP. In MILP the LP relaxation produces the LB, branch-and-bound updates the LB node-by-node, and primal heuristics plus branching exploration update the UB. Interpretation: a 5% gap means 'the solution value is at most 5% worse than the optimum' — no further improvement is mathematically possible below the known LB. Practical uses include risk communication to management (worst-case shortfall), early-termination decisions (time-quality trade-off in long branch-and-cut runs), and benchmarking heuristics (how 'good' is a heuristic measured against the gap). Lagrangian duality gap in convex nonlinear programming and relaxation gap in non-convex programming are analogous concepts. Canonical references include Nemhauser and Wolsey (1988) and Wolsey (1998).