Exercises — Branch and bound

Answer: (b). B&B optimization problems solve karta hai — woh jo bahut saari feasible options mein se best (sabse sasta / sabse valuable) dhundhte hain. (a) ek find-all task hai jo Backtracking ke liye suitable hai; (c) ek decision/computation hai, ek search tree par optimization nahi.

Prune. Is subtree ka best possible result $48$ hai, jo $\le 52$ hai, woh value jo hum already hold karte hain. Rule: max → prune when $UB\le \text{incumbent}$. $48\le 52$ ✅ toh poora subtree hopeless hai. Iske andar koi bhi path jo hum already hold karte hain use beat nahi kar sakta.

• FIFO B&B (breadth-first) → queue (sabse purana node pick karo).
• LIFO B&B (depth-first) → stack (sabse naya node pick karo).
• Least-Cost (LC) B&B → priority queue (pehle best bound wala node pick karo).

Prune. Rule: min → prune when $LB\ge \text{incumbent}$. Yahan $30\ge 30$ true hai. Best case mein bhi yeh subtree current best se tie karega — yeh strictly improve nahi kar sakta, toh hum ise discard karte hain. ($\ge$ use karna $>$ ki jagah ek valid choice hai: ties ko rakhna sirf kaam barbaad karta hai.)

Step 1 — densities $v/w$: A $=20$, B $=6$, C $=5$, D $=2$. Order: A, B, C, D. Step 2 — fill capacity $10$:

• A fully lo: profit $p=40$, weight used $w=2$, capacity left $c=8$.
• B fully lo: profit $p=70$, weight used $w=7$, capacity left $c=3$.
• C (weight $10$) tak pahuncho lekin sirf $3$ fit hoga → fraction $\frac{3}{10}\cdot 50=15$.

$UB=40+30+15=\boxed{85}.$ Yeh true integer optimum ka ek over-estimate hai kyunki hum ne item C ko slice karke cheat kiya. Dekho 0-1 Knapsack.

Neeche ka figure chaar cities ko blue circles ki tarah draw karta hai aur har edge ko uski cost se label karta hai. Green solid edges woh hain jo kisi city ke "two cheapest" ke roop mein chosen hain; gray dashed edges (yahan $2-3$, cost $35$) kisi bhi city ke two cheapest mein kabhi nahi hote, toh woh is bound mein contribute nahi karte. Har vertex ke do sabse saste incident edges padhna:

• City 1: edges $10,15$ → sum $25$
• City 2: edges $10,25$ → sum $35$
• City 3: edges $15,30$ → sum $45$
• City 4: edges $20,25$ → sum $45$

Total $=25+35+45+45=150$. Halve karo (figure mein har edge dono endpoints se count hua tha): $LB=\frac{1}{2}\cdot 150=\boxed{75}.$ Koi bhi real tour kam se kam $75$ zaroor cost karega — pruning ke liye ek valid floor.

Maximization → prune when $UB\le 70$.

• $85>70$ → keep.
• $55\le 70$ → prune.
• $68\le 70$ → prune.
• $70\le 70$ → prune (ties incumbent ko strictly beat nahi kar saktein).

Toh teen nodes mar jaate hain, ek survive karta hai. Yahi payoff hai: har prune ek single comparison se pura subtree erase kar deta hai.

$2-3$ force karne ka matlab hai ki cities 2 aur 3 dono ko apne do tour edges mein edge cost $35$ use karna hi hoga.

• City 2: $35$ include karna zaroori hai; sabse sasta doosra edge $10$ ($c_{12}$) hai. Sum $=35+10=45$ (pehle $35$ tha).
• City 3: $35$ include karna zaroori hai; sabse sasta doosra edge $15$ ($c_{13}$) hai. Sum $=35+15=50$ (pehle $45$ tha).
• Cities 1 aur 4 unchanged: $25$ aur $45$.

Total $=25+45+50+45=165$; halve → $LB=82.5$. Direction: yeh $75$ se $82.5$ tak badh gaya. Ek edge force karna freedom remove karta hai, toh sabse sasta legal completion sirf aur mehenga ho sakta hai. Ek tighter (higher) lower bound aur aggressively prune karta hai — exactly wahi jo hum deeper jaate waqt chahte hain.

