Q2 — TSP Branch-and-Bound
Reading a finished BnB tree backwards: the refine order falls out of a priority queue, the optimal leaf hides under an excluded edge, and the tour rebuilds by degree-forcing.
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, …, e4). 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
| # | Question | Official answer |
|---|---|---|
| 2.1 | Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes | b1,b2,c3,d3 |
| 2.2 | Which node represents the optimal tour and what is the cost of the optimal tour? | e3,390 |
| 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,D,C,B,E |
The Topic in 60 Seconds
TSP BnB keeps an OPEN priority queue of constraint-sets keyed by lower bound:
- Refine = pop the smallest-bound node, branch it into "edge XY included" vs "edge XY excluded".
- A leaf at depth fixes every remaining choice → one complete tour.
- After an incumbent tour appears, any open node with bound ≥ incumbent can be discarded.
Deep-dive: browse the Concepts section for Branch-and-Bound.
2.1 — Refine order → b1,b2,c3,d3
Simulate the queue (smallest bound first; ties by reference number):
| Step | Refined | Children pushed | OPEN after (sorted) |
|---|---|---|---|
| 1 | a1 (343) | b1 : 343 · b2 : 385 | b1(343), b2(385) |
| 2 | b1 (343) | c1 : 410 · c2 : 388 | b2(385), c2(388), c1(410) |
| 3 | b2 (385) | c3 : 385 · c4 : 462 | c3(385), c2(388), c1(410), c4(462) |
| 4 | c3 (385) | d3 : 385 · d4 : 460 | d3(385), c2(388), c1(410), d4(460), c4(462) |
| 5 | d3 (385) | e3 : 390 · e4 : 422 | … |
Next four refined after S0: b1, b2, c3, d3 — note how the fresh 385-bounded children keep leap-frogging the older 388/410 entries.
2.2 — Optimal leaf → e3, cost 390
Refining d3 yields two complete-tour leaves: e3 = 390 and e4 = 422. With e3 = 390 as incumbent, BnB must still empty the queue: c2 (388 < 390) refines to d1 (388) / d2 (491); d1 refines to e1 (430) / e2 (416) — both above 390, nothing beats the incumbent. Every other open bound (410, 422, 460, 462, 491) already exceeds 390.
⇒ optimal tour = leaf e3, cost 390.
2.3 — Number of cities → 5
Count the branching levels on any root-to-leaf chain: a1 → (BD decision) → (CD decision) → (BC decision) → (AD decision) = 4 edge decisions. This BnB variant pins one tour edge per level and needs levels, so
(Cross-check: five cities appear in the tour of 2.4.)
2.4 — Rebuilding the tour from leaf e3 → A,D,C,B,E
Collect the edge decisions along a1 → b2 → c3 → d3 → e3 (careful: e3 hangs under ~BD, not BD!):
| Node | Decision |
|---|---|
| b2 | exclude BD |
| c3 | include CD |
| d3 | include BC |
| e3 | include AD |
Forced edges: , with BD banned. Degrees so far: A–D, C–D, C–B. Cities E and A still have degree 1 → the two unbranched edges must close the loop:
Tour: A → D → C → B → E →(back to A), i.e. A,D,C,B,E. Cost check against the leaf: 390 ✓ (consistent bounds).
Interactive trace — the refine queue
Tricks & Tips
Answers: 2.1 b1,b2,c3,d3 · 2.2 e3,390 · 2.3 5 · 2.4 A,D,C,B,E