Back to the on-screen lesson ·
Search with a bound: how a node is processed, why the search terminates, and why a weak bound makes it hopeless.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to process a node of a branch-and-bound tree — solve, prune, update the incumbent or branch — decide from two numbers whether a node can be discarded, and split a fractional variable correctly into two children that lose no integer solutions and exclude the parent's answer. You will also be able to say why the search terminates, why termination says nothing about speed, and why a weak relaxation rather than a slow solver is the usual cause of a run that will not finish.
From lesson 22: the relaxation bounds the optimum, and an incumbent bounds it from the other side. This lesson is what to do with those two numbers — a search that uses the bound to avoid looking at almost everything, and that is the reason integer programming is possible at all in practice.
The idea in one sentence: split the problem into subproblems, bound each one, and throw away any subproblem that cannot contain a better answer than the one already in hand.
The machinery:
Processing a node:
Why it terminates. Each branch narrows an integer variable's range, and the ranges are bounded, so a variable can only be split finitely often. The tree is finite.
Why it can still be hopeless. Termination is not speed. With $n$ binaries the tree has up to $2^n$ leaves, and the only thing standing between the search and that number is step 3. If the bounds are weak, almost nothing is pruned, and the search enumerates. That is why lesson 21's tight big-M and lesson 22's strong formulation are not fastidiousness — they are what make this method work.
Another way: picture
A tree drawn downwards, each node a subproblem. Some branches are cut short with a stroke — pruned, because nothing below could beat what is already found. A good run cuts nearly every branch within a few levels; a bad one grows the whole tree.
Another way: steps
The loop:
Maximise $5x + 4y$ over $6x + 4y \le 24$, $x + 2y \le 6$, $x, y \ge 0$ integer.
Root. Relaxation gives $(3, 1.5)$, value $21$. Fractional in $y$, so bound $= 21$ and branch on $y$.
Node A: $y \le 1$. Relaxation gives $(10/3, 1)$, value $\approx 20.67$. Fractional in $x$; branch again.
Node A1: $y \le 1$, $x \le 3$. Gives $(3,1)$, value $19$ — integral. Incumbent $= 19$.
Node A2: $y \le 1$, $x \ge 4$. Gives $(4,0)$, value $20$ — integral and better. Incumbent $= 20$.
Node B: $y \ge 2$. Relaxation gives $(8/3, 2)$, value $\approx 21.33$... but wait: with the incumbent at $20$ this node is not pruned, and must be explored. Branching on $x$ there gives $(2,2)$ with value $18$ and an infeasible child.
Every node is now closed, so the incumbent $20$ at $(4,0)$ is optimal. Five nodes instead of enumerating every integer point of the region — and notice that node B had to be opened, because its bound beat the incumbent. Pruning is decided by the numbers, not by how promising a branch looks.
No incumbent early. With nothing to prune against, the search must go deep before it can discard anything. Running a quick heuristic first is often the single biggest speed-up available.
Pruning on a tie without meaning to. A node whose bound equals the incumbent can be discarded if any optimal solution will do, and must be kept if all optimal solutions are wanted. Decide which, and say so.
Branching on a poor variable. The choice of which fractional variable to split on affects the tree size enormously. Solvers use elaborate rules; the naive "most fractional" is a common and mediocre one.
Blaming the solver. A search that will not finish usually has a weak relaxation. Look at the root gap before anything else.
A run typically finds the optimal solution early and then spends most of its time proving that nothing better exists. Watching the incumbent stop improving while the clock runs is not the method stalling — it is the method doing the second of its two jobs, closing the bound. This matters for how a run is used: if a decision needs a good plan, the run can be stopped as soon as the gap is acceptable and the plan in hand is usually optimal already. If it needs a proof of optimality, the remaining time is the price of that proof. Knowing which of the two you actually need is worth more than any solver setting.
Maximising, incumbent $= 33$. A node's relaxation comes back at $31$.
The two numbers.
Nothing inside that node can beat $31$, and $31 < 33$. So no descendant of it is worth examining.
The comparison decides it.
Discard the node and everything below it, unexamined — possibly millions of integer points, ruled out by solving one linear program. That single trade is the entire method, and it is why a bound rather than a solution is the object unit 4 is built around.
One LP rules out a subtree.
A fixed-charge model written with $M = 10^6$ where the capacity $50$ would do, as in lesson 21.
A weak formulation.
The root relaxation sets every $y_j$ to about $5 \times 10^{-5}$, pays essentially no fixed cost, and returns a value far above any achievable integer answer.
The bound is nowhere near the truth.
So almost no node is prunable: every bound beats the incumbent, and the search enumerates the tree. Changing $M$ to $50$ can turn the same model from unsolvable to seconds. The solver never changed, the search never changed, and the bound did.
The bound is the whole method.
Branching splits at the fractional value: floor for one child, ceiling for the other.
Split at the value it actually took.
So one child adds $x \le 4$ and the other adds $x \ge 5$.
Check the two properties that make this work. Every integer value of $x$ is in exactly one child, so no solution is lost. And $x = 4.7$ is in neither, so the parent's answer cannot come back — which is what guarantees the search makes progress rather than circling.
In a maximisation, a node's relaxation bound is $50$ and the incumbent is worth $19$. Prune or explore?
A relaxation returns $x = 5.4$ for an integer variable. What upper bound does the left child put on $x$?
Answer:
Put the handling of one node of the search tree in order.
Number the steps in order (write the number in the box):
A model has $9$ binary variables. How many leaves would a tree that branched on every one of them have?
Answer:
In a maximisation, a node's relaxation bound is $25$ and the incumbent is worth $25$. Prune or explore?
Why is branch and bound guaranteed to terminate on a bounded integer program?
| Adds a tighter upper or lower bound | Excludes the parent's fractional solution | Can be subdivided only finitely many times | Lets the finite tree be pruned aggressively | |
|---|---|---|---|---|
| A branch on a fractional integer variable | ||||
| Each child node | ||||
| Bounded integer variable range | ||||
| A strong relaxation bound |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A relaxation returns $x = 2.4$ for an integer variable. What upper bound does the left child put on $x$?
Answer:
You can run the branch-and-bound loop by hand, prune correctly, and explain the difference between terminating and finishing. Next: tightening the relaxation instead of splitting it.
9. Your turn: the relaxation returns $x = 4.7$. What are the two children?, step 3