Bound $75$ wala node expand karo — sabse chota (best/most-promising) lower bound. LC-B&B hamesha us branch mein dive karta hai jiska optimistic estimate sabse best ho, kyunki woh true optimum contain karne aur jaldi ek strong incumbent produce karne ki sabse zyada possibility rakhta hai. Ek strong incumbent early aane se hum baaki nodes ($88,91,80$) ko jaldi prune kar sakte hain. FIFO blindly woh expand karta jo pehle enter hua, possibly $91$-bound branch par effort waste karte hue.

Densities: X $=10$, Y $=10$, Z $=6$. Order X, Y, Z. Tie-break rule: X aur Y ki equal density $10$ hai. Jab densities tie hoti hain, fractional relaxation value order se unaffected hoti hai — same total capacity same per-unit value se fill hoti hai chahe hum pehle kaun sa list karein, toh bound identical hota hai. Hum simply ek deterministic rule fix karte hain (e.g. lower item weight first, ya by input order) taaki trace reproducible ho; yahan hum input order ke hisaab se X before Y rakhte hain. Yeh choice sirf yeh affect karta hai ki hum pehle kaun se node par branch karte hain, kabhi correctness ya bound value nahi.

Root bound (capacity $6$ fill karo, $p,w,c$ use karke): X full ($p=30,w=3,c=3$); Y full ($p=50,w=5,c=1$); Z ko $4$ chahiye, fraction $\frac{1}{4}\cdot 24=6$. $UB=30+20+6=56$. Incumbent $=0$.

Branch on X.

• Include X ($p=30,w=3,c=3$): Y full ($p=50,w=5,c=1$); Z frac $\frac{1}{4}\cdot 24=6$. $UB=30+20+6=56$.
• Exclude X ($p=0,w=0,c=6$): Y full ($p=20,w=2,c=4$); Z full ($p=44,w=6,c=0$). $UB=44$ (already integer — ek complete candidate!). Incumbent $\to 44$ with $\{Y,Z\}$.

Expand include-X (bound $56>44$, promising). Branch on Y:

• Include Y ($p=50,w=5,c=1$): Z ko $4$ chahiye lekin $c=1$, fit nahi hoga → Z exclude force karo → complete solution $\{X,Y\}$ value $50$. Incumbent $\to 50$.
• Exclude Y ($p=30,w=3,c=3$): Z ko $4$ chahiye, $c=3$, fit nahi hoga → complete $\{X\}$ value $30\le 50$, no update.

Baaki saare live nodes ke $UB\le 50$ hain aur prune ho jaate hain. $\text{Optimal value}=\boxed{50},\text{set }\{X,Y\}.$ (Brute force se confirm karo: $\{X,Y\}=50$ w=5 ✅; $\{X,Z\}$ w=7 ✗; $\{Y,Z\}=44$; $\{X\}=30$. Max feasible $=50$.)

$S$ = sabhi jobs ka total processing time, aur $m$ = heavier machine par already placed current load. $t_j$ job $j$ ka processing time hai, toh ${\max }_j{t}_j$ sabse lamba single job ka time hai. Final makespan par ek valid lower bound hai: $LB=\max (m,\lceil \frac{S}{2}\rceil ,{\max }_j{t}_j)$ Valid kyun hai (under-estimate):

• Makespan $\ge m$: ek machine already $m$ carry karti hai; jobs add karna load kabhi remove nahi karta.
• Makespan $\ge \lceil S/2\rceil$: even ek perfectly balanced split mein ek machine ko kam se kam aadha total milta hai.
• Makespan $\ge {\max }_j{t}_j$: kisi machine ko sabse lamba single job ek uninterrupted chunk mein run karna hi hoga.

Har ek ek floor hai jiske neeche kuch nahi ja sakta, toh floors ka max abhi bhi ek floor hai — ek legitimate lower bound. Yeh ek relaxation hai: hum ek easy, optimistic estimate pane ke liye integrality/assignment constraints ignore karte hain (same trick jaise fractional 0-1 Knapsack bound). Compare karo ki Greedy Algorithms aur Dynamic Programming ise exactly solve karne ke liye kya karte.

