Branch and bound
WHAT it is
- Incumbent: best feasible complete solution known right now. Its value is the current best.
- Bound: a guaranteed-not-beatable-by-this-subtree value.
- For minimization: prune a node if
lower_bound(node) ≥ incumbent_cost. - For maximization: prune a node if
upper_bound(node) ≤ incumbent_value.
HOW it works (the algorithm)
We keep a live set of unexplored nodes. The order we pick from it defines the strategy:
| Strategy | Data structure | Picks next |
|---|---|---|
| FIFO B&B (BFS) | Queue | oldest node |
| LIFO B&B (DFS) | Stack | newest node |
| Least-Cost (LC) B&B | Priority queue | node with best bound |
function BranchAndBound(root):
incumbent = +inf # for minimization
bestSolution = none
live = priority_queue([root])
while live not empty:
node = live.extract_best() # best bound first (LC)
if bound(node) >= incumbent: # stale node, prune
continue
for child in expand(node):
if isComplete(child):
if cost(child) < incumbent:
incumbent = cost(child); bestSolution = child
elif bound(child) < incumbent: # promising → keep
live.insert(child)
# else: pruned, never inserted
return bestSolution, incumbent
DERIVATION: a correct bound for 0/1 Knapsack
We want max total value with total weight . WHY we even need a bound: to decide which partial item-selections are hopeless.
Step 1 — Relax the problem. The hard constraint is "items are 0 or 1 (indivisible)." Drop it: allow fractions of items. Why this step? The fractional problem is easier and its optimum is always the integer optimum (more freedom ⇒ never worse). So fractional value is a valid upper bound.
Step 2 — Solve the relaxation greedily. Sort items by value-density descending. Fill the remaining capacity, taking whole items until one doesn't fit, then a fraction of that one. Why this step? The fractional knapsack optimum is exactly this greedy — proven by exchange argument.
Step 3 — Bound for a partial node. At a node we've already decided some items (profit , weight used). The bound is:
Worked example 2: Travelling Salesman lower bound (minimization)
WHY: TSP is minimization, so we need a lower bound (under-estimate of any completing tour).
Derive the bound. Every city in a tour has exactly one edge entering and one leaving. So each city contributes at least its two smallest incident edges to the tour.
Common mistakes
Recall Feynman: explain to a 12-year-old
You're hunting for the cheapest way to visit all your friends' houses. Instead of trying every single route (boring, takes forever), you say: "If I've already found a route that costs ₹100, and I can prove this half-finished route will cost at least ₹120 no matter what, I won't bother finishing it." You throw away big chunks of bad routes by guessing their best possible score and seeing it's still too bad. That guessing-and-throwing-away is branch and bound.
Flashcards
What two ingredients does Branch and Bound add over plain exhaustive search?
For a minimization problem, when do you prune a node?
For a maximization problem, when do you prune a node?
Why must the bound be optimistic (over-estimate for max, under-estimate for min)?
What is the "incumbent"?
Difference between Branch and Bound and Backtracking?
What's the difference between FIFO, LIFO, and LC branch and bound?
How do you get a valid upper bound for 0/1 knapsack at a node?
How do you get a lower bound for TSP?
Is B&B better than brute force in the worst case?
Why re-check the bound when extracting a node from the live set?
Why does forcing/forbidding an edge in TSP only raise the lower bound?
Connections
- Backtracking — B&B = backtracking + cost bounds.
- Greedy Algorithms — fractional knapsack greedy supplies the knapsack bound.
- Dynamic Programming — alternative exact method; B&B prunes instead of memoizing.
- 0-1 Knapsack — canonical B&B application.
- Travelling Salesman Problem — classic LC-B&B with reduced-cost bounds.
- A* Search — LC-B&B with an admissible heuristic is A*; the heuristic is the bound.
- Big-O Notation — why worst case stays exponential.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Branch and Bound ek smart searching technique hai jab humein best answer chahiye — jaise sabse sasta TSP route ya max value wala knapsack. Brute force mein hum saari possibilities try karte hain jo bahut slow hai. B&B kehta hai: pehle har branch ka ek optimistic estimate (bound) nikaalo — yaani "is branch mein best se best kitna acha ho sakta hai?". Agar wo best-case bhi already mile hue answer (incumbent) se kharab hai, to poora branch udaa do bina explore kiye. Isi ko pruning kehte hain.
Yaad rakhne wali baat: bound hamesha optimistic hona chahiye. Maximization mein upper bound chahiye aur prune karo jab upper bound ≤ incumbent. Minimization mein lower bound chahiye aur prune karo jab lower bound ≥ incumbent. Agar bound galat direction ka use kiya to sahi answer wala branch bhi kat sakta hai — wrong answer! Isiliye bound ko hum problem ko relax karke nikaalte hain (jaise knapsack mein fractions allow karna), kyunki easy problem ka optimum hamesha valid estimate deta hai.
Knapsack mein bound nikalne ka tarika: items ko value/weight density se sort karo, bachi capacity ko greedily bharo, last item ka fraction le lo — ye fractional value ek valid upper bound hai. TSP mein har city ke do sabse saste edges add karke /2 karne se lower bound milta hai. Strategy: LC (Least-Cost) B&B priority queue use karta hai jo sabse acha bound wala node pehle nikaalta hai — yahi A* search ka core idea hai.
Ek important warning: B&B ka worst case abhi bhi exponential hai. Pruning se practical speed milti hai, magic polynomial solution nahi. Aur ek node ko queue se nikalte waqt bound dobara check karo, kyunki incumbent beech mein improve ho sakta hai. Mantra yaad rakho: "Bound is the dream, incumbent is the deal — agar dream bhi deal ko beat na kare, drop it."