3.7.18 · D5Algorithm Paradigms
Question bank — Branch and bound
Two words used everywhere below:
- incumbent — the best complete, feasible solution found so far (its objective value is your "current best to beat").
- bound — an optimistic estimate of the best objective value possibly achievable inside a subtree (an over-estimate for maximization, an under-estimate for minimization).
True or false — justify
A tighter (closer to the true optimum) bound always prunes at least as much as a looser one.
True — a tighter valid bound is closer to reality, so more subtrees fail the "even the best case is bad" test earlier; the cost is that computing a tighter bound is usually more expensive per node.
Branch and Bound and Backtracking are the same algorithm.
False — backtracking prunes only on feasibility (is this partial solution legal?) to find any/all solutions; B&B adds a cost bound to find the optimum. B&B = backtracking + bounds.
B&B has strictly better worst-case time complexity than brute force.
False — in the worst case nothing prunes and B&B is still exponential (, ); see Big-O Notation. It only improves average/practical time.
For a maximization problem you should prune a node when its bound is greater than the incumbent.
False — for maximization the bound is an upper bound; you prune when , i.e. when even the best-possible value can't beat what you already have.
The fractional-knapsack value is a valid upper bound for the 0/1 knapsack node.
True — allowing fractions gives more freedom, so the relaxed optimum can never be worse than the integer optimum; that "never worse" is exactly what makes it a safe over-estimate for a 0-1 Knapsack maximization node.
Once a node passes the bound test and enters the live set, it can never become prunable later.
False — the incumbent may improve while the node waits in the queue, so a node that was promising can become hopeless; that's why we re-test the bound when we pop it.
Least-Cost (LC) B&B is guaranteed to find the optimum faster than FIFO or LIFO B&B.
False — LC (best-bound-first) usually reaches good solutions sooner, but no ordering changes the worst case; on adversarial inputs any ordering explores the whole tree.
If a bound equals the incumbent value exactly, the node can be safely pruned (in minimization).
True — a node whose lower bound equals the incumbent cannot yield a strictly better solution, so pruning it loses nothing (any tie is already matched by the incumbent).
Using a pessimistic estimate as the bound is safe as long as it prunes a lot.
False — a pessimistic estimate can be worse than what a subtree truly contains, so you may prune the branch holding the real optimum and return a wrong answer. The bound must be provably optimistic.
The TSP 2-min lower bound can only stay the same or increase as we force more edges.
True — forcing edges removes freedom, so the cheapest way to complete the tour under those constraints can only cost the same or more; the optimistic estimate tightens (goes up) with depth.
Spot the error
"For minimization I'll prune whenever the bound is less than the incumbent."
The logic is reversed — a low lower bound means the subtree might contain something great, so you must keep it. Prune only when .
"I checked bound(child) < incumbent before inserting, so I don't need to check again when I pop the node."
The incumbent may have dropped (improved) while the child sat in the queue, making it now prunable. Re-test
bound(node) ≥ incumbent at extraction — that's the continue in the pseudocode."My bound is a fast heuristic guess of the tour length; close enough to prune with."
A heuristic that isn't a guaranteed under-estimate can exceed the true completion cost and prune the optimum. Only relaxation-based, provably optimistic bounds are safe.
"Initial incumbent for a maximization problem should be ."
For maximization the incumbent starts at (or the value of any known feasible solution); you're tracking the best (largest) value found, and a huge starting value would make every real solution look worse.
"Since greedy solves the fractional relaxation exactly, greedy also solves 0/1 knapsack."
Greedy is exact only for the fractional relaxation; the 0/1 version forbids fractions, so greedy can be sub-optimal — that gap is precisely why 0/1 knapsack needs B&B or Dynamic Programming.
"I'll prune a node the moment its bound is worse than a partial (incomplete) solution's value."
You prune against the incumbent, which must be a complete feasible solution; a partial solution isn't a real, achievable value to compare against.
"B&B always uses a priority queue."
Only Least-Cost B&B uses a priority queue; FIFO B&B uses a queue and LIFO B&B uses a stack. The data structure defines the search order, not the paradigm.
Why questions
Why must the bound be optimistic rather than accurate?
Because pruning is a proof — "even the best case here is no better than my incumbent." An optimistic bound guarantees nothing inside beats it, so cutting is safe; an accurate-but-not-optimistic bound offers no such guarantee.
Why does the TSP lower bound multiply the sum of two-cheapest edges by ?
Each edge touches two cities, so summing each city's two cheapest incident edges counts every edge roughly twice; halving corrects the double-count and keeps it a valid under-estimate. See Travelling Salesman Problem.
Why do we branch on the highest value-density item first in knapsack?
The densest item dominates the optimistic completion, so deciding it first produces the sharpest bounds early, letting us establish and beat an incumbent faster — stronger pruning sooner.
Why can A* Search be viewed as Branch and Bound in disguise?
A* expands the node with smallest where the heuristic is an admissible (optimistic) under-estimate of remaining cost — exactly an LC-B&B bound guiding a best-bound-first search.
Why does forcing a decision in a branch make the bound tighter, not looser?
Forcing removes options, so the relaxed problem has less freedom to be cheap (min) or valuable (max); with fewer ways to be optimistic, the optimistic estimate moves toward reality.
Why isn't B&B just "smarter Dynamic Programming"?
DP reuses overlapping subproblems via memoization; B&B explores a search tree and discards subtrees by bound comparison. They can be combined, but pruning-by-bound and memoizing-by-state are different mechanisms.
Edge cases
What is the bound of a complete solution (a leaf), and why?
It equals its own exact objective value — there's nothing left to complete, so the optimistic estimate collapses onto the real value; that value is what may become the new incumbent.
What happens when every node prunes immediately after the first incumbent is found?
You return that incumbent as optimal after only trivial extra work — the ideal case where the first complete solution's value already dominates all remaining bounds.
If the first feasible solution found is already optimal, does B&B still explore the rest of the tree?
It may still pop and test remaining live nodes, but each fails the bound check and is pruned in one comparison; it never expands them, so the extra cost is small but not zero.
What if two different subtrees have identical bounds — does correctness suffer?
No — ties only affect order of exploration (LC may pick either), never correctness; both will be explored or pruned consistently against the incumbent.
Zero-capacity knapsack (): what does the root bound evaluate to and why?
The bound is — no item fits even fractionally, so the optimistic completion adds nothing; the empty selection is immediately optimal.
Single-city (or single-item) problem — is B&B meaningful?
The tree is a single node that is already complete, so B&B returns it instantly with no branching; the paradigm degenerates gracefully to "the only solution is the answer."
What if no feasible complete solution exists (over-constrained problem)?
The incumbent never improves from its initial , and B&B terminates reporting no solution — the bounds simply never get beaten because there is nothing to beat.
Recall Fast self-test
Direction of the bound for maximization? ::: Upper bound; prune when . Why re-check the bound when popping? ::: The incumbent may have improved while the node waited, making it now prunable. Is a pessimistic bound ever safe? ::: No — it can prune the subtree holding the true optimum, giving a wrong answer.