Foundations — Branch and bound

This page assumes you know nothing. Before you can read the parent note, you need a small toolbox of pictures and symbols. We build each one from zero, in an order where every piece rests on the piece before it.

0. What is an "optimization problem"?

Picture a shelf of finished answers, each with a price tag. An optimization problem is not "find an answer" — it is "find the answer with the smallest (or largest) tag."

• Minimization = smallest tag wins (cheapest tour).
• Maximization = largest tag wins (most-valuable knapsack).

The topic needs this because B&B only makes sense when there is a "best" to chase. If you just want any legal answer, you'd use plain Backtracking instead.

Every dot on that shelf is a complete answer; the red dot is the optimum. B&B's whole job is to find the red dot without inspecting most of the black dots.

1. The objective function and its symbols

• $x$ ::: stands for one complete candidate answer (a full tour, a full item-selection).
• $\text{cost}(x)$ ::: the single number we compare answers by.

Why the topic needs it: pruning is one comparison of numbers. Without a number per answer, there is nothing to compare.

2. What is a "solution tree"? (branching)

Read the figure top-to-bottom:

• The root (top) is an empty choice.
• Each node branches into children — one child per option of the next decision (here: include item vs exclude item).
• A partial node in the middle = "some decisions made, some still open."
• A leaf = a full answer, ready to price.

"Branch" in "Branch and Bound" is literally this: splitting one node into its children.

3. The symbols $\le$, $\ge$, $\le W$ — comparing and constraining

Look at the figure: the sign is like a mouth that always opens toward the bigger number and its point aims at the smaller one. In $a\le b$ the wide open side faces $b$, so $b$ is the larger side; in $a\ge b$ the open side faces $a$. That single picture tells you which side wins — no memorizing needed.

In the parent note you meet $\text{weight}\le W$. This is a constraint: a rule an answer must obey to be legal (feasible). $W$ is just a fixed number — the knapsack's capacity.

• $W$ ::: the fixed limit (max weight the bag holds).
• $w$ ::: the weight already used by decisions made so far.
• $c=W-w$ ::: the capacity still remaining.

Picture a bag with a fill-line at $W$. As you drop items in, $w$ rises toward the line; $c$ is the gap left below it. When $w>W$ the answer is illegal — it overflows.

4. The incumbent — best-so-far

Picture a scoreboard with one line: "Best so far: ₹100." Every time we finish a leaf that beats it, we overwrite that line.

Why the topic needs it: the incumbent is the yardstick. Pruning asks "can this branch beat the champion?" — with no champion, nothing to compare against, so we start it at $+\infty$ (minimization) or $-\infty$ (maximization), meaning "no champion yet, everything beats nothing."

• $+\infty$ ::: "infinity," a value larger than any real number — a placeholder meaning "unbeaten."

5. The bound — the optimistic guess (the heart)

In the figure, the red horizontal line is the node's bound. Every leaf under that node lives on the worse side of the red line — that is what "guaranteed" means.

How do we get such a guaranteed guess? By relaxation:

Let us now build, from these symbols, the exact upper bound the parent note uses for 0-1 Knapsack. First we name the item symbols:

• $p$ ::: profit (value) already collected by decisions made at this node.
• $v_i$ ::: value of item $i$; $w_i$ ::: weight of item $i$.
• $v_i/w_i$ ::: value-density, "rupees per kilo" — how good an item is per unit weight.

Deriving the fractional-knapsack bound step by step

0-1 Knapsack forbids fractions of items (each item is 0 or 1). Relax that rule — allow fractions. Because fractions give more freedom, the relaxed maximum is $\ge$ the true maximum, so it is a valid upper bound. Here is how greedy computes it at one node.

Walk the bag-filling, tracking the space left. We already have profit $p$ and used weight $w$, so the space to fill is $c=W-w$ (our remaining capacity from Section 3).

Step 1 — pour in whole items that fit. Go through the not-yet-decided items in density order. Each one that entirely fits into the space left, drop it in fully: it adds its full value $v_j$. As we do this the free space shrinks. Call the space still free at the moment we can no longer fit a whole item $c^{\prime }$ — it is simply "how much of $c$ is left after the whole items went in." So $c^{\prime }$ is the same kind of number as $c$, just measured a few items later; it is not new notation, only a later snapshot of the remaining space.

• $j$ ::: any item that goes in fully (fits whole into the space left).
• $c^{\prime }$ ::: the space still free after all the whole items are packed. Starts at $c$, only shrinks.

Step 2 — meet the first item that does NOT fit; call it $k$. Item $k$ is simply the first item in density order whose full weight $w_k$ is bigger than the free space $c^{\prime }$. It is not chosen by magic — it is whichever item the pouring process bumps into first that would overflow the bag.

• $k$ ::: the first density-ordered item that overflows — it fits only partly.

Step 3 — shave off exactly the fraction of $k$ that fits (when $k$ exists). We have $c^{\prime }$ space and item $k$ weighs $w_k$. So the fraction of $k$ that fits is $\frac{c^{\prime }}{w_k}$ (space available ÷ item's weight). Why divide these two? If the item weighs $w_k$ and we only have room for $c^{\prime }$, the portion we can take is "room over full weight." That fraction of $k$ carries that same fraction of $k$'s value: $\text{value of the shaved piece}=\underset{\text{fraction that fits}}{\underbrace{\frac{c^{\prime }}{w_k}}}\times v_k.$ If $c^{\prime }=0$ (bag already exactly full), the fraction is $0$ and no piece is added — the formula still works.

Putting the three steps together gives the node's upper bound:

6. The pruning rule — one comparison

The figure shows two nodes. The kept node's bound sits on the winning side of the incumbent line (it might beat the champion). The red pruned node's bound sits on the losing side — deleted, along with everything below it, in one comparison.

7. The live set and picking order

• Queue ::: a line at a shop — first in, first out.
• Stack ::: a pile of plates — last on, first off.
• Priority queue ::: a magic bag that always hands you the most promising node first.

Why the topic needs it: pulling the best-bound node first tends to find a strong incumbent early, which makes the prune test fire more often — less total work.

8. Growth notation $O(2^n)$, $O(n!)$

Why the topic needs it: B&B does not change the worst-case growth — if nothing prunes, the tree is still fully $O(2^n)$ or $O(n!)$. It only speeds up the typical case. This is a common trap addressed in the parent's mistakes.

How these foundations feed the topic

The pieces you just built stack up in one clean chain. Read the map below one arrow at a time, top to bottom:

1. An optimization problem gives you the very notion of a "best" answer.
2. That best is measured by an objective value, $\text{cost}(x)$ — the number we compare.
3. Candidate answers get organised into a solution tree by branching; at any moment a partial node carries a remaining capacity $c$.
4. Separately, the best complete answer found so far is the incumbent.
5. At each partial node, relaxation produces a bound — the optimistic guess.
6. The prune test compares that bound against the incumbent; combined with the live set ordering, this is Branch and Bound.

Related paradigms that share pieces of this toolbox: Backtracking (branching + feasibility, no bound), Dynamic Programming (also finds optima, different mechanism), and applications Travelling Salesman Problem and A* Search (which is B&B with a heuristic bound).

Equipment checklist

Cover the answer and test yourself before reading the parent note.