Of all the challenges in combinatorial optimization, the Traveling Salesman Problem (TSP) stands as a classic benchmark. Think about it: it is deceptively simple to state: given a list of cities and the distances between each pair, find the shortest possible route that visits each city exactly once and returns to the origin city. While the problem is easy to understand, finding the optimal solution is computationally formidable, especially as the number of cities grows. This is where sophisticated algorithms like Branch and Bound come into play, offering a systematic and intelligent way to search through the vast landscape of possible routes without resorting to an exhaustive, brute-force check.
Most guides skip this. Don't Most people skip this — try not to..
Introduction: The Combinatorial Explosion of TSP
Imagine a salesman who needs to visit 10 cities. The number of possible round-trip routes is (10-1)! / 2 = 181,440. This is manageable for a computer. But increase the number of cities to 20, and the possibilities skyrocket to over 60 trillion. Consider this: for 50 cities, the number is astronomical, far beyond the computational capacity of any computer, even the world's fastest supercomputers. This is the curse of dimensionality, or combinatorial explosion.
A naive approach, checking every single permutation, is utterly impractical for all but the smallest instances. And we need a smarter strategy—one that can intelligently discard large portions of the search space without having to examine every possible route. This is the core idea behind the Branch and Bound algorithm Worth keeping that in mind..
The Core Strategy of Branch and Bound
Branch and Bound is not a single algorithm but a general framework for solving complex optimization problems, particularly NP-hard problems like TSP. Its power lies in two fundamental concepts: Branching and Bounding Turns out it matters..
-
Branching: This is the process of dividing the main problem into smaller, more manageable sub-problems. In the context of TSP, branching typically involves making decisions about which edges (routes between cities) to include or exclude in the final tour. As an example, we might branch by deciding that a tour must include the edge from City A to City B, and then create a sub-problem for that scenario. Simultaneously, we create another sub-problem where that edge is forbidden No workaround needed..
-
Bounding: For each sub-problem created by branching, we calculate a lower bound on the length of any complete tour that could be generated from it. This lower bound is a clever estimate of the minimum possible tour length for that particular set of constraints. It's not the actual length (which we don't know yet), but a guaranteed minimum. The key insight is that if the lower bound for a sub-problem is already greater than the length of the best complete tour we have already found (the incumbent), then we can prune that entire sub-problem. We can discard it without further investigation because it cannot possibly lead to a better solution Small thing, real impact..
This cycle of branching and bounding allows the algorithm to explore a tree-like structure of possibilities, but to aggressively prune entire branches that are guaranteed to be suboptimal.
A Concrete Example: The Assignment Problem as a Bound
A common and effective way to implement the bounding step for TSP is to relax the problem into an Assignment Problem. Here's the thing — the Assignment Problem is much easier to solve and asks a slightly different question: "What is the minimum cost way to assign each city to exactly one other city, such that every city has one incoming and one outgoing assignment? Practically speaking, " The solution to this relaxed problem is a set of cycles that cover all cities, but it may not form a single, continuous tour. It could, for instance, result in two or more separate loops.
Because the Assignment Problem is a relaxation (it removes the constraint that the solution must be a single tour), its optimal value is guaranteed to be a lower bound for the true TSP solution. Any valid tour is also a valid assignment, so the minimum cost of a tour cannot be less than the minimum cost of an assignment Most people skip this — try not to..
Let's illustrate with a simple 4-city example. The distance matrix is as follows (with ∞ representing a city not connected to itself):
| From/To | A | B | C | D |
|---|---|---|---|---|
| A | ∞ | 10 | 15 | 20 |
| B | 10 | ∞ | 35 | 25 |
| C | 15 | 35 | ∞ | 30 |
| D | 20 | 25 | 30 | ∞ |
Step 1: Calculate the Initial Lower Bound. We solve the Assignment Problem for this matrix. The optimal assignment is: A → B (cost 10) B → A (cost 10) [This forms a cycle A-B-A] C → D (cost 30) D → C (cost 30) [This forms a cycle C-D-C]
The total cost is 10+10+30+30 = 80. Still, this is not a valid tour because it consists of two separate cycles. The lower bound for the entire problem is 80.
Step 2: Branching. We need to break these cycles. We can branch on an edge. Let's choose to branch on the edge from A to B. We create two sub-problems:
- Sub-problem 1 (S1): Include edge A-B. (We set the cost of A→B to its actual value, 10, and forbid the reverse B→A to prevent a short cycle).
- Sub-problem 2 (S2): Exclude edge A-B. (We set the cost of A→B to ∞).
Step 3: Bounding and Pruning. We now solve the Assignment Problem for each sub-problem.
-
For S1 (A-B included): The optimal assignment might now be A→B (10), B→C (35), C→D (30), D→A (20). The total cost is 10+35+30+20 = 95. This forms a single tour: A-B-C-D-A. We have found a complete, valid tour! We store this as our incumbent solution with a length of 95.
-
For S2 (A-B excluded): We solve the assignment problem with A→B = ∞. The optimal assignment might be A→C (15), C→A (15) [cycle A-C-A], and B→D (25), D→B (25) [cycle B-D-B]. The total cost is 15+15+25+25 = 80. The lower bound for S2 is 80 Worth keeping that in mind..
Step 4: Compare and Decide. We compare the lower bound of S2 (80) with our incumbent solution (95). Since 80 < 95, we cannot prune S2 yet. It still has the potential to lead to a tour shorter than 95. We must continue branching on S2, perhaps by deciding to include or exclude another edge like A-C.
We continue this process. Each time we find a complete tour, we update our incumbent if it's better. Each time a sub-problem's lower bound exceeds the incumbent, we prune it Not complicated — just consistent..
Not obvious, but once you see it — you'll see it everywhere.
Continuing the Search
After the first round of branching we had two open sub‑problems, S1 (edge A‑B forced in) and S2 (edge A‑B forced out).
S1 already yielded a feasible tour of length 95, which became our incumbent (I = 95).
S2’s lower bound of 80 left room for improvement, so we proceeded to tighten it further And that's really what it comes down to..
Branching on the next “dangerous” edge
Inside S2 the assignment still contains two 2‑cycles: A ↔ C and B ↔ D.
To break these cycles we select the cheapest edge of the first cycle – the edge A‑C (cost 15) – and create two child sub‑problems:
| Sub‑problem | Decision on A‑C | Modified cost matrix (relevant entries) |
|---|---|---|
| S2a | Include A‑C | A→C = 15 (fixed), B→A = ∞, D→C = ∞ |
| S2b | Exclude A‑C | A→C = ∞, all other entries unchanged |
Both children inherit the ∞‑penalty for the excluded edge from S2, while the included child also locks the reverse edge C‑A to ∞ to avoid a short 2‑cycle That's the whole idea..
Bounding the children
S2a (A‑C included).
We now solve the assignment problem on the reduced matrix. One optimal assignment is:
- A → C (15) – fixed
- C → A (∞) – forbidden, so C must go elsewhere
- B → D (25) – cheapest remaining for B
- D → B (25) – cheapest remaining for D
Because C cannot return to A, the solver is forced to re‑assign C to another city. The cheapest feasible completion is:
- C → B (35)
- B → D (25) – already used, so B must go to A (∞) – infeasible.
The solver therefore adjusts and finds the following optimal assignment:
- A → C (15)
- C → D (30)
- D → B (25)
- B → A (∞) – again infeasible, so B is reassigned to C (35) and C to A (15) forming a 3‑cycle.
After a brief search the solver returns the minimal feasible assignment:
-
A → C (15)
-
C → D (30)
-
D → B (25)
-
B → A (∞) – infeasible, so the solver back‑tracks and finally settles on:
-
A → C (15)
-
C → B (35)
-
B → D (25)
-
D → A (20)
Total cost = 15 + 35 + 25 + 20 = 95.
Here's the thing — this assignment corresponds to the tour A‑C‑B‑D‑A, which is also length 95. Since it does not beat the incumbent, we keep (I = 95) unchanged, but we record the tour as an alternative feasible solution.
S2b (A‑C excluded).
Now A→C = ∞, so the original 2‑cycle A‑C‑A disappears. The remaining cycles are A‑B‑A (still forbidden by S2) and B‑D‑B. The solver now finds:
- A → B = ∞ (excluded) → A must go to D (20)
- D → A (20) – creates a 2‑cycle A‑D‑A, which is broken by forcing D→C (30)
- C → A (15) – now allowed because A‑C is excluded, but C→A is still possible
- B → C (35)
A feasible optimal assignment is:
- A → D (20)
- D → C (30)
- C → A (15)
- B →
