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

The Question

TSP BnB snapshot when the optimal tour is discovered.

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,c2,d1,b2

Pop the minimum bound each round; refining replaces the popped node by its two children.

Note how each include-node leaves its exclude-child cheaper than everything else (c2 : 242 under b1, then d1 : 242 under c2) — that cascade fixes the refine order on its own.

2.2 — Optimal tour → d3, cost 244

Pop c3(244) → adds d3(244), d4(255). Queue sorted: {d3 : 244, e2 : 249, e1 : 268, c4 : 270, c1 : 276, d4 : 255, d2 : 340} — i.e. min = d3 : 244, next-best e2 : 249.

d3 has no children in the snapshot — it is a complete tour — and every other open bound is ≥ 249 > 244. Nothing cheaper can ever appear → d3 = optimal, 244 ✓

2.3 — Cities → 5

Chain root→d3: ~AD excluded → BD in → BC in. Fixed edges: B–D, B–C.

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

AD is excluded, so A cannot pair with D → A's two partners are C and E. Now C is full (B, A), and D still needs one partner — only E remains → D–E. One closed cycle:

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

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

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

Amber = refined in order b1 → c2 → d1 → b2. Green = d3, the 244 tour.

Tricks & Tips

Answers: 2.1 b1,c2,d1,b2 · 2.2 d3,244 · 2.3 5 · 2.4 A,C,B,D,E