Branch and bound: Visual walkthrough — Hinglish deep dive

3.7.18 · D2 · Coding › Algorithm Paradigms › Branch and bound

Step 1 — Hum choose kya kar rahe hain? Items draw karo

KYA. Hamare paas ek knapsack (ek bag) hai jo zyada se zyada kuch total weight hold kar sakta hai, jise $W$ kehte hain ("capacity"). Hamare paas items hain. Har item $i$ ke paas do numbers hain: ek value $v_{i}$ (ise lene se kitna gain hoga) aur ek weight $w_{i}$ (yeh bag-space kitni khaata hai). Har item ke liye hum ek yes/no decision lete hain: lo ise (use $1$ kaho) ya chhod do (use $0$ kaho). Yahi "0 ya 1, kuch beech mein nahi" wali baat hai kyun ise 0-1 knapsack kehte hain.

PEHLE DRAW KYUN. Kisi bhi formula se pehle, hume dekhna chahiye ki ek "solution" kya hai: items ka ek subset jiska total weight $W$ mein fit ho, aur hum woh subset chahte hain jiska total value sabse zyada ho. Iske baad sab kuch machinery hai us subset ko dhundhne ke liye bina saare $2^{n}$ try kiye.

PICTURE. Char boxes. Har box ki height uski value hai, uski width uska weight hai. Bag ek shelf hai jiska width $W$ hai.

Hum parent se running example use karte hain: $W = 10$ aur items $A (v = 40, w = 2)$ , $B (30, 5)$ , $C (50, 10)$ , $D (10, 5)$ .

Step 2 — "Value per kilo": kyun density hi key ruler hai

KYA. Har item ke liye uski value-density compute karo $\frac{v _{i}}{w _{i}}$ — value divided by weight. Yeh jawab deta hai: "bag-space ki per unit, yeh item kitna reward deta hai?"

YEH TOOL KYUN, raw value kyun nahi? Bag-space scarce resource hai. Item $C$ ki value sabse badi hai ( $50$ ) lekin poora bag khaata hai ( $w = 10$ ). Item $A$ sirf $2$ ke liye $40$ deta hai — yeh $20$ per kilo hai. Agar space hi haari limit hai, toh rate $v_{i} / w_{i}$ batata hai konsa item best per kilo pay karta hai, na ki konsa item overall sabse bada hai. Is rate se sort karna woh ruler hai jo greedy filling ko optimal banata hai (Step 4).

PICTURE. Wahi boxes, ab apne slope $v_{i} / w_{i}$ ke saath labelled, tallest-rate pehle sorted.

Densities: $ρ_{A} = 40/2 = 20$ , $ρ_{B} = 30/5 = 6$ , $ρ_{C} = 50/10 = 5$ , $ρ_{D} = 10/5 = 2$ . Sorted order: $A, B, C, D$ .

Step 3 — Trick: fractions allow karo taaki problem easy ho jaaye

KYA. Hard rule hai "har item all-or-nothing hai." Hum ise relax karte hain: pretend karo ki hum kisi item ka koi bhi fraction le sakte hain — $C$ ka aadha, $B$ ka teesra hissa. Yeh ek alag, easier problem hai jise fractional knapsack kehte hain.

RELAX KYUN? Ek relaxation ek constraint hatata hai, isliye woh zyada freedom deta hai. Zyada freedom best-possible value ko kabhi chhota nahi kar sakti — worst case mein tum bas fractions use nahi karte. Isliye: $best fractional value \geq best 0-1 value .$ Yahi inequality poori baat hai: easy answer upar baith ta hai hard answer se, isliye yeh ek valid over-estimate hai — exactly wahi jo maximization bound ko hona chahiye.

PICTURE. Left bar 0-1 world dikhata hai (sirf whole boxes). Right bar fractional world dikhata hai jahan last item ko bag exactly fill karne ke liye slice kiya gaya hai. Fractional stack kam se kam utna hi tall hai.

Step 4 — Greedily fill karo aur last item slice karo

KYA. Fractional problem solve karo: items mein density order ( $A, B, C, \dots$ ) mein jaao, har ek ko whole lo jab tak fit hota hai, aur jab agla item overflow kare, exactly woh fraction lo jo bacha hua space fill kare.

