Q2 — TSP Branch-and-Bound: Refine Order and the 402 Tour

The Question

TSP BnB snapshot when the optimal tour is discovered. XY = include, ~XY = exclude; numbers = lower bounds; reference numbers break ties.

The Topic in 60 Seconds

Refine = pop the cheapest open node, insert its two children. Childless snapshot nodes are tours. Stop when a tour pops with no cheaper open node.

Deep-dive: Reading BnB Trees, Branch and Bound.

2.1 — Refine order → b1,c1,d1,d2

Pop the minimum bound each round (ties by reference number); refining replaces the popped node with its two children.

The 380 cluster (a1, b1, c1) refines back-to-back because each leaves an equal-bound child behind.

2.2 — Optimal tour → e2, cost 402

Queue after pop 5, sorted: {e2 : 402, c2 : 406, b2 : 422, e4 : 428, e3 : 434, e1 : 454}. The minimum, e2 : 402, has no children in the snapshot — it is a complete tour — and every other open bound is ≥ 406 > 402. Nothing below it can ever appear → e2 = optimal, 402 ✓

2.3 — Cities → 6

Chain root→e2: DE in → BC in → BE in → ~AD excluded. Fixed edges: D–E, B–C, B–E.

Degrees so far: B = 2 (C, E) full · E = 2 (D, B) full · C = 1 (B) · D = 1 (E) · A = 0 · F = 0.

AD is excluded, so A cannot pair with D. A needs two edges from {C, F} → forced A–C and A–F. Now C is full (B, A), and D still needs one partner — only F remains → D–F. One closed cycle:

$A - C - B - E - D - F - A \Rightarrow \textbf{6 cities} ✓$

2.4 — Tour from A → A,C,B,E,D,F

The forced cycle above read clockwise from A ✓ (the reverse A,F,D,E,B,C is the same tour).

Amber = refined in order b1 → c1 → d1 → d2. Green = e2, the 402 tour.

Tricks & Tips

Answers: 2.1 b1,c1,d1,d2 · 2.2 e2,402 · 2.3 6 · 2.4 A,C,B,E,D,F