Q2 — TSP Branch-and-Bound: Six Cities
A six-city TSP instance resolved via a 6-level BnB tree — the 456 tour through A,C,E,D,B,F.
The Question
TSP BnB snapshot when the optimal tour is discovered.
| # | Question | Official answer |
|---|---|---|
| 2.1 | Number of cities | 6 |
| 2.2 | 2nd–5th refined | b1,c2,d3,c1 |
| 2.3 | Optimal tour node | f1 |
| 2.4 | Cost | 456 |
| 2.5 | Tour from A | A,C,E,D,B,F |
The Topic in 60 Seconds
Each node carries an edge decision (XY = include, ¬XY = exclude) plus a lower bound. Refining = pop the node with the smallest bound and create both children. A childless node is a complete tour. Stop when a tour pops while every open bound is at least as large — nothing left can beat it.
Deep-dive: Reading BnB Trees, Branch and Bound.
2.1 — Number of cities → 6
The deepest branch runs root → b → c → d → e → f (nodes f1, f2): that is 5 decision levels below the root. Each level settles one tour edge, and a full refinement needs levels before the last edge is forced. So 6 cities ✓
2.2 — Refine order after a1 → b1,c2,d3,c1
Pop the cheapest bound each round; ties break on reference labels.
| Pop | Node : bound | Children created | OPEN after (cheapest first) |
|---|---|---|---|
| 1 | a1 : 424 | b1 : 424, b2 : 459 | b1 424 · b2 459 |
| 2 | b1 : 424 | c1 : 449, c2 : 437 | c2 437 · c1 449 · b2 459 |
| 3 | c2 : 437 | d3 : 440, d4 : 456 | d3 440 · c1 449 · b2 459 · d4 456 |
| 4 | d3 : 440 | e3 : 496, e4 : 490 | c1 449 · b2 459 · d4 456 · e4 490 · e3 496 |
| 5 | c1 : 449 | d1 : 449, d2 : 501 | d1 449 · b2 459 · d4 456 · e4 490 · e3 496 · d2 501 |
Refined #2–#5 = b1, c2, d3, c1 ✓ — note how c2 (437) jumps the queue ahead of its own sibling c1 (449).
2.3 & 2.4 — Optimal node and cost → f1, 456
Continuing from the last table:
| Pop | Node : bound | Children created | OPEN after |
|---|---|---|---|
| 6 | d1 : 449 | e1 : 460, e2 : 508 | d4 456 · b2 459 · e1 460 · e4 490 · … |
| 7 | d4 : 456 | e5 : 456, e6 : 488 | e5 456 · b2 459 · e1 460 · e6 488 · … |
| 8 | e5 : 456 | f1 : 456, f2 : 484 | f1 456 · b2 459 · e1 460 · … |
| 9 | f1 : 456 — leaf ⇒ a tour | none | b2 459 · e1 460 · e6 488 · f2 484 · e4 490 · e3 496 · d2 501 · e2 508 |
When f1 pops, every remaining open bound is ≥ 456, so no unexplored branch can produce anything cheaper → f1 is the optimal tour, cost 456 ✓
2.5 — Tour from city A → A,C,E,D,B,F
Walk the path a1 → f1 and collect the decisions: BF in (b1), DF out (c2), EF out (d4), CE in (e5), AC in (f1). Now finish the cycle by degree-forcing:
| City | Degree so far | Needs |
|---|---|---|
| A | 1 (AC) | 1 more |
| B | 1 (BF) | 1 more |
| C | 2 (AC, CE) | full |
| D | 0 | 2 more |
| E | 1 (CE) | 1 more |
| F | 1 (BF) | 1 more |
DF and EF are excluded, so F can only close via FA (C is full) → A becomes full too. D must take exactly two partners: DA is blocked (A is full), leaving DB and DE forced. That fills B (BF+BD) and E (CE+ED). Final edge set: AC, CE, ED, DB, BF, FA → cycle A-C-E-D-B-F-A, i.e. A,C,E,D,B,F, 6 cities ✓
Interactive refinement trace
Tricks & Tips
Answers: 2.1 6 · 2.2 b1,c2,d3,c1 · 2.3 f1 · 2.4 456 · 2.5 A,C,E,D,B,F