Three patterns that go wrong, and the lever that fixes each one.
Chapter: 0b — MIP theory · lesson id mip-readlog · theory lesson
You met the node log in the branch-and-bound lesson: every solver streams $Z_{\text{LB}}$, $Z^{*}$, and the relative $Gap$ between them as the search progresses. When the solve is short and finishes cleanly, you barely look at the log. When the solve is slow, stalls, or terminates without proving optimality, the log is the only diagnostic you have. This lesson is about the three classic misbehaviour patterns and the lever that fixes each one.
Theorem (Sandwich property). At every moment during a branch-and-bound search, the true integer optimum $Z_{\text{opt}}$ satisfies $$ Z_{\text{LB}} ;\leq; Z_{\text{opt}} ;\leq; Z^{}, $$ where $Z_{\text{LB}}$ is the current best lower bound (over all live subproblems) and $Z^{}$ is the current incumbent. This holds for minimisation; for maximisation, swap the inequalities to $Z^{*} \leq Z_{\text{opt}} \leq Z_{\text{UB}}$.
Diagnostics flow from the sandwich. A healthy solve shrinks both sides toward each other. A misbehaving solve fails on one or both sides in a specific way. The interesting question is: $which$ side has stopped moving, and $why$?
Definition (Gap (relative)). The Gap reported in the log is $\dfrac{|Z^{} - Z_{\text{LB}}|}{|Z^{}|}$. Termination at gap $0$ proves the incumbent is optimal. Termination at, say, $5%$ leaves you with an approximately-optimal solution whose worst-case suboptimality is bounded by that gap.
Definition (Stalled gap). A $stalled\ gap$ is a stretch of the log where neither $Z_{\text{LB}}$ nor $Z^{*}$ has moved for many nodes (say 10% of the total processed so far). The solver is grinding through the search tree without proving anything new.
A stalled gap almost always means the LP relaxation is $loose$. When a child node's LP value is essentially the same as its parent's, pruning by bound is rare and the search has to enumerate combinatorially. Tighter relaxations are the lever.
Quick check. A maximisation MIP shows $Z_{\text{UB}} = 100$ and $Z^{*} = 80$ for hundreds of consecutive log lines, neither moving. What is most likely happening?
Definition (No incumbent). A log where $Z^{*}$ stays at $\pm\infty$ for many nodes means no integer-feasible solution has been found yet. The solver is exploring but cannot produce a single feasible point to anchor the search.
This signals one of two situations:
The standard lever is a $warm\ start$: supply a known feasible solution to the solver before it begins. The solver uses it to seed the incumbent, then improves from there. A poor warm start is still infinitely better than none — it gives the search something to prune against from line one of the log.
Definition (Premature termination). A $premature\ termination$ is when the solver stops because of a limit other than closing the gap — typically a time limit, a node limit, or a memory cap. $Z^{*}$ is the best integer-feasible solution found, but optimality is $not$ proven. The reported gap quantifies the worst case.
Premature termination is a $reporting$ problem, not a math problem. The solution is still feasible. You just need to know how far from optimal it might be — that is exactly what the gap is for.
Example (Computing the relative gap). A min-MIP log shows after 200 nodes: $Z_{\text{LB}} = 47.3$, $Z^{*} = 53.0$. Gap is $(53.0 - 47.3) / 53.0 = 5.7 / 53.0 \approx 0.1075 = 10.75%$. Most solvers default to a gap tolerance around $0.01%$, so this solve is still far from termination. The optimum lies in $[47.3, 53.0]$.
Example (Estimating convergence). Over 50 consecutive lines, $Z_{\text{LB}}$ moved from $19.1$ to $19.2$ and $Z^{*}$ stayed at $22.5$. Bound is gaining $0.1$ across 50 nodes — a rate of $0.002$ per node. Remaining gap is $22.5 - 19.2 = 3.3$. At the current rate, closing it requires roughly $3.3 / 0.002 = 1650$ more nodes. Either tighten the formulation, accept the current gap, or set a time limit and walk away with the approximate answer.
Recap.
Read this through MCP: read with path: "lessons/mip-readlog", or resource hlpl://lessons/mip-readlog.