1 BRANCH AND BOUND ALGORITHM 2 FOR TSP WITH ANY COST MATRIXIn the first column published in the March/April, 2003 issue, a branch and bound algorithm that involves generating nodes that represent partial tours with constraints was presented and implemented. The computational cost as well as the memory overhead required to generate each node was shown to be significant. Furthermore, the algorithm assumes that the cost matrix that specifies the cost of traveling from one city to another is symmetric. All of these problems are overcome using the algorithm to be presented and implemented in this column. An alternative branchandbound that works for a cost matrix of any
type (no requirement that it be symmetric as is the case for the first
algorithm) is based on the following: The algorithm proceeds by starting with a root node (level 1) and
a partial tour of [1]. Then all the nodes at level 2 are generated.
For each of these nodes a lower bound is computed (details to be shown
below). The node with the smallest lower bound is used to generate nodes
at level 3. After the lower bounds for each of these nodes are computed,
level four nodes are generated from the level 3 node with smallest lower
bound. This process of rapid descent down the tree continues until nodes
that represent full tours at level n are produced. The lowest cost node
at level n is used to prune nodes as the depthfirst algorithm backtracks
up the tree and generates more nodes at the lowest level possible. Let us examine the mechanism for computing a lower bound for each node
in the tree described above. In any tour the length of an edge taken
when leaving a city must be at least as large as the length of the shortest
edge emanating from that city. This leads to a branch and bound algorithm
as shown with the example that follows.
To compute the lower bound on the root node with partial tour [1], we reason as follows: The lower bounds on the costs of leaving the five verticies (cities) are:
The lower bound is the sum of these minimums which equals 21. Suppose we consider the process for another more complex node, say the node that represents the partial tour [1, 2, 3].
The lower bound is therefore 34. It should be clear from this example that the cost of computing each lower bound is quite low. Furthermore the storage required in each node is minimal compared to the storage required using the constrained tour approach presented in the previous column. This offers the hope of generating significantly more nodes per unit time. A key issue in implementing the branch and bound algorithm outlined above is how to represent the tree structure. Since at a given level nodes may be ranked by their computed lower bound, a priority queue may be used to hold the tree structure. Using such a priority queue, the algorithm may be formulated as follows:
This algorithm follows a bestfirst branch and bound descent of a tree (like the first algorithm). Before a node is inserted into the priority queue it is screened to determine that its lower bound is less than the currently known best tour. This helps to assure that the number of nodes being held in this priority queue is manageable. What priority rules must the queue enforce? First, nodes at a deeper
level (higher level number) have priority over nodes at a shallower
level. This assures that the tree grows downwards and that leaf nodes
representing complete tours are generated as quickly as possible. In
comparing two nodes at the same level, priority is given to the node
with the smallest lower bound. In the event of a tie (two nodes with
equal lower bound), the sum of the cities in the partial tour is computed.
The node with the smaller sum is given a higher priority than the node
with the larger sum (a tie cannot occur). It should be evident that
the rules just stated disallow two distinct nodes from having an equal
priority. 2 IMPLEMENTATIONIn searching among the huge number of classes provided in the Java API, there is no class priority queue class. But there is a standard Java collection class that is close in behavior – class TreeSet. This collection class orders its elements (which must implement the interface Comparable) based on the definition of the compareTo method. It is in this method that we encapsulate the rules given above for the priority queue. Listing 1 presents the details of this method compareTo (in class Node). Listing 1 – Method compareTo Each of the rules stated above are included in this compareTo method. When nodes are added to a TreeSet, they will be ordered according to the logic given above. The entire class Node is presented in Listing 2. Listing 2 – Class Node
An examination of the field structure of this class reveals how much lighter it is than the corresponding class Node in the previous implementation. Class TSP, in Listing 3, implements the algorithm presented earlier. Methods read and write support object persistence. This allows a computation session to be ended and the state of the system preserved on disk in a file OnGoing.data. When the next session begins this data file may be used to restore the state of the system to where it last was when the previous session ended. Java’s object persistence through serializability is used to accomplish this. The details are shown in Listing 3. Listing 3 – Class TSP
3 EMPIRICAL RESULTSLike with the first implementation presented in the previous column, a GUI is constructed that enables the user to perform experiments. If the 33 city problem used in the previous column is loaded, the implementation presented above must generate 4.191 billion nodes (4,191,003, 606 nodes) before finalizing the same solution with cost 10,861. It takes the same computer (Pentium 4, 1.7 GHz processor with 256M RAM and running under Windows 2000) 24,170 seconds (6 hours, 42 minutes and 50 seconds) to find this solution. The priority queue size during this long computation never exceeds several hundred nodes – a testimony to the efficacy of pruning. The rate of generation of nodes is about 167,000 nodes per second (significantly faster than the several hundred nodes per second produced using the previous algorithm). Before reaching the conclusion that this algorithm is less efficient at obtaining a solution than the previously presented solution, let us examine another problem – a 24 city problem. The cost matrix is generated randomly and saved. Using this algorithm, it takes 4 minutes and 59 seconds and close to 52 million nodes (52,958,736) to finalize a solution. Using the previous algorithm with constrained nodes, it takes 2619 seconds (43.65 minutes) and 588,253 nodes to finalize the same solution. These two data points immediately suggest the desirability of using each of the implementations on a given problem since it is not known in advance which of the two (if either) will find a solution in a reasonable time. On the same 20 city problem with random costs, the algorithm presented
in this column took 22 seconds and 5,041,269 nodes and the nodeconstrained
previous algorithm took 113.8 seconds and 88807 nodes. Once again the
algorithm presented above outperformed the previous algorithm this time
by a factor of 6 to 1. About the author

Richard Wiener is Associate
Professor of Computer Science at the University of Colorado at Colorado
Springs. He is also the EditorinChief of JOT and former EditorinChief
of the Journal of Object Oriented Programming. In addition to University
work, Dr. Wiener has authored or coauthored 21 books and works
actively as a consultant and software contractor whenever the possibility
arises. 
Cite this column as follows: Richard Wiener: "Branch and Bound Implementations for the Traveling Salesperson Problem – Part 2”, in Journal of Object Technology, vol. 2, no. 3, MayJune 2003, pp. 6576. http://www.jot.fm/issues/issue_2003_05/column7