Branch and Bound

1Live nodes, E-nodes, and a bounding function

Branch and bound searches a tree of partial answers. Each node is a prefix of a solution — the first few include/exclude decisions, or the first few cities of a tour. A live node has been created and is waiting to be expanded. The E-node (expansion node) is the live node you are expanding now. A dead node will never be expanded.

What kills a node is a bounding function: a number that no feasible completion of that node can beat. For a maximisation problem you kill the node when its bound is no better than the best complete solution already in hand (the incumbent). The bound must be a true limit — if it can be worse than some real completion, you may discard the optimum.

Figure. Static snapshot of statuses, not a playback of the search. The E-node is being expanded; the right child is already dead by bound.

One expansion

1. Pick an E-nodeTake one live node (FIFO, LIFO, or least-cost).
2. BranchGenerate its children — the next decision's options.
3. Bound or killCompute each child's bound. If it cannot beat the incumbent, mark the child dead; otherwise it becomes live.

2FIFO, LIFO, or least-cost live nodes

The bounding function does not pick which live node becomes the next E-node. That is a separate policy. FIFO expands live nodes in the order they were born — breadth-first. LIFO expands the newest live node — depth-first, close to backtracking. Least-cost (LC) expands the live node whose bound looks best: largest upper bound on a maximisation problem, smallest lower bound on a minimisation problem.

LC often finds a strong incumbent sooner, which then kills more siblings. It is not a different algorithm family; it is a different queue.

Figure. Same bound, three queues. The bars are a qualitative 'how soon a good incumbent arrives' sketch, not a runtime claim.

What the queue changes

1. FIFOExpand level by level. Memory holds a whole level of live nodes.
2. LIFODive down one path. Memory holds one path plus unexplored siblings.
3. Least-costAlways expand the currently most promising bound. Needs a priority queue of live nodes.

30/1 knapsack: one item per level

The 0/1 knapsack state-space tree has one level per item. The left child of a node includes that item (if it still fits); the right child excludes it. A leaf is a complete packing. Without pruning there are 2^n leaves — the same tree backtracking walks.

The running instance for the rest of this topic: three items (w,v) = (2,10), (3,14), (4,16) and capacity W = 6. Feasible packs are \{1,2\} value 24, \{1,3\} value 26, and the singletons. The 0/1 optimum is 26. Item 3 alone is 16; items 2 and 3 together weigh 7 and do not fit.

Figure. Partial state-space, not the full 2^3 tree. The highlighted leaf is the 0/1 optimum 26. Skip-1 children are omitted so the figure stays readable.

Read one node

1. PrefixA node records which of the first i items are taken, the weight so far, and the value so far.
2. Left = takeIf item i+1 fits, the left child adds its weight and value.
3. Right = skipThe right child leaves weight and value unchanged and moves to the next item.

Coding lab. Pack the three-item knapsack runs in the app, with checks on your output.

4Knapsack bound: fill the rest fractionally

At a knapsack node you already have some weight and value. The remaining items are considered in decreasing v/w order. Take each whole item that still fits; when the next item does not fit, take the fraction of it that fills the leftover capacity. Add that (possibly fractional) extra value to the node's value. The sum is an upper bound on every 0/1 completion of the node.

It is legal as a bound because a fractional packing is at least as good as any 0/1 packing of the same remaining capacity. It is not a feasible 0/1 answer. Prune a node when this bound is \le the incumbent.

Figure. Root bound as a capacity strip: items 1 and 2 fill 5 of 6, then a quarter of item 3 fills the last unit for +4. The terracotta slice is the fraction — not a 0/1 item.

Bound at the root

1. Sort by v/wItem 1 has 10/2 = 5; item 2 has 14/3 \approx 4.67; item 3 has 16/4 = 4.
2. Take wholesTake item 1 (weight 2, value 10) and item 2 (weight 3, value 14). Capacity left is 1.
3. Take a fractionItem 3 needs 4; take 1/4 of 16, which is 4. Bound 10+14+4 = 28.

Fractional upper bound

def bound(level, weight, value, items, W):
    # items[level:] already sorted by v/w decreasing
    cap = W - weight
    b = value
    for w, v in items[level:]:
        if w <= cap:
            cap -= w
            b += v
        else:
            b += v * (cap / w)
            break
    return b

5TSP: append one unused city

The travelling-salesman state-space tree (from a fixed start) has one level per unvisited city. A node is a simple path that has not yet returned home. A child appends one unused city. A leaf that has used every city is completed by the edge back to the start and becomes a tour.

The running instance: four cities, start at 1, symmetric distances 1-2=2, 1-3=9, 1-4=10, 2-3=6, 2-4=4, 3-4=3. Without pruning there are 3! = 6 tours. Two of them cost 18: 1-2-4-3-1 and 1-3-4-2-1. That 18 is the optimum.

Figure. One optimal tour 1-2-4-3-1 of cost 2+4+3+9=18. Edge lengths are the instance, not to scale.

One branch from city 1

1. Children of the startPaths 1-2 (cost 2), 1-3 (cost 9), 1-4 (cost 10).
2. Continue 1-2Append 3 (path 8) or 4 (path 6).
3. Close a tour1-2-4-3 plus the edge 3-1 of 9 is 18.

6TSP prune: path already worse than the incumbent

TSP is a minimisation problem, so a node dies when no completion can be cheaper than the incumbent. The weakest correct bound is the path cost so far: if that number is already \ge the incumbent, every completion is at least as expensive (edge weights here are positive), and the node is dead.

On the running instance, once the tour of cost 18 is in hand, path 1-4 (cost 10) is still alive under this weak bound, and path 1-2-3 (cost 8) is still alive. A node whose path had already reached 18 or more would die. Stronger textbook bounds — row-and-column reduction of the cost matrix, or path plus a cheap spanning completion — kill more nodes, but only if they are true lower bounds. A bound that can undershoot a real tour can discard the optimum.

Apply the weak bound

1. Find any tourExpand 1-2-4-3-1 and record incumbent 18.
2. Test a live pathPath 1-3 costs 9. 9 < 18, so the weak bound does not kill it.
3. What would dieAny path whose cost is already \ge 18 is dead. Completions of 1-3 happen to be 18 and 29 — none beats 18.