Any feasible plan, from any source at all, bounds the optimum from one side, and any relaxation bounds it from the other. The distance between them is the only thing actually proved at a given moment; closing it is what the search spends its time on; and reporting it is what honesty looks like when the exponential worst case cannot be ruled out. A small gap is not a probability.
Core ideas
One hard idea, and it is about what the word “proved” covers. The gap is a statement about the bound, and there is no probability anywhere in it.
A feasible plan is a lower bound for a maximisation because it is achievable; it can come from greed, from a tree, from a person who knows the business. A relaxation is an upper bound because it optimises over a larger set. Neither knows about the other, and the optimum is between them.
A gap of 5/2 on an incumbent of 21 proves that nothing whole beats 21 by more than 5/2. It does not say the optimum is near 23.5, and it does not say 21 is probably optimal. On this instance 21 is not optimal, and on the next one the plan found at the third node is optimal for a long stretch of nodes during which nothing has been proved about it.
gap ÷ incumbent: 5/2 on 21 is 5/42, about 11.9%. The incumbent is the number you have, which is the only one defined before the optimum is known, and it is what every solver reports. Dividing by the bound instead gives a different number and is a different claim, so the denominator belongs in the report.
The material
Where each bound comes from, what their difference proves, and why search order changes the work and never the answer.
The incumbent is the best feasible solution found so far, together with its value. It is a lower bound on the optimum of a maximisation and an upper bound for a minimisation, and its provenance is irrelevant: a plan is a plan.
The global bound is the best bound over every node still open, or the incumbent's own value when none is. The absolute gap is the difference between the global bound and the incumbent; the relative gap is that difference divided by the incumbent. A gap of zero means the incumbent is optimal, and that is a proof.
Take max 4x₁ + 3x₂ subject to 3x₁ + 2x₂ ≤ 17 welding and 2x₁ + 5x₂ ≤ 23 painting. The root relaxation is worth 261/11, about 23.73. Its answer is 23, at (5, 1). Watch what is proved along the way, taking the newest open node each time.
Read the second row as a sentence. “Nothing beats 21 by more than 5/2.” That is all of it. It is a statement about 47/2, which is a property of a relaxation, and it contains no claim about how likely 21 is to be best. As it happens 21 is not best: the answer is 23, two more, and well within the 5/2 the bound allowed.
The first row is worth as much as the others. With no incumbent there is no gap and nothing whatever has been proved — a bound alone rules out nothing, because it does not exhibit a plan. Two numbers are needed, and a report with one of them is not a weaker report; it is a different kind of statement.
A 2% gap proves that nothing beats the incumbent by more than 2%. There is no probability in that sentence and none can be smuggled in: the gap is a bound on how wrong the plan in hand could be, not an estimate of how wrong it is. The incumbent is frequently optimal long before the gap closes, and the nodes spent after it was found buy the proof rather than the plan.
That is also the honest answer to “can we stop?”. Stopping with a stated gap is a result: the plan is in hand and its worst case is quantified. Stopping without one leaves a plan and a hope, and the two look identical on a slide.
Search order changes the work and not the answer. On this instance, taking the newest open node closes the tree in nine nodes; taking the most promising open node closes it in seven, and reaches the answer without ever holding a worse incumbent — its first incumbent is 23, and the gap is zero the moment it appears. Neither order is right; they trade a good early plan against a fast-falling bound, and which helps depends on the instance.
The reason a gap is the deliverable at all is that the alternative cannot be promised. The search tree's worst case is exponential and that result belongs to the Algorithms path’s “Backtracking and Branch-and-Bound”; the vocabulary for saying what kind of hardness this is belongs to Discrete Mathematics’ “P, NP and NP-Completeness”. Neither is restated here. What is this lesson's own is the consequence: if the tree may not close, then the number you report has to be the pair.
Interactive
Two numbers that squeeze the optimum, and the only thing proved at any moment
Method
Five steps, and the last is the one that makes the other four worth doing.
Greed, a heuristic, last year's plan, a guess that turns out feasible. Its quality does not matter yet; its existence does, because without a feasible plan there is nothing for a bound to bound.
The root relaxation is the cheapest one. Later, the best bound over the open nodes is the global bound, and it falls as the tree grows because every child's region is smaller than its parent's.
Absolute, as an exact difference, and relative, against the incumbent. Say which denominator you used: the same tree supports two different percentages and only one of them is the convention.
“Nothing beats 21 by more than 5/2.” If the sentence you write contains “probably”, “roughly” or “close to”, it is not the sentence the arithmetic supports.
A plan with a gap of zero is an optimum with a proof. A plan with a gap of 5/42 is a result. A plan with no gap is a number, and nobody reading it can tell which of the three they have been handed.
One instance, run both ways. The answer is 23 in both; everything else differs.
The two runs illustrate the trade directly. Depth first had a plan worth 21 in hand after five nodes and spent four more proving it was beatable and then beaten. Best bound had no plan at all until node seven and then had the answer with a closed gap in the same step.
Which is preferable depends entirely on whether you might have to stop early. With a hard time limit, a run holding 21 with an 11.9% gap is worth more than a run holding nothing with a tighter bound, because the first can be acted on. That is a reason to prefer depth first early and best bound late, and it is why real solvers switch.
For a faded rehearsal, use the lab's first instance — the one whose bound comes down slowly — and stop the node count at each value in turn. The supplied first move is that the incumbent can never fall and the global bound can never rise, so the gap is non-increasing. Find the first node at which the gap is below 5%, and then say whether the incumbent changed after that point.
You should be able to produce an incumbent from a heuristic and a bound from a relaxation, compute the absolute and relative gaps with the denominator named, write the one sentence each stage licenses without the word “probably” in it, and say what changes and what cannot change when the search order changes.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.