L26 Travelling Salesman Problem Using B and B

DAA (Unit-5)
Solving problems using

Branch and Bound Algorithm
By
Dr. Ratnesh Litoriya
Medi-Caps University, Indore (M.P.)
5/6/2023
 In computer science, there is a large number of optimization
problems which has a finite but extensive number of feasible
solutions. Among these, some problems like finding the
shortest path in a graph or Minimum Spanning Tree can be
solved in polynomial time.
 A significant number of optimization problems like production
planning, crew scheduling can’t be solved in polynomial time,
and they belong to the NP-Hard class. These problems are
the example of NP-Hard combinatorial optimization problem.
 Branch and bound (B&B) is an algorithm paradigm widely
used for solving such problems.
2
 Branch and bound is one of the algorithm design
techniques used for problem solving.
 It is similar to the backtracking since it also uses the
state space tree.
 It is used for solving the optimization problems and
minimization problems.
 If we have given a maximization problem then we can
convert it using the Branch and bound technique by
simply converting the problem into a maximization
problem.
3
 Branch and bound is generally used for solving
combinatorial optimization problems.
 These problems are typically exponential in terms of time
complexity and may require exploring all possible
permutations in worst case.
 The Branch and Bound Algorithm technique solves these
problems relatively quickly.
4
Travelling Salesman Problem | Branch & Bound
 You are given-

 A set of some cities
 Distance between every pair of cities
 Travelling Salesman Problem states-

 A salesman has to visit every city exactly once.
 He has to come back to the city from where he starts his
journey.
 What is the shortest possible route that the salesman
must follow to complete his tour?
5
 Example
If salesman starting city is A, then a TSP tour in the graph

is-
A→B→D→C→A
Cost of the tour
= 10 + 25 + 30 + 15
= 80 units 6
 working example
7
Solution
Step-01:
Write the initial cost matrix and reduce it-
Rules
To reduce a matrix, perform the row reduction and column reduction of
the matrix separately.
A row or a column is said to be reduced if it contains at least one entry
‘0’ in it.
Solution
Row reduction
Performing this, we obtain the above row-reduced matrix-

Solution
Column reduction
Consider the columns of above row-reduced matrix one by one

we obtain the following column-reduced matrix-.
Solution
Finally, the initial distance matrix is completely
reduced.
Now, we calculate the cost of node-1 by
adding all the reduction elements.
Cost(1)
= Sum of all reduction elements
= 4 + 5 + 6 + 2 + 1
= 18
Solution
Step-02
 We consider all other vertices one by one.
 We select the best vertex where we can land upon to minimize the tour
cost.
 Choosing To Go To Vertex-B: Node-2 (Path A → B)
 From the reduced matrix of step-01, M[A,B] = 0
 Set row-A and column-B to ∞
 Set M[B,A] = ∞
 Now, resulting cost matrix is-
Now,
We reduce this matrix.
Then, we find out the cost of node-02.
Solution
The reduced matrix is given here.

Now, we calculate the cost of node-2.
Cost(2)
= Cost(1) + Sum of reduction
elements + M[A,B]
= 18 + (13 + 5) + 0
= 36
Solution
 Choosing To Go To Vertex-C: Node-3 (Path A → C)
From the reduced matrix of step-01,

M[A,C] = 7
Set row-A and column-C to ∞
Set M[C,A] = ∞
Now, resulting cost matrix is-
Now,
Solution
Cost(3)
elements + M[A,C]
= 18 + 0 + 7
= 25
Solution
 Choosing To Go To Vertex-D: Node-4 (Path A → D)

M[A,D] = 3
Set row-A and column-D to ∞
Set M[D,A] = ∞
Now,
Solution
The reduced matrix is given here.

Cost(4)
elements + M[A,D]
= 18 + 5 + 3
= 26
Solution
Thus, we have-
Cost(2) = 36 (for Path A → B)
Cost(3) = 25 (for Path A → C)
Cost(4) = 26 (for Path A → D)
We choose the node with the lowest cost.

Since cost for node-3 is lowest, so we
prefer to visit node-3.
Thus, we choose node-3 i.e. path A → C.
Solution
Step-03:
We explore the vertices B and D from

node-3.
We now start from the cost matrix at
node-3 which is-
Solution
Choosing To Go To Vertex-B: Node-5
(Path A → C → B)

M[C,B] = ∞
Set row-C and column-B to ∞
Set M[B,A] = ∞
Now,
Solution
Finally, the matrix is completely

reduced.
Cost(5)
= cost(3) + Sum of reduction elements
+ M[C,B]
= 25 + (13 + 8) + ∞
=∞
Solution
Choosing To Go To Vertex-D: Node-6
(Path A → C → D)

M[C,D] = ∞
Set row-C and column-D to ∞
Set M[D,A] = ∞
Now,
Solution
Thus, the matrix is already reduced.
Cost(6)
= cost(3) + Sum of reduction elements +
M[C,D]
= 25 + 0 + 0
= 25
Solution
Thus, we have-
Cost(5) = ∞ (for Path A → C → B)
Cost(6) = 25 (for Path A → C → D)
We choose the node with the lowest cost.

Since cost for node-6 is lowest, so we prefer to
visit node-6.
Thus, we choose node-6 i.e. path C → D.
Solution
Step-04:
We explore vertex B from node-6.
We start with the cost matrix at node-6
which is-
Solution
Choosing To Go To Vertex-B: Node-7
(Path A → C → D → B)

M[D,B] = 0
Set row-D and column-B to ∞
Set M[B,A] = ∞
Now,
Solution
Finally, the matrix is already completely reduced.
All the entries have become ∞.
Cost(7)
= cost(6) + Sum of reduction elements + M[D,B]
= 25 + 0 + 0
= 25
Thus,
Optimal path is: A → C → D → B → A
Cost of Optimal path = 25 units
Time Complexity
Traveling salesman problem is a NP-hard problem.
Until now, researchers have not found a polynomial
time algorithm for traveling salesman problem.
 Among the existing algorithms, dynamic
programming algorithm can solve the problem in
time O(n^2*2^n) where n is the number of nodes in
the graph.
The branch-and-bound algorithm has been applied
to solve the problem with a large number of nodes.
 However, branch-and-cut algorithm also has an
exponential worst-case running time.

L26 Travelling Salesman Problem Using B and B

Uploaded by

Copyright:

Available Formats

L26 Travelling Salesman Problem Using B and B

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

L26 Travelling Salesman Problem Using B and B

Uploaded by

Copyright:

Available Formats

DAA (Unit-5)

Solving problems using

 You are given-

 Travelling Salesman Problem states-

If salesman starting city is A, then a TSP tour in the graph

Performing this, we obtain the above row-reduced matrix-

Consider the columns of above row-reduced matrix one by one

The reduced matrix is given here.

From the reduced matrix of step-01,

Now, resulting cost matrix is-

Now, we calculate the cost of node-3.

From the reduced matrix of step-01,

Now, resulting cost matrix is-

The reduced matrix is given here.

We choose the node with the lowest cost.

We explore the vertices B and D from

From the reduced matrix of step-02,

Now, resulting cost matrix is-

Finally, the matrix is completely

From the reduced matrix of step-02,

Now, resulting cost matrix is-

We choose the node with the lowest cost.

From the reduced matrix of step-03,

Now, resulting cost matrix is-

You might also like