False. Pruning tabhi kaam remove karta hai jab ek node ka bound prove kare ki woh hopeless hai. Worst case mein, kuch bhi prune nahi hota — incumbent kabhi itna achha nahi hota itni jaldi, aur B&B (asymptotically) poora tree expand kar leta hai. TSP ke liye us tree mein $O(n!)$ leaves hote hain; knapsack ke liye $O(2^n)$. Toh worst-case complexity unchanged hai — abhi bhi exponential. B&B average/practical running time ko pruning ke zariye improve karta hai, worst-case big-O ko nahi. Yeh ek smarter exhaustive search hai, kabhi polynomial-time trick nahi. (Agar yeh TSP ke liye guaranteed polynomial method hota, toh P vs NP resolve ho jaata — ek hint ki claim sahi nahi ho sakta.)

Bug: yeh "bound" valid upper bound nahi hai. Sirf ek remaining item add karna true best completion ko under-estimate kar sakta hai, kyunki ek real integer completion kai remaining items pack kar sakti hai jinki combined value kisi bhi single item se kaafi zyada ho. Ek valid maximization bound har completion ka over-estimate hona chahiye; yeh quantity kuch completions se neeche ho sakti hai, toh yeh definition fail karti hai. Galat answer kyun aata hai: kyunki "bound" bahut chota ho sakta hai, test $UB\le \text{incumbent}$ us node par fire ho sakta hai jiske real completions actually incumbent ko beat karte hain. Woh node — aur uska poora subtree, jisme true optimum ho sakta hai — wrongly prune ho jaata hai, toh algorithm true max se neeche value return karta hai. Yeh exactly reported symptom se match karta hai. Concrete counterexample (proof ki yeh under-estimate karta hai): maan lo kisi node par $p=5$ hai aur remaining capacity $c=4$ hai, remaining items P(10, 2) aur Q(10, 2) ke saath.

• True best completion: dono P aur Q lo (total weight $4\le c$) → completion value $10+10=20$, toh node ki real reachable value $5+20=25$ hai.
• Buggy bound: $p+(\text{single most-valuable item that fits})=5+10=15$.

Kyunki $15<25$, bound genuinely ek integer completion se strictly neeche hai — yeh upper bound nahi hai. Agar incumbent, $18$ hota, toh buggy test $15\le 18$ is node ko prune kar deta even though yeh $25>18$ tak pahunchta hai. Optimum kho jaata hai. ∎ Fix: 0-1 Knapsack ka fractional relaxation bound use karo — density-sorted greedy fill jisme overflow item ka fraction shamil ho — jo provably $\ge$ har integer completion hota hai. Counterexample mein yeh $5+10+10=25$ deta hai (dono exactly fit hote hain), correctly $\ge 25$, toh node prune nahi hota. Ek valid bound optimistic hona chahiye: maximization ke liye over-estimate.

Ab objective maximization hai, toh:

• Bound type: ek upper bound (optimistic = ek completion sabse zyada cost tak pahunch sakti hai).
• Prune test: ek node discard karo jab $UB\le \text{incumbent}$ (incumbent = abhi tak ka best complete scenic tour).
• Bound build karna: 2-min idea mirror karo lekin har city ke do sabse mehenga incident edges lo aur halve karo: $UB=\frac{1}{2}{\sum }_{\text{city }i}(\text{two most expensive edges at }i).$ Yeh valid over-estimate kyun hai: har real tour mein har city ke exactly do incident edges hote hain (ek in, ek out). Kisi city ke liye, woh do edges uske do sabse mehenga incident edges se zyada cost nahi kar sakti — tum available sabse mehenga se bhi mehenga edge nahi pick kar sakte. Woh per-city maximum ko sabhi cities par sum karna har tour edge ko do baar count karta hai (ek baar har endpoint par), toh halving ek aise quantity ko recover karta hai jo kisi bhi real tour ki cost se $\ge$ hai. Isliye $UB$ ek legitimate ceiling hai: koi completion ise exceed nahi kar sakti, exactly woh optimism jo ek maximization bound ko chahiye. Tour mein ek edge force karna is bound ko sirf lower kar sakta hai (woh us city ke pricier edge choose karne ki freedom remove karta hai), descend karte waqt pruning tight hoti hai. Core loop A* Search-style best-first expansion ke identical hai — sirf inequalities ki direction aur "best" edge choice flip hoti hai. Travelling Salesman Problem ke standard minimizing version se compare karo.

Woh single question jo upar ki har problem unlock karta hai ::: "Kya mera bound ek proven best-case hai (max ke liye over-estimate, min ke liye under-estimate), aur kya mein sirf tabhi prune kar raha hoon jab woh best-case jo mein already hold karta hoon use beat nahi kar sakta?"