Vamshi Jandhyala - Traveling Salesman Problem

Branch and bound (BB)

Branch and bound is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.

Generic version of the BB algorithm

The following is the skeleton of a generic branch and bound algorithm for minimizing an arbitrary objective function \(f\). To obtain an actual algorithm from this, one requires a bounding function \(\textbf{bound}\), that computes lower bounds of \(f\) on nodes of the search tree, as well as a problem-specific branching rule.

Using a heuristic, find a solution \(x_h\) to the optimization problem. Store its value, \(B = f(x_h)\). (If no heuristic is available, set \(B\) to infinity.) \(B\) will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
Loop until the queue is empty:
1. Take a node \(N\) off the queue.
2. If \(N\) represents a single candidate solution \(x\) and \(f(x) < B\), then \(x\) is the best solution so far. Record it and set \(B ← f(x)\).
3. Else, branch on \(N\) to produce new nodes \(N_i\). For each of these:
  1. If \(bound(N_i) > B\), do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded.
  2. Else, store \(N_i\) on the queue.

Several different queue data structures can be used. This FIFO queue-based implementation yields a breadth-first search. A stack (LIFO queue) will yield a depth-first algorithm. A best-first branch and bound algorithm can be obtained by using a priority queue that sorts nodes on their lower bound. Examples of best-first search algorithms with this premise are Dijkstra’s algorithm and its descendant A* search. The depth-first variant is recommended when no good heuristic is available for producing an initial solution, because it quickly produces full solutions, and therefore upper bounds.

Traveling Salesman Problem (TSP)

The traveling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

Solution to TSP using BB

For the TSP example below we will use a branch and bound best-first search algorithm to find the shortest tour. The cities involved are \(\{c_0,c_1,c_2,c_3,c_4,c_5\}\) and the distance matrix is:

\[ \begin{bmatrix} \infty & 1 & 4 & 5 & 4 & 5 \\\\ 1 & \infty & 6 & 3 & 1 & 6 \\\\ 4 & 6 & \infty & 1 & 1 & 5 \\\\ 5 & 3 & 1 & \infty & 2 & 1 \\\\ 4 & 1 & 1 & 2 & \infty & 5 \\\\ 5 & 6 & 5 & 1 & 5 & \infty \end{bmatrix} \]

One of the minimum length tours given the above distance matrix is \([c_0, c_1, c_4, c_2, c_3, c_5, c_0]\) which has a length of \(10\).

Bounding function

We use the following lower bounding method to evaluate any partial tour. If the TSP instance has \(n\) cities and let \(t = \{c_1, c_2, ..., c_m\}\) be a partial tour. Then a lower bound for the length of a tour containing the given partial tour \(t\) is given by

\[ LB(t) = d(c_1, c_2) + d(c_2, c_3) + ... + d(c_{m−1}, c_m) + n_{left} × d_{min}, \]

where \(n_{left}\) is the number of edges yet needed to complete the tour and \(d_min\) is the length of the smallest edge between any two cities in the instance.

Python code

Here is the Python code which is a straightforward adaptation of the generic version of the BB algorithm to the TSP using priority queue and the bound function described above:

from dataclasses import dataclass, field
from math import inf
from queue import PriorityQueue

def bound(node, dist_mat):
    d_min = min(d for row in dist_mat for d in row)
    n_left = len(dist_mat) - node.level
    return n_left * d_min

def length(path, dist_mat):
    l = 0
    for i in range(len(path[:-1])):
        l += dist_mat[path[i]][path[i+1]]
    return l

@dataclass(order=True)
class Node:
    bound: float
    level: int = field(compare=False)
    path: list = field(compare=False)
    
def tsp_bb(dist_mat):
    opt_tour =  None
    n = len(dist_mat)

    pq = PriorityQueue()
    u = Node(0, 0, [0])
    u.bound = bound(u, dist_mat)
    pq.put(u)

    minlength = inf

    while(not pq.empty()): 
        u = pq.get()

        if u.level == n-1:
            u.path.append(0)
            len_u = length(u.path, dist_mat)
            if len_u < minlength:
                minlength = len_u
                opt_tour = u.path
        else:
            for i in set(range(0, n))-set(u.path):
                u_new = Node(0, u.level + 1, u.path + [i])
                u_new.bound = bound(u_new, dist_mat)
                if u_new.bound < minlength:
                    pq.put(u_new)
    
    return opt_tour, length(opt_tour, dist_mat)

dist_mat = [ 
    [inf, 1, 4, 5, 4, 5],
    [1, inf, 6, 3, 1, 6],
    [4, 6, inf, 1, 1, 5],
    [5, 3, 1, inf, 2, 1],
    [4, 1, 1, 2, inf, 5],
    [5, 6, 5, 1, 5, inf],
]

print(tsp_bb(dist_mat))

References

Branch and Bound