TSP Branch and Bound: Complete Walkthrough

1. TSP setup: cities, matrix, tour

TSP: visit every city exactly once and return to the start, minimising total cost. Input is a cost matrix. A tour on \(n\) cities uses exactly \(n\) edges.

Example cost matrix (symmetric)

Solved mini-example. Tour A,B,D,C,A costs 10 (AB) + 25 (BD) + 30 (DC) + 15 (CA) = 80. Tour A,C,B,D,A costs 15 + 35 + 25 + 20 = 95. So the first is better. Every TSP question below is this same comparison, scaled up and organised by the search tree.

2. Branch and Bound for TSP: the refinement space

The search space here is not a map. It is a refinement space: the root node S0 is the set of all possible tours. Refining a node means splitting its tour set in two using one edge: one child includes the edge (label XY), the other excludes it (label ¬XY; the question text writes it as ~XY).

Each node carries a cost = lower bound on the best tour inside its set. A lower bound never overestimates: every tour in that set costs at least the bound. The algorithm is one line:

Always refine the unrefined leaf with the smallest cost. Stop when that leaf is a fully refined single tour. At that point no other leaf can beat it, because every other leaf only promises a bound at or above its actual cost.

Solved mini-example. Leaves: b1 (cost 218), b2 (cost 235). Refine b1: it promises the cheaper set. Its children c1 (250), c2 (222) join the leaves. Now leaves are b2 (235), c1 (250), c2 (222). Refine c2. That is the whole algorithm, repeated.

3. How to read the search tree

Every node in the exam tree shows three things:

1. Edge: XY means every tour in this set uses edge XY; ¬XY means no tour in this set uses it. The root S0 has no edge.
2. Cost: the lower bound for this set. Costs never decrease along a refinement path in a correct tree.
3. Reference number: a unique id like a1, b1, b2, c1. The letter is the depth level, the digit counts nodes at that level. Ties in cost are broken by reference number (compare alphabetically: b1 before b2, any b before any c).

Solved mini-example. Node "b1, AD, 224" reads: first-level node, every tour here includes edge AD, cheapest such tour costs at least 224. If another leaf also shows 224, say b2, refine b1 first (b1 comes first alphabetically).

4. Worked example: 2024T2 FN, Q57 to Q60 (real tree)

4a. The tree as a table (solve from this, then check the animation)

Cover the animation below. Starting from a1, list each refinement by picking the cheapest unrefined leaf, then find the cheapest complete tour. Official answers: b1,c2,d1,b2; d3,244; 5; A,C,B,D,E.

4b. Animation: the full tree, highlighted step by step

The animation below hides nothing: every node is visible from the start. Stepping forward only marks progress. Black means refined, outline means refining right now, grey means the two new leaves that refinement has just produced, thick border at the end means the optimal tour. The ¬ sign marks exclusion (the question text writes ~AD): ¬AD means the edge AD is excluded.

4c. Full question

4d. Step by step solution

1. Refinement order. 1st: a1 (only node). It generates b1 (AD, 224) and b2 (¬AD, 244). Min is b1, so 2nd: b1. It generates c1 (BD, 276) and c2 (¬BD, 242). Leaves: c2 (242), b2 (244), c1 (276). Min is c2, so 3rd: c2. It generates d1 (BC, 242) and d2 (¬BC, 340). Leaves: d1 (242), b2 (244), c1 (276), d2 (340). Min is d1, so 4th: d1. It generates e1 (AC, 268) and e2 (¬AC, 249). Leaves: b2 (244), e2 (249), e1 (268), c1 (276), d2 (340). Min unrefined leaf is b2 (244), so 5th: b2. It generates c3 (BD, 244) and c4 (¬BD, 270). Leaves: c3 (244), e2 (249). Min is c3, so 6th: c3. It generates d3 (BC, 244, complete tour) and d4 (¬BC, 255). Answer to Q57: b1,c2,d1,b2.
2. Optimal node. Scan all leaves for a fully refined single tour with the smallest cost: d3 is the complete tour A-C-B-D-E-A costing 244. The only other complete tour is e2 (249). Every partial leaf promises a bound at or above 244 (c1: 276, d2: 340, c4: 270, d4: 255). So none can beat d3. Answer to Q58: d3,244.
3. Number of cities. The optimal tour A-C-B-D-E-A uses edges AC, CB, BD, DE, EA. Distinct cities: A, B, C, D, E. Answer to Q59: 5. Rule: count distinct city letters; a tour on n cities has exactly n edges.
4. Tour from A. Walk the tour edges from A: A to C (AC), C to B (CB), B to D (BD), D to E (DE), E to A (EA). Answer to Q60: A,C,B,D,E. The reverse walk A,E,D,B,C is the same tour and is accepted. Note the path is consistent with the tree: the d3 branch includes BC and BD (via c3) and excludes AD (via b2).

5. Practice: four more real trees

Each tree below is a real past paper tree. For each one, answer all four sub-questions with a pen, then open the answer. Rule throughout: refine the min-cost unrefined leaf, ties by reference number.

Tree P1: 2024T3 FN, Q62 to Q65 (small, asks 2nd to 4th)

Q: 2nd to 4th refined? Optimal node and cost? Cities? Tour from A?

Tree P2: 2024T3 AN, Q62 to Q65 (small, asks 2nd to 4th)

Q: 2nd to 4th refined? Optimal node and cost? Cities? Tour from A?

Tree P3: 2024T1 FN, Q100 to Q103 (big, 6 cities)

Q: 2nd to 5th refined? Optimal node and cost? Cities? Tour from A?

Tree P4: 2025T2 FN, Q69 to Q73 (big, optimal found late)

Q: 2nd to 5th refined? Optimal node? Optimal cost? Cities? Tour from A?

6. Exam checklist (write this on the rough sheet)

1. Refinement order: a1 first, then always the min-cost unrefined leaf; ties by reference number (b1 before b2, any b before any c).
2. After each refinement, list all current unrefined leaves with costs before picking the next. Never pick from memory.
3. Optimal = cheapest fully refined leaf (a complete tour), answer as ref,cost. Partial leaves with higher bounds are pruned by definition.
4. Cities = distinct city letters in the optimal tour. A tour on n cities has exactly n edges.
5. Tour from A: walk the tour edges from A; reverse is accepted. No spaces in the answer. NIL only if no complete tour exists.