GREEDY YAHAN EXACTLY OPTIMAL KYUN HAI. Kyunki space hi ek limit hai aur fractions allowed hain, agla kilo highest-density item pe spend karna jo fit hota ho hamesha best hai — koi bhi kilo lower-density item pe swap karna sirf value khoata (ek exchange argument). Yeh un kuch jagahon mein se ek hai jahan greedy choice provably optimal hoti hai. (Whole-item 0-1 problem ke liye greedy optimal nahi hai — isliye hume abhi bhi search chahiye.)

PICTURE. Width- $10$ shelf ko left to right bharo: $A$ (width 2), $B$ (width 5) — total 7 use hua, 3 baaqi — phir $C$ ka 3/10 slice amber mein shade kiya gaya aakhri 3 units fill karne ke liye.

Root pe numbers (abhi kuch decide nahi hua):

$A$ fully lo: value $+ 40$ , weight used $2$ .
$B$ fully lo: value $+ 30$ , weight used $7$ .
$C$ ko $10$ chahiye lekin sirf $3$ bacha hai: $C$ ka $\frac{3}{10}$ lo → $+ \frac{3}{10} \cdot 50 = 15$ .
Root bound $= 40 + 30 + 15 = 85$ .

Step 5 — Bound ek partial node pe (kuch items already decide ho gaye)

KYA. Search mein gehrai mein hum pehle se kuch items commit kar chuke hain. Ab tak locked in value ko $p$ (profit) kaho aur pehle se spent weight ko $w$ . Bacha hua space $c = W - w$ hai. Bound = jo hum lock kar chuke hain plus still-undecided items ka fractional fill $c$ mein.

IS TARAH SPLIT KYUN. $p$ pehle se real value hai jo hamare paas hai — wahan koi optimism nahi. Uncertainty sirf undecided items ke baare mein hai, isliye hum optimistic fractional fill sirf unhe apply karte hain, leftover capacity $c$ mein. Locked part honest hai; future part optimistic hai; sum ek valid over-estimate hai.

PICTURE. Ek tank do zones mein split: ek solid cyan zone height $p$ ka (already-decided, capacity $w$ consumed), aur ek amber "optimistic completion" remaining capacity $c$ mein pour ki gayi.

Step 6 — Branch: "include" vs "exclude" mein split karo

KYA. Agla undecided item pick karo (pehle highest density, isliye $A$ ) aur do children banao: ek jahan hum ise include karte hain, ek jahan hum ise exclude karte hain. Har node Step 5 se apna bound compute karta hai.

HIGHEST DENSITY PE BRANCH KYUN? Woh item bound ko sabse zyada shape karta hai, isliye use pehle decide karna ek strong branch aur ek weak branch ke beech sabse sharp split deta hai, jisse hume jaldi ek acha incumbent milta hai (jo zyada pruning powers karta hai). Yeh yes/no splitting backtracking tree hai — B&B sirf bound add karta hai.

PICTURE. Root Include A (bound 85) aur Exclude A (bound 55) mein split hota hai.

Include A: $p = 40$ , $w = 2$ . Baaki fill karo: $B$ full ( $+ 30$ ), $C$ slice $\frac{3}{10} \cdot 50 = 15$ → bound $= 85$ .
Exclude A: $p = 0$ , $w = 0$ . Baaki fill karo: $B$ full ( $+ 30$ ), phir $C$ slice $\frac{5}{10} \cdot 50 = 25$ (B ke baad 5 baacha) → bound $= 55$ .

Step 7 — Prune: ek comparison ek poora subtree maar deta hai

KYA. Hum sabse promising node (Least-Cost: best bound first) expand karte rehte hain. Include- $A$ side eventually ek complete solution ${A, B}$ value $70$ ke saath deta hai. Incumbent $= 70$ set karo. Ab Exclude A revisit karo: iska bound $55$ hai.

YEH KYUN MARTA HAI. $55 \leq 70$ matlab Exclude-A ke neeche kahin bhi best possible result $55$ hai, jo pehle se haath mein $70$ ko beat nahi kar sakta. Hum woh poora subtree ek bhi explore kiye bina delete kar dete hain — yeh ek proof hai, guess nahi. Yahi pruning hai.

PICTURE. Tree jisme Exclude-A amber mein struck out hai, labelled "bound $55 \leq$ incumbent $70$ → PRUNED"; ${A, B}$ tak surviving path cyan mein glow kar raha hai.

Step 8 — Degenerate & edge cases (reader ko kabhi stranded mat chhodna)

