Students usually have a hard time finding a good way to solve the traveling salesman problem. This is where the Branch and Bound approach comes in. It gives you a smart way to get rid of problematic paths early on and just look at the best ones.
Also Read – Advance Data Structure and Algorithms
What is the Traveling Salesman Problem (TSP)?
It is a classic combinatorial optimization problem. It is classified as NP-hard, which means there is no known polynomial-time solution that works for all cases. In graph theory, the cities are the nodes and the paths between them are the edges that show distance or cost.
The main goal is to find a Hamiltonian cycle with the least amount of weight. A Hamiltonian cycle is a path that starts and finishes at the same vertex and visits each vertex just once. Because the number of permutations for n cities is (n-1)! / 2 for a symmetric graph, a 20-city problem would result in trillions of possibilities.
Branch and Bound in the Traveling Salesman Problem
Branch and Bound is a way to develop algorithms that is used only for discrete and combinatorial optimisation issues.. Unlike a simple backtracking approach that explores all possibilities, it uses a “bounding” function to estimate the minimum cost of completing a path from a specific node.
In the context of the TSP algorithm, we use a state-space tree. Each node in this tree represents a partial solution.
- Branching: We split the problem into smaller sub-problems (choosing the next city).
- Bounding: We calculate a “lower bound” for each node. If the lower bound of a branch is already higher than the best solution found so far, we “prune” that branch and stop exploring it.
Lower Bound in the Traveling Salesman Problem
To understand why Branch and Bound works efficiently, we need a mathematical way to estimate the minimum possible cost of completing a tour.
One common approach is the following:
- Lower Bound = ½ × (sum of the two minimum cost edges for each city)
Why divide by 2?
Each city must have exactly two edges in a complete tour (one incoming and one outgoing). Since every edge gets counted twice across cities, we divide the total by 2.
This offers us a fixed minimum cost that any eligible route must have. This helps us cut out paths that aren’t useful early on.
Also Read – Introduction to Red-Black Tree
First Min and Second Min in Traveling Salesman Problem Algorithm
We use two related notions to quickly find the lower bound:
- firstMin(i): The lowest cost of an edge from city i
- secondMin(i): The second lowest cost of an edge from city i
These numbers help figure out how much each city needs to contribute to the whole route.
For example, if the margins from city A are [10, 15, 20]:
firstMin = 10 secondMin = 15
You utilise these variables to figure out both the initial and modified bounds while you are traversing.
Also Read – Geometric Algorithms
Traveling Salesman Problem Solution
To solve the TSP using Branch and Bound, we generally follow a structured mathematical approach. This is how the logic works:
1. The Cost Matrix
We begin with an adjacency matrix in which the value at [i][j] denotes the expense of traversing from city i to city j. The cost is set to infinity if there is no path.
2. Reducing the Matrix
We do row and column reductions to determine the first lower bound:
- Row Reduction: For each row, take away the smallest number from every number in that row. The sum of these minimum elements is added to the total cost.
- Column Reduction: After row reduction, subtract the minimum element of each column from every element in that column. Again, add these values to the cost.
- Result: The sum of all subtracted values gives us the initial lower bound for the root node.
3. State Space Tree Exploration
From the starting city, we move to every other possible city. For each move, we create a new reduced matrix and calculate its cost.
- Cost Calculation: Cost of child node = Cost of parent + Cost of edge (i, j) + Reduction cost of the new matrix.
- Pruning: We throw away the child if its cost is higher than the lowest path we have found so far.
How Lower Bound is Updated in Traveling Salesman Problem Algorithm
The lower bound is adjusted in real time as we look at the state-space tree.
At the first level:
- New Bound = Old Bound – (firstMin(u) + firstMin(v)) / 2 + cost(u, v)
At deeper levels:
- New Bound = Old Bound – (secondMin(u) + firstMin(v)) / 2 + cost(u, v)
Where:
u is the present city and v is the following city.
This keeps our estimate accurate and helps us cut down on pathways that aren’t the best early on.
Also Read – Randomized Algorithm
Comparison of Traveling Salesman Problem Methods
There are many strategies to deal with the TSP. The table below highlights why Branch and Bound is often preferred over simple recursion or dynamic programming for certain constraints.
| Feature | Brute Force | Dynamic Programming | Branch and Bound |
| Complexity | O(n!) | O(n^2 * 2^n) | O(Exponential in worst case) |
| Optimal Solution | Always | Always | Always |
| Approach | Exhaustive search | Overlapping sub-problems | State-space pruning |
| Memory Usage | Low | High | Medium to High |
| Efficiency | Very Low | Moderate | High (with good pruning) |
Implementation of the TSP Algorithm
When writing an algorithm using Branch and Bound, the state is usually maintained in a priority queue. This is known as “best-first search”.
- Structure of the Node: Each node keeps track of the current city, the reduced matrix, the current path, and the current cost.
- Priority Queue: We always grow the node with the lowest bound first. This makes it easier to locate the best or almost best solution early on, which makes it easier to cut off additional branches.
- Path Completion: After we have been to all n cities, we add the cost of getting back to the start city and update our global minimum cost.
Traveling Salesman Problem Algorithm (Pseudocode)
- Use firstMin and secondMin to find the first lower bound.
- Start at city 0 and cross it off your list of places to visit.
- 3. Explore all available cities again and again:
- Change the current cost
- Change the lower limit
- If (current cost + bound < best cost):
Recur for the following level
- Other:
Cut back this branch
- When all of the cities have been visited:
Add the cost of returning to the starting city.
Change the minimum cost
This organised method makes sure we only look into paths that are likely to lead to success, which makes the process faster than brute force.
Why Use Branch and Bound for TSP?
The best thing about this strategy is that it can overlook big parts of the search space. We don’t need to see the end of a road to know it’s a bad decision in a normal solution.
Imagine you are traveling from London to Manchester. If the first leg of your journey already costs more than a known complete route through London-Leeds-Manchester, there is no reason to continue calculating the rest of that specific path. Branch and bound formalises this intuition.
Key Factors for Performance:
- Initial Bound: The tighter the initial lower bound, the more branches we can prune.
- Branching Strategy: Choosing which city to visit next can impact how quickly we find the global minimum.
- Matrix Reduction: This is the most common way to calculate the lower bound in the TSP.
Example of Traveling Salesman Problem Solution
Consider a 4-city problem. If our first row has values [10, 20, 30, 15], the minimum value is 10. After row reduction, the row becomes [0, 10, 20, 5]. We add 10 to our lower bound. We do this for each column and row. This “normalised” matrix shows the relative costs, and the sum of the values that were taken away establishes a baseline cost that any legitimate tour must achieve.
Limitations of the Traveling Salesman Problem (TSP)
Even though this Branch and Bound approach is much faster than brute force, it still has the “state explosion” problem. When there are more than 40 or 50 cities, the memory needed to keep the state-space tree in a priority queue can get very big. When this happens, developers often use approximation methods like genetic algorithms or ant colony optimisation. However, these do not guarantee the shortest path like Branch and Bound does.
FAQs
Is the TSP solution always optimal when using Branch and Bound?
Yes, Branch and Bound is a precise algorithm. It looks at or takes into account all possible paths, which is different from heuristic methods, to make sure that the final result is the shortest route.
What is the main difference between TSP's backtracking and Branch and Bound?
Backtracking uses a depth-first search approach and only cuts off paths based on the cost of the current path. Branch and Bound cuts off branches significantly earlier in the search tree by using a lower bound estimate, which is commonly done by reducing the matrix.
How does the TSP algorithm handle unreachable cities?
In the adjacency matrix, cities or paths that can't be accessed obtain an infinite value. This makes sure that the algorithm's cost-calculation logic doesn't use these paths by itself.
Why is the TSP called NP-hard?
It is called NP-hard because there is no known algorithm that can solve every instance of the problem in polynomial time. As the number of cities (n) increases, the time required to solve it grows at an extremely fast rate.
Can I use Branch and Bound for a large TSP with 1000 cities?
In practice, no. For 1000 cities, the memory and time required for Branch and Bound would be astronomical. For such large scales, professional strategists use "approximation algorithms" or "heuristics", which provide a "good enough" path very quickly.