TSP 4-Cities Branch & Bound

Distance matrix symmetric, start A:
$$\begin{array}{c|cccc} &A&B&C&D\\\hline A&0&10&15&20\\ B&10&0&35&25\\ C&15&35&0&30\\ D&20&25&30&0 \end{array}$$
Brute force $(n-1)!/2 =3$ unique tours from A:

• A-B-C-D-A: 10+35+30+20=95
• A-B-D-C-A: 10+25+30+15=80
• A-C-B-D-A: 15+35+25+20=95
• A-C-D-B-A: 15+30+25+10=80
• A-D-B-C-A: 20+25+35+15=95 etc → Optimum 80 (A-B-D-C-A or A-C-D-B-A reverse).

Branch & Bound (lower bound = sum of two smallest edges per node /2, or reduced matrix)

Simple bound: For partial path, LB = cost so far + sum of min outgoing edges for unvisited nodes + min return edge.

Root (path [A]): cost 0, LB = (10+15)/2? Let's compute 1-tree bound: Two smallest per node: A10,15 B10,25 C15,30 D20,25 → sum=140/2=70 initial LB=70.

Branch level1:

• A→B: cost10, remaining {C,D} mins: C min15 (to A) or30, D min20or25 → LB≈10+ (15+20)+? =80? Detailed: path A-B cost10 + min B->?35? Actually B visited, next mins C15+30, D20+25. Compute reduced cost 10+15+20=45 + return? Approximates 80.
• A→C: cost15 similar LB ~80
• A→D: cost20 LB ~85

Expand A→B node:

• A-B-C: cost10+35=45 → need D → min C→D30 + D→A20 =45+30+20=95
• A-B-D: cost10+25=35 → need C → min D→C30 + C→A15 =35+30+15=80 (best)

Expand A-B-D-C-A: cost35+30=65+15=80 feasible, update best=80, prune branches with LB ≥80 (e.g., A-B-C-D-A =95 pruned after comparison).

Similarly A-C branch yields also 80 via A-C-D-B-A.

Bounding Effect

Without bounding, explore 3!=6 permutations from A. With bound, once best=80 found, any partial with LB≥80 is pruned: e.g., after exploring A-B-C (LB95), don't expand further; A-D branch LB85 pruned if tight. Reduces explored nodes from 15 to ~6 in 4-city case; dramatic for larger $n$.

Answer: Optimal tour A → B → D → C → A (or reverse A → C → D → B → A) cost 80. Branch-and-bound prunes subtrees where lower bound ≥ current best (80), avoiding exhaustive enumeration.

Time still worst $O(n!)$ but pruning often cuts huge fraction.