Solve the relaxation; if a variable comes back fractional, split the problem into two children that lose no whole-number plan and exclude the fractional point. Re-solve each child from its parent's final tableau, and close a node when it is infeasible, when its bound cannot beat the best plan in hand, or when its relaxation is already whole. What makes this a method rather than an enumeration is the bound, and the bound is a linear programme.
Core ideas
One hard idea, and it is the correctness argument: the two children between them keep every whole-number plan the parent had, and neither keeps the fractional point that caused the split.
If x₁ comes back at 37/18, the children are x₁ ≤ 2 and x₁ ≥ 3. The first still permits x₁ = 0; the second still permits x₁ = 5. Every whole value of x₁ satisfies one of the two, and 37/18 satisfies neither — which is the entire reason the method is correct and the entire reason it makes progress.
The bound says nothing inside that node beats this number. So a node closes when its relaxation is infeasible, when its bound cannot beat the best whole plan already in hand, or when its relaxation came back whole — in which case it is a new best plan. There is no fourth reason and no case in which a closed node needs revisiting.
Adding x₁ ≤ 2 to a solved tableau leaves it optimal and makes it infeasible, which is exactly the situation the dual simplex of “Duality and Sensitivity Analysis” was built for. Each child therefore costs a few pivots from its parent rather than a fresh solve, and the table in the lab names the method it used on every node.
The material
Why the split loses nothing, what each of the three closing reasons proves, and where the bound comes from.
Take max 5x₁ + 4x₂ subject to 6x₁ + 4x₂ ≤ 25 machine hours and 3x₁ + 5x₂ ≤ 22 inspection hours. The relaxation stops at (37/18, 19/6), worth 413/18, which is about 22.94 and is not a plan. Both coordinates are fractional, so there are two variables to choose between and the method works either way.
If the relaxation of a node returns x_k = v with v not an integer, the node is replaced by two children: the same problem with x_k ≤ ⌊v⌋ added, and the same problem with x_k ≥ ⌈v⌉ added. The node itself is not solved again.
Every integer point feasible for the parent is feasible for exactly one of the two children, and the parent's fractional optimum is feasible for neither.
Let x be feasible for the parent with x_k an integer. Then either x_k ≤ ⌊v⌋ or x_k ≥ ⌊v⌋ + 1 = ⌈v⌉, because there is no integer strictly between ⌊v⌋ and ⌈v⌉ when v is not an integer. So x satisfies one of the two added rows and every other row unchanged.
The parent's optimum has x_k = v with ⌊v⌋ < v < ⌈v⌉, so it satisfies neither added row. Hence the union of the children contains every whole-number plan of the parent and the two bounds are computed on strictly smaller regions.
□
That is the whole correctness argument, and it is why the children are inequalities. Fixing x₁ = 2 in one child and x₁ = 3 in the other would lose every plan with x₁ = 0 or x₁ = 4, and the search would return a confident wrong answer.
Branch on x₁ at 37/18. Child x₁ ≤ 2 bounds at 114/5 and stops at (2, 16/5), still fractional; child x₁ ≥ 3 bounds at 22 and stops at (3, 7/4). Split the first on x₂ at 16/5: x₂ ≤ 3 comes back at (2, 3), whole, worth 22, and becomes the plan in hand; x₂ ≥ 4 bounds at 58/3, about 19.33, which cannot beat 22, so it closes. Now x₁ ≥ 3 bounds at exactly 22 and cannot beat 22 either, so it closes too. Five nodes, no open nodes, answer 22 at (2, 3).
Read the last two closures again, because they are the method. Neither node was explored and neither needed to be: a bound of 58/3 is a promise that nothing inside is worth more than 58/3, and 22 is already in hand. The tree did not decide those subtrees were unpromising; it proved there was nothing in them.
The search tree itself — explore, keep the best so far, prune any branch whose optimistic bound cannot beat it, and accept that the bound's quality is the whole algorithm — belongs to the Algorithms path's “Backtracking and Branch-and-Bound”, which works it on a six-item knapsack with the fractional bound. What is this course's own is that the bound here is a linear programme, and that each child is re-solved from its parent's final tableau by the dual simplex rather than from scratch.
One reconciliation worth stating once: on a binary variable the two branching schemes are the same tree. “Include the item” and “exclude the item” are x ≥ 1 and x ≤ 0, which is exactly x ≥ ⌈v⌉ and x ≤ ⌊v⌋ for any v strictly between 0 and 1. The knapsack tree of that lesson and the tree here are one method described in two vocabularies.
None of this is a complexity result. Pruning removes subtrees that have been proved empty of better plans, and on a bad instance it removes none of them: the worst case is still exponential, and that fact is Algorithms’. The practical consequence is visible in the lab, where the order the nodes are taken in changes the work and never the answer — depth first closes this instance in five nodes and best bound takes seven, which is the opposite of the usual expectation and is what measuring is for.
Interactive
Branch on a fractional variable, bound each child, and prune for one of three reasons
Method
Five steps, and the fourth is the one that turns a search into a proof.
Exactly. Its value is that node's bound and its solution tells you whether there is anything to split. A whole solution here means this node is finished.
x_k ≤ ⌊v⌋ and x_k ≥ ⌈v⌉, as inequalities added to the node's own rows. Which variable you pick changes the shape of the tree and not the answer, so pick one and record which.
The added row makes the parent's optimal tableau infeasible without making it non-optimal, which is the dual simplex's case. A few pivots, not a fresh solve.
Infeasible, bounded out, or integral. Writing the reason next to the node is what makes the finished tree a proof: a reader can check each closure without re-solving anything.
An open node is an unproved region. If you must stop early, report the best plan in hand together with the best bound over the open nodes — which is the next lesson, and is what the lab does when it hits its budget.
One instance, taken depth first, branching on the first fractional variable. Every bound is exact and every closure names its reason.
Node 2 is the interesting closure. Its bound is 22, exactly equal to the plan in hand, and that is enough: nothing in a node beats the node's bound, so nothing there beats 22. It might tie 22, and there may well be a second optimal plan inside — the method finds an optimum, not all of them.
Node 4 shows why a branch is an inequality. Its region has x₂ ≥ 4, which forces x₁ down to 2/3, and the bound collapses to 58/3. Had the branch been the assignment x₂ = 4 the effect would have looked the same here and would have been wrong elsewhere, because x₂ ≥ 4 also contains x₂ = 5.
For a faded rehearsal, run the same instance branching on the second variable first — the lab has a control for it. The supplied first move is that the root is unchanged, since the root does not depend on the branching rule: x₂ = 19/6, so the children are x₂ ≤ 3 and x₂ ≥ 4. Predict the node count before you look, then say whether the answer moved.
You should be able to run a two-variable tree by hand with every node's bound as an exact fraction, name which of the three reasons closed each node, say why the two children lose no whole-number plan, explain what the dual simplex is doing between a parent and a child, and state what changes and what does not 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.