Branch and Bound - Travelling Salesman Problem (TSP)
Branch and Bound
Branch and Bound is an algorithm design technique used mainly for solving optimization problems.
It is particularly useful when we have a very large number of possible solutions and we want to find the best solution.
A classic example is the Travelling Salesman Problem (TSP).
1. Basic Idea
Suppose we want to find the minimum-cost solution.
Instead of checking every possible solution, Branch and Bound does the following:
Branch: Divide the problem into smaller choices.
Bound: Calculate a lower/upper bound for each choice.
Prune: If a choice cannot possibly produce a better solution than the best solution already found, discard it.
The basic idea is:
Problem | --------------------- | | Choice 1 Choice 2 | | Calculate Calculate bound bound | | Promising? Promising? / \ / \ Yes No Yes No ↓ × ↓ × Explore Explore
The × branches are pruned.
2. Why Do We Need Branch and Bound?
Consider a problem with 10 cities.
The number of possible tours is very large.
Checking every possible tour would be expensive.
Branch and Bound tries to avoid unnecessary work.
For example, suppose we have already found a tour costing:
100Now consider a partial tour whose minimum possible final cost is already:
120There is no reason to explore this branch because even its best possible completion costs 120, which is worse than our current solution of 100.
So we discard it.
Current best = 100 Partial solution | Lower bound = 120 | ↓ Cannot beat 100 | PRUNE
This is the central idea of Branch and Bound.
3. Branching
Branching means dividing the problem into different possibilities.
For example, suppose a salesman starts from city A.
He can choose:
A → B A → C A → D
So we create three branches:
A / | \ B C D
From each of these cities, we again make choices.
For example:
A / | \ B C D / \ / \ / \ C D B D B C
This produces a state-space tree.
4. Bounding
Branching alone is just exhaustive search.
The important additional idea is bounding.
For every partial solution, we calculate a value called a bound.
For a minimization problem:
The bound represents the best possible cost that this partial solution could achieve.
Usually, this is a lower bound.
Suppose:
Current best solution = 80
and we have:
| Branch | Lower Bound |
|---|---|
| A → B | 65 |
| A → C | 90 |
| A → D | 72 |
Since we want to minimize the cost:
-
A → B: 65 < 80 → explore -
A → C: 90 > 80 → prune -
A → D: 72 < 80 → explore
So we don't waste time exploring A → C.
5. Branch and Bound vs Backtracking
These two techniques are closely related, but they are not exactly the same.
| Backtracking | Branch and Bound |
|---|---|
| Mainly used for constraint problems | Mainly used for optimization problems |
| Checks whether a partial solution is valid | Calculates a bound on the possible solution |
| Rejects invalid solutions | Rejects solutions that cannot improve the current best |
| Example: N-Queens | Example: TSP |
| Uses promising/non-promising test | Uses bound and best-known solution |
A simple way to remember:
Backtracking asks: "Is this choice valid?"
Branch and Bound asks: "Can this choice possibly give me a better solution?"
6. Control Abstraction of Branch and Bound
A control abstraction is a general framework showing how a Branch and Bound algorithm operates.
For a minimization problem, the basic procedure is:
BRANCH-AND-BOUND() create the initial state calculate its bound put the state into a list of live nodes while live nodes are not empty select a live node if its bound is worse than the current best discard the node else branch the node into smaller problems for each child calculate its bound if child can improve the current best add child to live nodes otherwise discard child
The important terms are:
Live node
A partial solution that may still lead to an optimal solution.
Dead node
A node that will no longer be explored.
It may be dead because:
- it already represents a complete solution, or
- its bound shows that it cannot improve the current best solution.
Bound
An estimate of the best possible solution that can be obtained from a node.
Best solution
The best complete solution found so far.
7. Travelling Salesman Problem
The Travelling Salesman Problem (TSP) is one of the most famous optimization problems.
Problem
Suppose there are n cities.
A salesman must:
- Start from a particular city.
- Visit every other city exactly once.
- Return to the starting city.
- Minimize the total travelling cost.
For example:
B /|\ / | \ A-----C \ | / \| / D
We need to find the cheapest tour such as:
A → B → C → D → A
or
A → C → B → D → A
and so on.
8. Simple TSP Example
Consider four cities:
A, B, C, D
Suppose the travelling costs are:
| From/To | A | B | C | D |
|---|---|---|---|---|
| A | — | 10 | 15 | 20 |
| B | 10 | — | 35 | 25 |
| C | 15 | 35 | — | 30 |
| D | 20 | 25 | 30 | — |
We start from A.
One possible tour is:
Cost:
Another tour:
Cost:
So we already have a solution with cost:
80This is our current best solution.
9. Building the State-Space Tree
Starting from A:
A / | \ B C D
Suppose we explore:
A → B
From B, we can go to C or D:
A / \ B ... / \ C D
So we get:
A → B → C A → B → D
We continue branching until all cities have been visited.
10. Where Does Bounding Help?
Suppose we already have:
Best complete tour = 80
Now consider the partial tour:
A → C
Suppose the calculated lower bound for completing this tour is:
90Since we are looking for the minimum:
Therefore:
A → C | Bound = 90 | ↓ Cannot beat 80 | PRUNE
We don't explore any of the possibilities below A → C.
This can save a huge amount of computation.
11. What Is the Bound in TSP?
The exact method used to calculate the bound can vary.
A simple idea is:
Estimate the minimum possible additional cost required to complete the partial tour.
For example:
Partial tour cost = 40 Minimum possible remaining cost = 35 Lower bound = 40 + 35 = 75
If our current best solution is:
80
then:
So this branch is still promising.
But if:
Partial tour cost = 50 Minimum possible remaining cost = 40 Bound = 90
then:
so the branch can be pruned.
12. TSP Branch and Bound Algorithm
A simple version can be written as:
TSP-BRANCH-AND-BOUND() start from city A bestCost = infinity create the initial node calculate its bound insert the node into the live-node list while live-node list is not empty select a node if node.bound >= bestCost discard node else if all cities have been visited calculate total tour cost if total cost < bestCost bestCost = total cost save this tour else generate possible next cities for each possible city create a child node calculate its bound if child.bound < bestCost add child to live-node list else discard child return best tour
Example :
13. A Simple View of Least-Cost Branch and Bound
Start / | \ 70 55 80 ↑ choose this
The algorithm chooses the node that currently looks most promising.
Then it branches that node further.
14. General Control Abstraction
For undergraduate students, you can remember Branch and Bound using this simple template:
START | BRANCH | ----------------- | | | Node1 Node2 Node3 | | | Bound Bound Bound | | | Good? Good? Good? / \ \ YES NO YES | X | Explore Prune Explore
The whole process is:
Branch→Bound→Prune→Explore15. Complexity of TSP
The Travelling Salesman Problem is computationally difficult.
A brute-force method considers approximately:
tours when the starting city is fixed.
Therefore, its worst-case complexity is:
O(n!)Branch and Bound can greatly reduce the number of nodes actually explored by pruning branches.
However, in the worst case, Branch and Bound may still need to explore an exponential/factorial number of possibilities.
Therefore:
Worst-case complexity of TSP Branch and Bound remains exponential/factorial.The advantage is that pruning can make the actual execution much faster for many practical instances.
16. Backtracking vs Branch and Bound – Easy Example
Imagine you are looking for the cheapest route.
Backtracking
Can I continue this route? ↓ YES → Continue NO → Backtrack
Branch and Bound
Can this route possibly become cheaper than my current best route? ↓ YES → Continue NO → Prune
So:
Backtracking focuses on feasibility.
Branch and Bound focuses on optimization.
17. Applications of Branch and Bound
Branch and Bound is useful in many optimization problems:
- Travelling Salesman Problem
- 0/1 Knapsack Problem
- Job Assignment Problem
- Scheduling problems
- Combinatorial optimization
- Vehicle routing problems
18. Quick Summary
| Concept | Meaning |
|---|---|
| Branch | Divide a problem into smaller choices |
| Bound | Estimate the best possible result from a choice |
| Live node | Node that may still produce a better solution |
| Dead node | Node that will not be explored further |
| Pruning | Discarding a node using its bound |
| Current best | Best complete solution found so far |
| TSP | Find the minimum-cost tour visiting every city once |
| Worst case | Still exponential/factorial |
| Main advantage | Avoids exploring unpromising branches |
One-line definition
Branch and Bound is an optimization technique that systematically explores possible solutions while using bounds to eliminate branches that cannot produce a better solution.
For TSP, the idea is simply:
Comments
Post a Comment