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, e2). Use the reference numbers to break ties. When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the se
| # | Question | Official answer |
|---|---|---|
| 2.1 | Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes | b1,c2,b2,c3 |
| 2.2 | Which node represents the optimal tour and what is the cost of the optimal tour? | d3,434 |
| 2.3 | Determine the number of cities in the TSP instance. Enter the number of cities i | 5 |
| 2.4 | Start from city A, what is the path representation of the optimal tour? Enter th | A,B,D,E,C |
The Topic in 60 Seconds
Every tree node carries a lower bound. The loop:
- Pick the live node with the smallest bound (ties → reference number).
- Refine it: split on the next edge — child
XY= edge included, child~XY= edge excluded. - A child whose constraints already force a unique complete tour becomes a leaf with the tour cost.
- Stop when the smallest live bound ≥ best complete tour found → that tour is optimal.
Deep-dive: BnB Tree Reading, Branch and Bound.
The Trace
Always refine the cheapest live node:
| Refined | Bound | Children created | Live set after (ref : bound) |
|---|---|---|---|
| a1 : 375 | 375 | b1 = BD∈ (375), b2 = BD∉ (414) | b1(375), b2(414) → pick b1 |
| b1 : 375 | 375 | c1 = CD∈ (418), c2 = CD∉ (410) | c2(410) < b2(414) < c1(418) → pick c2 |
| c2 : 410 | 410 | d3 = AB∈ (complete tour, 434), d4 = AB∉ (468) | b2(414) < c1(418) < incumbent 434 → pick b2 |
| b2 : 414 | 414 | c3 = CD∈ (414), c4 = CD∉ (452) | c3(414) < c1(418) < 434 → pick c3 |
| c3 : 414 | 414 | d5 = AB∈ (414), d6 = AB∉ (572) | d5(414) < c1(418) < 434 → pick d5 |
| d5 : 414 | 414 | e1 = AD∈ (436), e2 = AD∉ (472) | c1(418) < 434 → pick c1 |
| c1 : 418 | 418 | d1 = AB∈ (456), d2 = AB∉ (548) | min live bound = incumbent 434 → STOP |
The next four refinements after a1 are exactly b1 (375), c2 (410), b2 (414), c3 (414) ✓ — each time the whole live set is compared and the smallest bound wins.
Watch the tree grow (orange = refining now, blue = live in the queue):
Answers, decoded
- 2.1 →
b1,c2,b2,c3. After a1 splits, the queue holds b1(375) vs b2(414) → b1. Refining b1 drops c2(410), which undercuts everything → c2 next. Then b2(414) beats c1(418); then c3(414) beats c1(418). Always compare the whole live set, not just siblings. - 2.2 →
d3,434. d3's constraint chain: BD∈ (b1), CD∉ (c2), AB∈ (d3) forces the path A–B–D outright — a leaf with no children means the remaining edges were forced, so its bound is a complete tour cost. Termination: after c1 is refined, every live bound (436, 452, 468, 472, 548, 572) ≥ 434. - 2.3 →
5. The optimal tour visits five distinct cities — A, B, D, E, C — so the instance has 5 cities; a Hamiltonian cycle here has 5 edges, and the tree fixes them one branching at a time (BD, CD, AB, AD explicit — the fifth edge CA comes for free). - 2.4 →
A,B,D,E,C. From d3's forced path A–B–D, the only unvisited cities are E and C; CD∉ forbids closing D→C directly, so D must go to E, leaving C to close the cycle: , cost 434 ✓.
Tricks & Tips
Answers: 2.1 b1,c2,b2,c3 · 2.2 d3,434 · 2.3 5 · 2.4 A,B,D,E,C