Branch and bound — Hinglish notes

3.7.18 · Coding › Algorithm Paradigms

WHAT it is

Incumbent: abhi is waqt jaani hui best feasible complete solution. Iska value hi current best hai.
Bound: ek guaranteed-not-beatable-by-this-subtree value.
Minimization ke liye: ek node ko prune karo agar lower_bound(node) ≥ incumbent_cost.
Maximization ke liye: ek node ko prune karo agar upper_bound(node) ≤ incumbent_value.

HOW it works (the algorithm)

Hum unexplored nodes ka ek live set rakhte hain. Jis order mein hum us se pick karte hain woh strategy define karta hai:

Strategy	Data structure	Picks next
FIFO B&B (BFS)	Queue	sabse purana node
LIFO B&B (DFS)	Stack	sabse naya node
Least-Cost (LC) B&B	Priority queue	node jiska best bound ho

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

Hum max total value chahte hain with total weight $\leq W$ . WHY hume bound ki zaroorat hai: decide karne ke liye ki kaunse partial item-selections hopeless hain.

Step 1 — Relax the problem. Hard constraint hai "items 0 ya 1 hain (indivisible)." Use drop karo: fractions of items allow karo. Why this step? Fractional problem easier hai aur iska optimum hamesha $\geq$ integer optimum hota hai (zyada freedom ⇒ kabhi worse nahi). Toh fractional value ek valid upper bound hai.

Step 2 — Solve the relaxation greedily. Items ko value-density $v_{i} / w_{i}$ descending order mein sort karo. Remaining capacity fill karo, whole items lete jao jab tak koi fit na ho, phir us ek ka fraction lo. Why this step? Fractional knapsack optimum exactly yahi greedy approach hai — exchange argument se proven.

Step 3 — Bound for a partial node. Ek node par hum pehle se kuch items decide kar chuke hain (profit $p$ , weight $w$ used). Bound hai:

bound = p + optimistic completion (fractional fill of remaining items into W - w)

Worked example Tiny knapsack run

$W = 10$ . Items (value, weight): A(40,2), B(30,5), C(50,10), D(10,5). Densities: A=20, B=6, C=5, D=2 → order A,B,C,D.

Root bound (A fully lo: +40 w=2; B fully: +30 w=7; C ko 10 chahiye par sirf 3 bachi → fraction $3/10 \cdot 50 = 15$ ): bound = 85, incumbent = 0.

Branch on A. Why A first? Highest density bound ko drive karta hai.

Include A (p=40,w=2): bound (B full +30 w=7; C frac 3→15) = 85. Promising.
Exclude A (p=0,w=0): bound (B+30; C frac 5→25... actually full B w=5, C frac 5/10·50=25) = 55. Rakho par worse hai.

Include-A node expand karo (LC picks bound 85). Include B → p=70,w=7, bound = 70 + C frac 3→15 = 85. Continue... eventually ek complete solution {A,B} value 70 ke saath incumbent ban jaata hai. Koi bhi node jiska bound ≤ 70 ho pruned ho jaata hai. Exclude-A branch (bound 55 ≤ 70) explore kiye bina khatam. Why this saves work: ek comparison mein poora subtree gone.

Worked example 2: Travelling Salesman lower bound (minimization)

WHY: TSP minimization hai, toh hume ek lower bound chahiye (kisi completing tour ka under-estimate).

Derive the bound. Ek tour mein har city ka exactly ek edge enter karta hai aur ek leave karta hai. Toh har city tour mein kam se kam apne do sabse chhote incident edges contribute karti hai.

Common mistakes

Recall Feynman: explain to a 12-year-old

Tum apne sabhi doston ke ghar visit karne ka sabse sasta raasta dhundh rahe ho. Har single route try karne ke bajaye (boring, forever lagta hai), tum kehte ho: "Agar maine pehle se ek route dhundha hai jo ₹100 cost karta hai, aur main prove kar sakta hoon ki yeh half-finished route kam se kam ₹120 cost karega chahe kuch bhi ho, toh main ise finish nahi karunga." Tum bade chunks of bad routes phek dete ho unka best possible score guess karke aur dekh ke ki woh abhi bhi bahut bura hai. Wahi guessing-and-throwing-away branch and bound hai.

Flashcards

Branch and Bound plain exhaustive search ke upar kaunse do ingredients add karta hai?

Ek bounding function (har subproblem ka optimistic estimate) aur un subtrees ki pruning jinke bound incumbent ko beat nahi kar sakte.

Minimization problem mein tum ek node ko kab prune karte ho?

Jab uska lower bound ≥ current incumbent ho (best complete solution ki cost).

Maximization problem mein tum ek node ko kab prune karte ho?

Jab uska upper bound ≤ current incumbent ho (abhi tak mili best value).

Bound optimistic kyun hona chahiye (max ke liye over-estimate, min ke liye under-estimate)?

Taaki "best case bhi hamare paas jo hai use better nahi" ek valid proof ho, ensure karne ke liye ki hum woh branch kabhi prune na karein jo true optimum contain karta hai.

"Incumbent" kya hai?

Abhi tak mili best complete feasible solution; uski value pruning ka threshold hai.

Branch and Bound aur Backtracking mein kya fark hai?

Backtracking feasibility se prune karta hai koi bhi/sabhi solutions dhundhne ke liye; B&B optimal solution dhundhne ke liye cost bound add karta hai.

FIFO, LIFO, aur LC branch and bound mein kya fark hai?

FIFO queue use karta hai (BFS), LIFO stack (DFS), Least-Cost priority queue use karta hai jo pehle best bound wale node ko pick karta hai.

0/1 knapsack mein ek node ke liye valid upper bound kaise paate ho?

Remaining capacity par fractional (relaxed) knapsack solve karo: value-density se items add karo, last wale ka fraction lete hue.

TSP ke liye lower bound kaise paate ho?

Har city ke incident 2 cheapest edges sum karo, 2 se divide karo (har edge double-counted hai).

Kya B&B worst case mein brute force se better hai?

Nahi — worst case abhi bhi exponential hai; B&B pruning se practically/average mein help karta hai.

Live set se node extract karte waqt bound dobara kyun check karte ho?

Incumbent wait karte waqt improve ho sakta hai, node ko ab prunable bana deta hai (stale node).

TSP mein ek edge force/forbid karna lower bound ko sirf kyun raise karta hai?

Yeh freedom (choices) remove karta hai, toh optimistic estimate sirf increase ho sakta hai, pruning tighten hoti hai.

Connections

Backtracking — B&B = backtracking + cost bounds.
Greedy Algorithms — fractional knapsack greedy knapsack bound supply karta hai.
Dynamic Programming — alternative exact method; B&B memoize karne ki jagah prune karta hai.
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*; heuristic hi bound hai.
Big-O Notation — kyun worst case exponential rehta hai.