In a branch-and-bound search for a minimum-cost plan, what do the incumbent and the bounding function each do to let you skip a subtree?
answer
- two numbers, not one
- best achieved vs best possible
- optimistic estimate of the rest
- relax a constraint to get it
- compare, then cut the subtree
basics
~20 sThe incumbent is the best complete plan found so far, and its cost is the cut-off. The bounding function computes an optimistic cost for everything still reachable in a subtree; if that is no better, the subtree is discarded unexplored.
solid answer
~50 sBranch and bound is exhaustive search that refuses to enter regions it can prove are hopeless. The **incumbent** is the best complete, feasible plan found so far; for a minimisation objective its cost is an *upper* bound on the optimum. The **bounding function** takes a partial plan and returns an optimistic cost for the best completion of it — a *lower* bound, usually obtained by relaxing a constraint the real problem imposes. If that optimistic figure is no better than the incumbent's cost, no completion in that subtree can win, so the whole subtree is cut without being enumerated. The bound must never overshoot the true subtree optimum, or the search will prune the answer and still report success. Worst case remains exponential; what pruning changes is how much of the tree you actually walk on a real instance.
code
pseudocode · 19 linesbest_cost = INFINITY
best_plan = none
push(stack, root_partial_plan)
while stack is not empty:
node = pop(stack)
if bound(node) >= best_cost:
continue # cut: no completion here can win
if node is complete:
best_cost = cost(node) # new incumbent
best_plan = node
continue
for each child in branch(node):
push(stack, child)
report best_plan, best_costgo deeper
Remember there are two numbers: the best plan you have actually built, and an optimistic guess at the best plan you could still build. Skipping happens when the guess is not better than what you hold.
Explain the mechanics: the incumbent is an achieved upper bound, the bounding function a relaxation giving a lower bound, and pruning is the comparison of the two. Say which direction the bound must err in and why.
Show you have run this against a clock: seed the incumbent, measure nodes-per-second against nodes-pruned when you tighten the bound, and report the incumbent with the remaining gap rather than a bare plan.
Own the question of how much certification is worth. Paying for a tighter bound or a longer run buys a narrower interval; decide when that interval changes a decision and when a good plan with no certificate is the right purchase.
## The setting An overnight planning run has a fixed wall-clock budget and must return the cheapest plan it can defend by morning. The space of complete plans is exponential, so walking all of it is not an option. **Branch and bound** walks that space anyway, while refusing to look inside the parts it can prove cannot contain the answer. Two objects make the refusal possible: the **incumbent** and the **bounding function**. The search tree is built by *branching*: each node fixes one more decision, an internal node is a partial plan, and a leaf is a complete plan with a real cost. ## The incumbent: an achieved cost The incumbent is the best complete, feasible plan the search has produced so far. - It is **achieved**, not estimated — the number corresponds to a plan you could execute tonight. - For a minimisation objective it is therefore an **upper bound on the optimum**: the optimum is at most this. - It only ever improves; each cheaper complete plan replaces it. Until the first leaf is reached the incumbent is effectively infinite, which is why nothing prunes during the first descent. Seeding it with any feasible plan, however crude, makes pruning start near the root. ## The bounding function: an optimistic estimate The bounding function takes a partial plan and answers one question: *what is the best cost any completion of this could possibly reach?* For minimisation that is a **lower bound**, and it is normally computed by **relaxing** something the real problem enforces: - assume every remaining decision takes its individually cheapest option, ignoring that they conflict; - drop a capacity or an integrality requirement and solve the easier problem exactly; - add the cost already committed to a cheap optimistic estimate of the rest. The safety rule is one-directional and easy to get backwards: for minimisation the bound **must never exceed** the true optimum inside that subtree. A bound that is occasionally too high prunes the region holding the optimum, and the run finishes quickly, silently returning a worse plan while still claiming it searched everything. A bound that is too low is merely weak: it prunes less and costs time, but never costs correctness. ## The prune, step by step 1. Pop a node representing a partial plan. 2. Compute `bound(node)`, the optimistic cost of its best completion. 3. If `bound(node) >= incumbent_cost`, discard the node and everything below it — no completion there can beat what you already hold. 4. Otherwise, if the node is complete, it is cheaper than the incumbent, so it becomes the new incumbent. 5. Otherwise branch: generate children and continue. Because step 3 uses `>=` rather than `>`, subtrees that could only *tie* the incumbent are cut too. That is a deliberate choice: you get **one** optimal plan, not every optimal plan. If the caller needs all optima, the test must be strict, and the search gets more expensive. ## How tight should the bound be? | | Loose, cheap bound | Tight, expensive bound | |---|---|---| | Work per node | small | large | | Subtrees cut | few | many | | Typical failure | the tree explodes anyway | most nodes survive, and each cost a lot | | Good when | branching factor is small | completions are expensive to enumerate | There is no universally right setting. The productive question in an interview is not *which bound is better* but *what does one node cost me, and how many nodes does the extra tightness remove on instances like mine* — an empirical tradeoff, measured per instance family. ## What pruning does not buy - **It does not change the worst case.** On an adversarial instance nothing prunes and you enumerate the whole tree. Branch and bound is a practical accelerator, not a complexity result. - **It does not give a ratio.** A proven worst-case ratio is a different kind of guarantee, produced by a different family of methods. What branch and bound produces is instance-specific. - **It is not a heuristic.** Run to completion it returns a provably optimal plan, which is exactly why it is expensive. ## The payoff at a deadline The real reason engineers reach for this shape is that it is **anytime**. Stop the run at 06:00 and you hold two numbers: the incumbent's cost, and the smallest bound among the nodes still unexplored. The optimum lies between them. That interval is a *certificate* you can put in front of whoever has to sign off the plan: this plan costs C, and nothing cheaper than L exists, so we are at most C - L away from the best possible. A run that produces a plan but no such interval tells you nothing about how much money is still on the table.
- What happens if the bounding function is sometimes too optimistic, and what if it is sometimes too pessimistic?Too optimistic (for minimisation, a bound below the true subtree optimum) is safe but weak: it prunes less, so the run is slower. Too pessimistic is a correctness bug: a subtree containing the optimum is cut, and the search returns a worse plan while still reporting that it explored everything. Only one of the two errors is survivable.
- Why does seeding the incumbent with a quickly-computed feasible plan speed up the whole run?Pruning compares against the incumbent, so with no incumbent the first full descent prunes nothing. A seeded incumbent gives the comparison something to bite on from the root, cutting subtrees before the first leaf is even reached. The seed does not need to be good — only feasible and cheap to produce.
- What does the search hold at a deadline that lets you state how far from optimal you are?The incumbent's cost, and the smallest bound among nodes still unexplored. The optimum is between them, so the difference is a proven upper limit on how much you could still save. Without the second number you have a plan and no idea of its quality.
House hunting with an agreed maximum: once you learn that the cheapest possible house on a whole street is listed above what you have already agreed to pay elsewhere, you skip every viewing on that street without seeing one.
saying these in an interview costs you the question
- Calling branch and bound polynomial because pruning removes most nodes
- Using the incumbent's cost as the optimistic estimate for a subtree
- Letting the bound overshoot the subtree optimum to prune harder
- Claiming the plan held at a deadline is optimal with no bound to show
- Believing a tighter bound is always worth its extra cost per node
- Thinking pruning a tied subtree loses correctness rather than losing duplicate optima