Question bank — Branch and bound

TRUE. Agar bound pessimistic hota toh woh ek aisi subtree ko under-sell kar sakta tha jisme secretly true optimum chhupa ho, toh hum winner ko prune karke galat answer dete.

TRUE. Minimization mein bound ek lower bound (under-estimate) hota hai; agar sab se sasti possible completion bhi best full solution jaisi costly hai, toh wahan kuch behtar nahi milega.

FALSE. Maximization mein bound ek upper bound hota hai aur tum tab prune karte ho jab woh at most ($\le$) incumbent ho — woh subtree jiska best possible value jo tumhare paas pehle se hai use beat nahi kar sakta, woh hopeless hai.

FALSE. Worst case mein kuch bhi prune nahi hota, toh B&B $O(2^n)$ ya $O(n!)$ rehta hai — Big-O Notation dekho. Ye average/practical cases mein jeetता है, worst case mein nahi.

TRUE. Fractions allow karne se sirf zyada freedom milti hai, toh relaxed optimum constrained one se kabhi worse nahi ho sakta — yehi wajah hai ki ye ek valid upper bound hai.

TRUE. Backtracking sirf feasibility par prune karta hai (kya ye partial solution legal hai?); B&B ek cost/objective bound add karta hai taaki legal-but-hopeless branches bhi prune ho sakein.

FALSE. LC ek achha incumbent jaldi dhundh leta hai (better pruning), lekin har instance par zyada kam nodes expand karna guaranteed nahi hai, aur priority queue maintain karne ka per-step cost bhi zyada hota hai.

FALSE. Jab woh live set mein wait kar raha tha tab incumbent improve ho sakta hai, toh extraction par bound(node) ko incumbent ke against dobara test karna zaroori hai.

TRUE. Ek decision fix karne se freedom kam hoti hai, toh optimistic estimate sirf tighten hokar upar ja sakti hai — yehi baat deeper nodes ko prune karna aasaan banati hai.

FALSE. Tighter bound zyada prune karta hai lekin agar ise per node compute karna mehenga ho, toh total work badh sakta hai; useful bound woh hai jo best prune-per-cost trade-off ho, na ki sabse tight.

Jo heuristic guaranteed over-estimate nahi hai woh optimum wali branch ko prune kar sakti hai, aur galat answer de sakti hai — bound provably optimistic (relaxation-based) hona chahiye, sirf plausible nahi.

Ulta hai. Kam lower bound ka matlab hai ki subtree shayad incumbent ko beat kar sake, toh use rakhte hain; tab prune karte ho jab lower bound kam se kam ($\ge$) incumbent ho.

Nahi — incumbent sabse achhe complete, feasible solution ki value hai jo mili hai. Bounds incomplete nodes ke optimistic estimates hain; sirf realized full solutions hi incumbent ko update kar sakte hain.

Tumhe remaining items ko decreasing value-density ($v_i/w_i$, value ÷ weight) order mein add karna chahiye; woh greedy fill hi fractional value ko true upper bound banata hai. Arbitrary order ek chhota, invalid (non-optimistic) number deta hai.

Tumhe one half ($\frac{1}{2}$) se multiply karna hoga. Har edge dono endpoints se count hoti hai, toh raw sum har edge ko double-count karta hai aur over-estimate deta hai, lower-bound guarantee tod deta hai.

Aisa nahi hai. B&B ek smarter exhaustive search hai; NP-hard problems worst case mein exponential rehte hain — ye sirf provably-hopeless work ko avoid karta hai practice mein.

Greedy sirf fractional problem ke liye exact hai; 0-1 ke liye ye galat ho sakta hai, yehi wajah hai ki hume B&B (ya Dynamic Programming) ki zaroorat hai — greedy sirf bound supply karta hai, answer nahi.

Kyunki pruning is logic se kaam karta hai "yahan best case bhi bura hai, toh hata do." Ye sirf tab valid proof hai jab bound sach mein best case ko cap kare; pessimistic bound optimum ko discard kar sakta hai.

