Q2 — TSP Branch-and-Bound
A six-city BnB tree: the priority queue dictates b1,c1,d2,c2, a forced tour pops out at e1=432, and degree bookkeeping rebuilds A,B,C,E,F,D.
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, ..., e2, ..., f1, f2). 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 search tree.
| # | Question | Official answer |
|---|---|---|
| 2.1 | Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes | b1,c1,d2,c2 |
| 2.2 | Which node represents the optimal tour and what is the cost of the optimal tour? | e1,432 |
| 2.3 | Determine the number of cities in the TSP instance. Enter the number of cities i | 6 |
| 2.4 | Start from city A, what is the path representation of the optimal tour? Enter th | A,B,C,E,F,D,A,D,F,E,C,B |
The Topic in 60 Seconds
BnB keeps OPEN as a priority queue on lower bounds; refining = popping the smallest and pushing its include/exclude children. A node whose forced edges already determine a complete tour is a tour leaf even mid-tree.
Deep-dive: browse the Concepts section for Branch-and-Bound.
2.1 — Refine order → b1,c1,d2,c2
| Step | Pop | Push | OPEN after (sorted) |
|---|---|---|---|
| 1 | a1 (372) | b1 : 372 · b2 : 415 | b1(372), b2(415) |
| 2 | b1 (372) | c1 : 372 · c2 : 410 | c1(372), c2(410), b2(415) |
| 3 | c1 (372) | d1 : 432 · d2 : 397 | d2(397), c2(410), b2(415), d1(432) |
| 4 | d2 (397) | e3 : 446 · e4 : 420 | c2(410), b2(415), e4(420), d1(432), … |
| 5 | c2 (410) | … |
Next four after S0: b1, c1, d2, c2 — exactly the key (note d2's fresh 397 leap-frogging both 410 and 415).
2.2 — Optimal leaf → e1, cost 432
Refining c1 produced d1 (BC, 432); its child e1 (AD) completes a forced tour at 432 — incumbent set. Termination sweep:
- b2 (415 < 432) refines → c3(438), c4(449): both ≥ 432 → pruned unopened.
- e4 (420 < 432) refines → f1(453), f2(447): dead.
- Everything else open (432+, 438, 441, 446, 447, 449, 453…) ≥ incumbent.
⇒ optimal = e1, cost 432.
2.3 — Number of cities → 6
Edge-decision levels on a root-to-leaf chain: AB → CE → BC → AD/AC → BD = 5 levels ⇒
2.4 — Rebuilding the tour → A,B,C,E,F,D
Constraints along a1 → b1(AB) → c1(CE) → d1(BC) → e1(AD):
Degree tally: A:{B,D} ✓ · B:{A,C} ✓ · C:{E,B} ✓ · E:{C} needs one more · D:{A} needs one more · F:{} needs two.
The unbranched edges must supply and :
Tour: A,B,C,E,F,D — the official key prints it concatenated with its reverse (…,D,A,D,F,E,C,B), i.e., the same cycle read from both ends; either single direction describes the identical tour.
Interactive trace — refine queue to optimality
Tricks & Tips
Answers: 2.1 b1,c1,d2,c2 · 2.2 e1,432 · 2.3 6 · 2.4 A,B,C,E,F,D