Foundations — Branch and bound

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

"Branch and Bound" ek lamba naam hai, isliye aage hum ise B&B likhenge — yeh do letters sirf un do words ke liye hain. Is page par kuch bhi assume nahi kiya gaya. Parent note — woh main Branch and bound topic page jiske neeche yeh "Deep Dive" latak rahi hai (is vault mein, deep-dive pages kisi topic note ki children hoti hain) — tumhare saamne bohot saare symbols aur words phenk deta hai; unme se har ek yahan se ground up build kiya jayega, ek aisi sequence mein jahan har idea sirf pehle wale ideas par lean karta hai.

0. Woh picture jis par hum baar baar aate hain: ek decision tree

Kisi bhi symbol se pehle, humein woh shape chahiye jisme B&B rehta hai.

Yahan har optimization problem kuch yes/no (ya which-next) decisions ki ek sequence leke chalta hai. "Item A include karo ya nahi?" "Aage city 3 jaao ya city 5?" Har decision current situation ko kuch choti situations mein split kar deta hai. Start ke liye ek dot banao, har situation ke liye ek dot banao jahan decision le jaata hai, unhe connect karo — woh shape ek tree hai.

Figure s01 (neeche) exactly yahi dikhata hai: ise top-to-bottom padho. Bilkul upar ka single dot woh jagah hai jahan kuch bhi decide nahi hua; har neecha line ek decision hai; red dots aur red lines woh ek subtree mark karti hain jise B&B baad mein ek hi move mein phenk dega.

Yeh topic ko yeh picture kyun chahiye: B&B ki poori trick ek hi move mein ek poori subtree ko phenk dena hai. Tum "subtree cut off karo" tab tak nahi samajh sakte jab tak tum nahi dekh sakte subtree kya hai, aur tum decide nahi kar sakte kaunsi subtree cut karni hai jab tak tumne branch ka naam nahi rakha jo usme le jaati hai.

1. Optimization problem, objective, feasible

Yeh topic ko yeh kyun chahiye: "best" tab hi sense karta hai jab koi number ho compare karne ke liye. Woh number objective hai, aur poora page unhe compute kiye bina objective values compare karne ke baare mein hai.

2. Symbols $\le$, $\ge$ (har comparison ki language)

Yeh do symbols B&B mein saare decisions karte hain, toh ab bilkul literal ho jaate hain. (Hum abhi word "cut off" use kar rahe hain; precise prune rule — exactly kab ek subtree phenki jaati hai — section 8 mein build hogi, jab hamare paas compare karne ke liye "bound" aur "incumbent" honge.)

Figure s02 (neeche) dono symbols ko ek number line par pin karta hai. Red dot ek value $b=6$ mark karta hai; top black arrow har woh point sweep karta hai jo $a\le b$ satisfy karta hai (red dot ke left mein ya equal), bottom arrow har woh point sweep karta hai jo $a\ge b$ satisfy karta hai (right mein ya equal). Jab bhi parent note ek prune condition likhta hai, woh sirf pooch raha hai "hum red dot ke kis side hain?"

Tum parent note ko lower_bound(node) ≥ incumbent_cost (minimization) aur upper_bound(node) ≤ incumbent_value (maximization) likhte dekhoge. Dono same human sentence kehte hain: "is branch ka best possible result pehle se jo mere paas hai usse better nahi ho sakta." Hum "bound" aur "incumbent" agle sections mein earn karenge aur full rule section 8 mein assemble karenge — abhi ke liye, $\le /\ge$ sirf "line ke kis side" hai.

3. Objective value symbols: cost, profit, value, $W$, $c$

Parent note bahut saare one-letter names use karta hai. Yahan har ek hai, ek knapsack ke bhar jaane ki picture se joda hua.