Kisi bhi tour mein har city ki exactly ek edge enter karti hai aur ek leave karti hai, toh woh kam se kam apni do sabse sasti incident edges contribute karta hai — ek use karna under-count hoga aur genuine minimum nahi dega.

Incumbent tab improve ho sakta hai jab node queue mein wait kar raha ho, ek promising node ko prunable bana deta hai; stale nodes ko skip karna un subtrees ko expand karne se bachata hai jo ab hopeless jaane ja chuke hain.

Ye sabse promising region ki taraf pehle dive karta hai, toh ek strong incumbent jaldi discover ho jaata hai; strong incumbent ek tighter pruning threshold hai, baki zyada tree ko khatam karta hai.

Feasibility ko prune karne ke liye sirf "kya ye legal hai?" test chahiye, lekin best dhundhne ke liye ek cost threshold ke against compare karna padta hai — bound — jo backtracking akela provide nahi karta.

Ek bound allowed choices ke ek set par best completion ke roop mein compute hota hai. Ek decision fix karna us allowed set ko shrink karta hai, aur ek chhote set par maximum (ya minimum) kabhi bhi bade set se zyada optimistic nahi ho sakta — mathematically bound sirf tumhare against move kar sakta hai (min ke liye upar, max ke liye neeche), tumhare favour mein nahi.

Correctness sirf pruning invariant par depend karti hai "koi node mat hatao jiska optimistic bound abhi bhi incumbent ko beat kar sake." Tie-breaking sirf nodes ke expand hone ka order reorder karta hai, kya woh test pass karte hain ye nahi, toh same set of non-prunable nodes eventually process hote hain chahe order kuch bhi ho — sirf running speed change hoti hai.

Tightness node count kam karti hai lekin aksar bound compute karne ka per-node cost badha deti hai; total time nodes $\times$ cost-per-node hai, toh zyada expensive bound tumhe slow kar sakta hai.

Ye $+\infty$ se start hota hai (plus infinity, ek "impossibly large" cost; maximization ke liye $-\infty$) taaki pehla complete feasible solution hamesha ise improve kare — koi valid solution "kuch nahi se better nahi" kehkar reject nahi hona chahiye.

Tum safely prune kar sakte ho: barabar bound ka matlab hai woh best case mein sirf current best ke saath tie kar sakta hai, toh explore karne se strictly better optimum nahi milega (koi bhi tie pehle se achieve ho chuka hai).

Nahi — woh incumbent ban jaata hai, lekin B&B ko phir bhi remaining live nodes ko expand ya bound-prune karna hota hai taaki prove ho sake ki kuch use beat nahi kar sakta; optimality sirf tab confirm hoti hai jab live set khatam ho jaaye.

B&B poori tree par full brute force mein degenerate ho jaata hai, worst-case $O(2^n)$ ya $O(n!)$ behaviour deta hai — pruning ek optimization hai, guarantee nahi.

Items ki count mein near-linear hoti hai jab ek strong incumbent turant appear ho (jaise pehla greedy dive optimal ho), kyunki almost har sibling branch ek bound comparison se prune ho jaati hai — tree essentially ek root-to-leaf path aur uske pruned stubs tak collapse ho jaata hai.

Real instances par B&B aksar $2^n$ ya $n!$ tree ka bahut chhota fraction explore karta hai kyunki achhe bounds aur achha incumbent jaldi prune karte hain; fayda empirical average-case speed hai, better asymptotic class nahi.

FIFO/best-first (Least-Cost) B&B ek time mein exponentially many live nodes (poora frontier) hold kar sakta hai, bahut zyada memory lagti hai, jabki LIFO/DFS B&B sirf current root-to-node path aur uske siblings rakhta hai — roughly $O(n)$ depth — kam memory ke liye possibly weaker early pruning ka trade-off karta hai.

Koi overflow item nahi hogi jiska fraction lena pade, toh bound sirf decided profit plus saare remaining items ki full value hai — fractional aur integer completions wahan coincide karte hain.

Koi bhi choose kiya ja sakta hai; correctness affect nahi hoti kyunki dono optimistic hain aur abhi bhi bounded/expanded honge — sirf tie-break order, aur isliye speed, differ karti hai.