Back to the on-screen lesson ·
Split at a fractional variable, bound each piece, and discard whole subtrees that cannot win.
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 branch on a fractional variable into two children with the right bounds, compare a node's bound with the incumbent to decide whether to prune it, name the three conditions that close a node, put the steps of handling a node into order, and bracket the integer optimum between the incumbent and the best open bound.
You can relax an integer program for a bound, and you know the bound may not be rounded into an answer. Branch and bound is what to do with the bound instead: use it to throw away regions of the search without looking at them.
A node is a sub-problem: the original with some extra bounds added. Its bound is its relaxation's optimum. The incumbent is the best integer plan found so far. To prune a node is to discard it and everything below it, unopened.
Solve the relaxation. If its answer is integral, it is the answer. If not, some variable $x_j$ came out fractional, at $v$ say — and no integer plan has $x_j$ strictly between $\lfloor v \rfloor$ and $\lceil v \rceil$. So split: one child adds $x_j \le \lfloor v \rfloor$, the other adds $x_j \ge \lceil v \rceil$. Between them the children keep every integer plan the parent had and exclude the fractional point, so each child's relaxation must return something new.
Three ways a node closes. Its relaxation is infeasible; its relaxation is integral, in which case it may become the new incumbent; or its bound is no better than the incumbent, in which case nothing below it can win and the whole subtree goes.
That third one is where the method earns its keep: one comparison discards an exponential number of plans. Two things make it fire more often — a tight relaxation, and a good incumbent found early, which is why heuristics are run alongside an exact search rather than instead of it.
Stopping early. The incumbent and the best open bound bracket the optimum, so a run cut short still reports a plan and a guarantee.
Another way: steps
Another way: example
$\max 5x_1 + 4x_2$, $6x_1 + 4x_2 \le 24$, $x_1 + 2x_2 \le 6$, integer. Relaxation $(3, 1.5)$, bound $21$. Branch on $x_2 \le 1$: $(3.33, 1)$, bound $20.67$; then $x_1 \le 3$ gives $(3, 1)$, integral, value $19$ — the incumbent. The branch $x_2 \ge 2$ bounds at $18 < 19$, so it is pruned.
A node is pruned because its relaxation is fractional, which is the opposite of a closing condition — a fractional answer is the signal to branch. The second error is pruning against an estimate rather than a valid bound: a heuristic guess can be optimistic in the wrong direction and throw away the subtree holding the answer.
A node with twelve binaries still free has a relaxation bound of $118$, and the incumbent is worth $120$.
The bound caps the subtree.
Nothing below it can reach $120$, so the node is closed without any of it being solved.
One comparison.
Twelve free binaries is $4096$ combinations, none of which was visited. That is the whole method in one line.
An exponential subtree, discarded.
Adding bounds to an infeasible problem can only keep it infeasible, so every child would be infeasible too.
Nothing below it.
So the node is closed at once, with nothing recorded and nothing to branch on.
The best integer plan so far is worth $38$. Three open nodes have relaxation bounds of $47$, $36$ and $44$. Fill in each node's bound minus the incumbent.
| Bound minus incumbent | |
|---|---|
| Node with bound $47$ | |
| Node with bound $36$ | |
| Node with bound $44$ |
A node of a branch-and-bound tree with $8$ integer variables has just been taken off the list. Put the steps of handling it into order.
Number the steps in order (write the number in the box):
In a maximisation, a node's relaxation gives $33$ and the incumbent already achieves $34$. How many descendants of that node need exploring?
Answer:
The incumbent is worth $36$. Which of these closes a node of the search tree?
A node's relaxation gives $x = 19/2$, so the search branches on $x$. Complete the bound each child adds.
The first child adds the upper bound a, and the second adds the lower bound b.
A search has an incumbent worth $53$, and the best bound among all its open nodes is $60$. Give the interval the integer optimum must lie in.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The best integer plan so far is worth $34$. Three open nodes have relaxation bounds of $37$, $27$ and $40$. Fill in each node's bound minus the incumbent.
| Bound minus incumbent | |
|---|---|
| Node with bound $37$ | |
| Node with bound $27$ | |
| Node with bound $40$ |
You can run the branch-and-bound loop on a node and say why a pruned subtree may be discarded unopened. Say in your own words why a good plan found early makes the whole search faster.
7. Your turn: a node's relaxation is infeasible. Do you branch on it?, step 2