Branch and Bound Travelling Salesman Problem
Travelling Salesman Problem is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.
Branch and Bound
 Set up a bounding function, which is used to compute a bound (for the value of the objective function) at a node on a statespace tree and determine if it is promising.
 Promising (if the bound is better than the value of the best solution so far): expand beyond the node.
 Nonpromising (if the bound is no better than the value of the best solution so far). Not expand beyond the node (pruning the statespace tree).
Traveling Salesman Problem
Construct the statespace tree:
 A node = a vertex: a vertex in the graph. A node that is not a leaf represents all the tours that start with the path stored at that node; each leaf represents a tour (or nonpromising node).
 Branchandbound: we need to determine a lower bound for each node.
 For example, to determine a lower bound for node [1, 2] means to determine a lower bound on the length of any tour that starts with edge 1—2.
 Expand each promising node, and stop when all the promising nodes have expanded. During this procedure, prune all the nonpromising nodes.
 Promising node: the node’s lower bound is less than current minimum tour length.
 Nonpromising node: the node’s lower bound is NO less than current minimum tour length.
 Because a tour must leave every vertex exactly once, a lower bound on the length of a tour b (lower bound) minimum cost of leaving every vertex.

The lower bound on the cost of leaving vertex v_{1} given by the minimum of all the nonzero entries in row 1 of the adjacency matrix.
 The lower bound on the cost of leaving vertex v_{n} given by the minimum of all the nonzero entries in row n of the adjacency matrix.
 Because every vertex must entered and exited exactly once, a lower bound on the length of a tour is the sum of the minimum cost of entering and leaving every vertex.
 For a given edge (u, v), think of half of its weight as the existing cost of u. And half of its weight as the entering cost of v.
 The total length of a tour = the total cost of visiting (entering and exiting) every vertex exactly once.
 The lower bound of the length of a tour = the lower bound of the total cost of visiting (entering and exiting) every vertex exactly once.
 Calculation:
 For each vertex, pick top two shortest adjacent edges. (their sum divided by 2 is the lower bound of the total cost of entering and exiting the vertex); add up these summations for all the vertices.
 Assume that the tour starts with vertex a and that b visited before c.
Related Terms
ADA Algorithms, Back Tracking, Knapsack Problem using Backtracking, Minmax Principle
Leave a Reply