Q2 — TSP Branch-and-Bound
TSP BnB tree reading
The Question
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique reference number (a1, b1, b2, ..., c1, ..., d1, ..., e1, …, f1, f2). Use the reference numbers to break ties. When required, enter the reference numbers in short answers.
| # | Question | Official answer |
|---|---|---|
| 2.1 | Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes refined | b1,c2,b2,c3 |
| 2.2 | Which node represents the optimal tour and what is the cost of the optimal tour? | f1,412 |
| 2.3 | Determine the number of cities in the TSP instance. Enter the number of cities in the text box | 5 |
| 2.4 | Start from city A, what is the path representation of the optimal tour? Enter the tour in the text box | A,B,D,C,E |
The Topic in 60 Seconds
- Every tree node = a set of candidate tours sharing the include (
DE) / exclude (~DE) decisions on the path from the root; its number is a lower bound on all tours in that set. - Refining = pop the cheapest open node and insert its two children (include / exclude one more edge).
- A childless node in the snapshot is a finished branch: either a complete tour or pruned.
- Stop condition: when a tour is popped and every remaining open bound is ≥ its cost → that tour is optimal.
Deep-dive: Reading BnB Trees, Branch and Bound.
2.1 — Refinement order → b1,c2,b2,c3
Simulate one priority queue (min bound first; ties by reference number). Internal nodes get refined; leaves get selected.
| Pop # | Queue at pop time (bound : ref) | Action |
|---|---|---|
| 1 | a1 : 383 | refine → add b1(383), b2(406) |
| 2 | b1 : 383, b2 : 406 | refine → add c1(408), c2(392) |
| 3 | c2 : 392, b2 : 406, c1 : 408 | refine → add d3(410), d4(432) |
| 4 | b2 : 406, c1 : 408, d3 : 410, d4 : 432 | refine → add c3(406), c4(436) |
| 5 | c3 : 406, c1 : 408, d3 : 410, d4 : 432, c4 : 436 | refine → add d5(406), d6(446) |
Next four refined after a1: b1, c2, b2, c3 ✓. Note how ~AE (392) jumped ahead of everything after pop 2 — excluding an edge can raise the bound less than including it.
2.2 — Optimal tour node and cost → f1,412
Continue the simulation:
| Pop # | Popped (ref : bound) | Action |
|---|---|---|
| 6 | d5 : 406 | refine → add e3(406), e4(426) |
| 7 | e3 : 406 | refine → add f1(412), f2(426) |
| 8 | c1 : 408 | refine → add d1(436), d2(426) |
| 9 | d3 : 410 | refine → add e1(444), e2(428) |
| 10 | f1 : 412 — childless in the snapshot = complete tour | every open node ≥ 426 > 412 → optimal, stop |
Order check for pops 6–9: the 406-chain keeps regenerating itself (b2 → c3 → d5 → e3 all carry bound 406, so they pop in ref-number order ahead of everything else); refining e3 finally inserts f1(412)/f2(426), after which c1(408) and d3(410) are still cheaper than f1 and get refined first — exactly why the snapshot shows children under c1 and d3 but f1 stays childless. When f1 surfaces at 412 with the whole queue ≥ 426, no cheaper tour can exist anywhere → f1, cost 412 ✓.
2.3 — Number of cities → 5
Reconstruct the tour forced by f1's decision chain (root → b2 → c3 → d5 → e3 → f1):
| Decision | Effect |
|---|---|
| ~DE (b2) | edge D–E forbidden |
| AE (c3) | edge A–E included |
| CE (d5) | edge C–E included |
| BD (e3) | edge B–D included |
| CD (f1) | edge C–D included |
Degrees so far: A–1, B–1, C–2 (full), D–2 (full), E–2 (full). Only A and B still need one edge each → the closing edge AB is forced. That yields a cycle through 5 distinct letters {A, B, C, D, E} → the instance has 5 cities ✓.
2.4 — Optimal tour from A → A,B,D,C,E
Chain the forced edges: A–B (closing edge), B–D, D–C, C–E, E–A:
Tour A,B,D,C,E (return to A implied), total cost 412 ✓. Note it uses both excluded-edge logic (~DE is why the tour detours through C between D and E... rather D–C–E instead of D–E) and the included edges verbatim.
Interactive view of the run — step through the refinements and the final tour pop:
Amber marks each pop in order (a1, b1, c2, b2, c3, d5, e3, c1, d3, then f1); green traces the winning include-chain b2 → c3 → d5 → e3 → f1.
Tricks & Tips
Answers: 2.1 b1,c2,b2,c3 · 2.2 f1,412 · 2.3 5 · 2.4 A,B,D,C,E