Figure s03 (neeche) bag ko ek bar ke roop mein draw karta hai jiska total width $W=10$ hai. Black block woh weight $w$ hai jo is node par already commit ho chuka hai; red block woh hai jo bacha hai, remaining capacity $c=W-w$. Ek node feasible tab hi hai jab black block abhi bhi outline ke andar fit ho — yaani jab $w\le W$.

Subscript kyun matter karta hai: $v_i$ chote $i$ ke saath matlab hai "ek specific item ki value"; plain $p$ matlab hai "accumulated total value." Subscript ek item aur running sum ke beech ka fark hai. Inhe confuse karna parent note ka har formula galat padhne ka sabse tez rasta hai.

4. Sum symbol $\sum$

Parent note likhta hai ${\sum }_{j\text{ fit fully}}{v}_j$ aur $\frac{1}{2}{\sum }_{\text{city }i}(\dots )$. Agar $\sum$ tumhare liye naya hai, toh yeh raha bina kisi mystery ke.

5. Value-density $v_i/w_i$ — aur yahan division kyun

Parent note $v_i/w_i$ se sort karta hai. Division kyun aur subtraction $v_i-w_i$ kyun nahi?

6. Bound — asli star of the show

Ab baaki sab build ho gaya hai, hum sabse important word define kar sakte hain.

Figure s04 (neeche) poora judgement ek picture mein dikhata hai: dashed line woh champion score hai jo hum already rakhte hain; har bar ek branch ka optimistic bound hai. Chota grey bar dashed line tak nahi pahunch sakta → uski poori subtree phenk di jaati hai. Lamba red bar line se upar uthta hai → woh shayad kuch better chhupa raha ho, isliye hum use explore karte rehte hain.

Yeh exist kyun karta hai: bound ke bina, yeh jaanane ka ek hi tarika hai ki subtree hopeless hai — use poora explore karo — jo wahi brute force hai jise hum avoid karna chahte hain. Bound ek cheap over-estimate hai jo hume subtree ko khole bina reject karne deta hai.

Ek concrete bound: fractional-knapsack upper bound

Abstract "optimistic estimate" slippery hai, isliye yahan woh classic recipe hai jo ise ek actual number mein badal deti hai, sirf $\sum$ (section 4) aur value-density (section 5) use karke.

7. Incumbent

8. Prune rule, ab poori tarah readable

Section 2 ($\le /\ge$), section 6 (bound) aur section 7 (incumbent) ko ek saath rakho aur parent note ke rules khud decode ho jaate hain. Yeh woh definition hai jiska promise pehle sections ne kiya tha.

9. Live set aur uske data structures

Topic ko teen kyun chahiye: identical correctness, alag practical efficiency. Worst case exponential rehta hai regardless (dekho Big-O Notation); ordering typical speed ke baare mein hai, complexity guarantee nahi.

10. Relaxation — woh trick jo bound ko valid banati hai

Parent note ki dono derivations apna bound "relaxing" karke build karti hain. Ek clean definition:

Prerequisite map

Neeche ka diagram Mermaid mein likha gaya hai, flowcharts ke liye ek tiny text language. Ise aise padho: quotes mein har box ek concept hai; har arrow A --> B matlab "A ek prerequisite hai jo B mein feed karta hai." graph TD ka matlab sirf "ise top-down draw karo." Dekho ki ground-level ideas Branch and Bound mein kaise assemble hote hain arrows bottom-up follow karke.

Ise bottom-up padho: trees shape dete hain, objectives ek score deta hai, relaxation + density + sums bound build karte hain, bound plus incumbent aur $\le /\ge$ prune rule assemble karte hain, aur live set search order karta hai — sab Branch and Bound mein pour hota hua. Yahan se tum parent note ke 0-1 Knapsack aur Travelling Salesman Problem derivations ke liye ready ho, aur yeh dekhne ke liye ki B&B Backtracking, Greedy Algorithms, aur Dynamic Programming se kaise alag hai.

Equipment checklist

Right side cover karo; reveal karne se pehle jawaab zor se bolo.