Q2 — TSP Branch-and-Bound
TSP BnB tree reading — refine order b1,c1,d2,b2, optimal leaf d5 at 366, tour A,B,D,C,E.
The Question
TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below.
Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties. When required, use 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 search tree.
| # | Question | Official answer |
|---|---|---|
| 2.1 | Determine the number of cities in the TSP instance | 5 |
| 2.2 | Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes refined | b1,c1,d2,b2 |
| 2.3 | Which node represents the optimal tour? | d5 |
| 2.4 | What is the cost of the optimal tour? | 366 |
| 2.5 | Starting from city A, what is the path representation of the optimal tour? | A,B,D,C,E |
The Topic in 60 Seconds
Every node = an edge decision (XY include / ¬XY exclude) with a lower bound. Refine = pop the cheapest bound and branch both ways. A node with no children in the snapshot is a complete tour. When a tour pops while all open bounds are ≥ its cost, it is optimal.
Deep-dive: Reading BnB Trees, Branch and Bound.
2.1 — Number of cities → 5
The deepest branch runs root → b → c → d → e (nodes e1, e2): four decision levels below the root. Each level settles one tour edge and the remainder is forced, so levels ⇒ 5 cities ✓
2.2 — Refine order after a1 → b1,c1,d2,b2
Pop the minimum bound each round (ties → reference labels). Full ledger:
| Pop | Node : bound | Children created | OPEN after (cheapest first) |
|---|---|---|---|
| 1 | a1 : 305 | b1 : 305, b2 : 342 | b1 305 · b2 342 |
| 2 | b1 : 305 | c1 : 305, c2 : 350 | c1 305 · b2 342 · c2 350 |
| 3 | c1 : 305 | d1 : 382, d2 : 327 | d2 327 · b2 342 · c2 350 · d1 382 |
| 4 | d2 : 327 | e1 : 378, e2 : 403 | b2 342 · c2 350 · e1 378 · d1 382 · e2 403 |
| 5 | b2 : 342 | c3 : 342, c4 : 387 | c3 342 · c2 350 · e1 378 · d1 382 · c4 387 · e2 403 |
Refined #2–#5 = b1, c1, d2, b2 ✓ — note d2 (327) leapfrogs everything right after being created.
2.3 & 2.4 — Optimal node and cost → d5, 366
Continue the ledger:
| Pop | Node : bound | Children created | OPEN after |
|---|---|---|---|
| 6 | c3 : 342 | d5 : 366, d6 : 382 | c2 350 · d5 366 · e1 378 · d1 382 · d6 382 · c4 387 · e2 403 |
| 7 | c2 : 350 | d3 : 500, d4 : 516 | d5 366 · e1 378 · d1 382 · d6 382 · c4 387 · e2 403 · d3 500 · d4 516 |
| 8 | d5 : 366 — leaf ⇒ tour | none | e1 378 · d1 382 · d6 382 · c4 387 · e2 403 · d3 500 · d4 516 |
d5 pops as a leaf with every open bound ≥ 366 → nothing can beat it → d5 is the optimal tour at cost 366 ✓
2.5 — Tour from city A → A,B,D,C,E
Walk a1 → d5: ¬AC (b2), BD in (c3), CD in (d5). Fixed facts on the five cities:
| City | Degree from fixed edges | Note |
|---|---|---|
| B | 1 (BD) | needs 1 more |
| D | 2 (BD, CD) | full |
| C | 1 (CD) | AC excluded |
| A | 0 | AC excluded |
| E | 0 | free |
D is full, so A's two partners come from B and E → AB and AE forced, which fills B. C cannot use A (excluded) or B/D (full), leaving CE forced. Final edge set: AB, BD, DC, CE, EA → cycle A-B-D-C-E-A = A,B,D,C,E, five cities ✓
Sanity read-back: the tour uses BD ✓, CD ✓ and avoids AC ✓ exactly as d5's ancestry demands.
Interactive refinement trace
Tricks & Tips
Answers: 2.1 5 · 2.2 b1,c1,d2,b2 · 2.3 d5 · 2.4 366 · 2.5 A,B,D,C,E