KYA & KYUN, case by case:

Ek item bag se bhaari ( $w_{i} > W$ ). Ise kabhi whole include nahi kiya ja sakta; fractional bound mein yeh abhi bhi ek slice contribute kar sakta hai. Theek hai — bound ko optimistic hone ki permission hai; 0-1 branches simply ise kabhi nahi lete.
Capacity exactly use hua, $c = 0$ . Koi fraction add nahi hota; bound $= p + \sum (decided whole)$ . Step 5 ka sum empty hai — yeh ek valid (tight) bound hai, koi error nahi.
Saare items fit ho jaate hain ( $\sum w_{i} \leq W$ ). Bound sab kuch ki total value ke barabar hai; optimum hai "sab lo". Koi pruning needed nahi, lekin machinery phir bhi sahi answer return karta hai.
Zero-weight item ( $w_{i} = 0$ ). Density $v_{i} / w_{i}$ undefined hai (divide by zero). Rule: positive-value zero-weight item hamesha pehle liya jaata hai — space cost nahi karta. Sort karne se pehle handle karo.
Density mein ties. Equal- $ρ$ items ke beech order bound ki value affect nahi karta, sirf tree shape ko. Koi bhi tie-break sahi hai.

PICTURE. In chaar situations ka 2×2 grid, har ek ek mini bar jisme dikhaya gaya hai ki bound kya karta hai.

Recall Kis problem ke liye kaunsa sign?

Knapsack maximize karta hai ::: ek upper bound use karo; prune karo jab $UB \leq incumbent$ . TSP minimize karta hai ::: ek lower bound use karo; prune karo jab $LB \geq incumbent$ . Ek line mein rule ::: "bound = is subtree mein best possible; prune karo jab best-possible jo mere paas hai use beat nahi kar sakta."

Ek-picture summary

Upar sab kuch, compressed: relax karo → greedily fill karo → woh height bound hai → branch karo → jo kuch bound incumbent ke upar lift nahi kar sakta use prune karo.

Recall Poore walkthrough ki Feynman retelling

Tumhare paas ek bag hai aur kuch khazane hain, har ek ki ek worth aur ek weight hai. Tum woh sabse ameer haul chahte ho jo fit kare. Har combination try karna forever le leta hai, isliye tum ek smarter game khelate ho. Pehle tum khazanon ko worth-per-kilo se rank karte ho — best deals. Phir tum daydream karte ho: "Kya hoga agar mein aadha khazana le sakta?" Us easy fantasy mein tum bas best-per-kilo items grab karte ho aur aakhre wale ko exactly bag fill karne ke liye slice karte ho. Woh fantasy total hamesha kam se kam real answer ke barabar hota hai, isliye yeh ek safe ceiling hai — bound. Ab tum actually decide karte ho, item by item, "lo ya chhoddo," choices ka ek tree banate hue. Kisi bhi half-made choice pe tum baaki ke liye ceiling recompute karte ho. Jis moment kisi branch ki ceiling ek real haul se uunchi nahi hoti jo tum pehle se bag kar chuke ho, tum jaante ho woh branch hopeless hai aur tum poori cheez ek comparison se throw karte ho — kholne ki zaroorat nahi. Tab tak chalte raho jab tak sirf real solutions bachein; best wala jeetta hai. Yahi Branch and Bound hai: ek honest ceiling daydream karo, phir har woh branch discard karo jo us floor tak nahi pahunch sakta jis par tum pehle se khade ho.

Recall One-line takeaways

Max ke liye bound over-estimate hona chahiye kyunki ::: ek over-estimate "even the best case too low hai" ko ek valid proof banata hai, isliye pruning kabhi true optimum delete nahi karta. Fractional knapsack bound ke roop mein use hota hai kyunki ::: yeh ek easy relaxation hai jiska optimum $\geq$ 0-1 optimum hai, ek valid, computable ceiling deta hai. Greedy fractional problem ke liye optimal hai lekin 0-1 problem ke liye nahi kyunki ::: fractions tumhe hamesha agla kilo highest density pe spend karne deta hai; whole items nahi de sakte, isliye 0-1 ko abhi bhi search tree chahiye.

Dekho bhi: Dynamic Programming (knapsack ke liye ek exact alternative), A* Search (graph mein search guide karte bounds), Big-O Notation (worst case exponential rehta hai).