Research interests

Here is the outline for the parallelization research.

• Introduction
• Held and Karp's 1-tree relaxation
• Lagrangean cost function
• Why use Prim's algorithm?
• Computational experience
• Things to do

Introduction

I'm particularly interested in finding out the best way to parallelize branch and bound codes that use Held and Karp's 1-tree relaxation. These are of interest because this relaxation is the basis for the most efficient sequential algorithms known for solving symmetric TSPs. This is according to Balas and Toth's survey in The Traveling Salesman Problem, edited by Lawler et al., 1985. It is always a good idea to start one's work with the best algorithm known so far.

Branch and bound algorithms based on 1-trees are also notable because the search trees they generate are very small. For instance, Smith and Thompson report that on problems of size 42, 48, 57, and 100 their algorithm generates 7, 7, 34, and 95 branch and bound search nodes, respectively. (Most of the time is spent computing many minimum 1-trees per branch and bound node.) Compare this with the thousands of nodes generated on a problem of size 48 when using the LMSK algorithm reported by Abdelrahman in 1994.

It therefore seems worthwhile to study the profitability of using many processors per branch and bound node. Abdelrahman calls this subproblem-level parallelism. I want to gain experience with exploiting parallelism at this level, especially in using the 1-tree framework where it appears to be most promising.

Held and Karp's 1-tree relaxation

Notice that any tour of G qualifies as a 1-tree for G. It follows then that the length of a shortest 1-tree of G is a lower bound on the length of a shortest tour of G. A minimum cost 1-tree for G can be found by computing a minimum spanning tree for (V\{1},E) and by scanning for the two shortest edges incident upon vertex 1. There are efficient algorithms for these two steps. This is the basis for the use of the 1-tree relaxation in branch and bound codes for the TSP.

Lagrangean cost function

Unfortunately, the length of the minimum 1-tree of a graph is on average only about 60% of the length of the shortest tour of that graph. How can we improve on this? The trick is to use Lagrange multipliers to incorporate some degree constraints. That is, we can add a cost to vertices that have either too many or too few edges.

Instead of computing the minimum 1-tree using the plain cost function c(i,j), use c(i,j)+l(i)+l(j) where l is some real-valued function on the vertices. With some rearrangement and noting that every vertex in a tour is of degree 2, we can show that for any choice of l, L(l) = min 1-tree cost (using c(i,j)+l(i)+l(j))- 2 sum_{i \in V} l(i) <= min tour cost. (Sorry, but HTML isn't TeX.)

Given the right choice of l, this Lagrangean lower bound consistently achieves 99.5% of the minimum tour cost on symmetric instances, and is the basis for the most successful algorithms for the symmetric TSP (up to 1985, according to Balas and Toth).

We use what is called a subgradient optimization method to compute the n-vector l. This is basically a numerical hill-climbing procedure in n dimensions. Some theory has been developed to aid in the choice of step sizes, though there are still some parameters that must be chosen; this is still a black art.

Why use Prim's algorithm?

As suggested by Quinn's parallel programming text, I also implemented Sollin's algorithm. It suffers from two drawbacks. First, it is quite complex; the parallel version would require much fine-grained locking and synchronization. Second, it turns out to be much slower than Prim's algorithm on the (nearly) complete graphs that we encounter. (See my research log book for timing comparisons.)

[Perhaps insert descriptions of Prim's and Sollin's algorithm.]

Computational experience

Minimum spanning trees

I have run experiments to determine the speedup for various problem sizes with various numbers of processors. For small problems (e.g. 51 cities), there is no speedup over a the sequential algorithm. For larger problems, we get some speedup with the best being 60% of optimal speedup for a 3038 city problem on up to 10 processors, taking 8.6 seconds.

Branch and bound code for the TSP itself

• It uses a best-first problem selection strategy. (Thanks to Wayne Hayes for the priority queue routines.)
• It uses geometrically decreasing alpha-step parameter. The exact scheme is original to me, although Volgenant and Jonker mention such a scheme in passing.
• It uses an original set of stopping rules based on the convergence properties of the ascent. I found those of Volgenant and Jonker to be too basic (a fixed number of steps) and those of Smith and Thompson too opaque.
• It uses the branching scheme of Volgenant and Jonker.
• It uses their rule that if two edges are fixed into a vertex, then no other edges should be allowed to be incident upon that vertex in the 1-tree computed.
• It uses a fictitious upper bound: After the initial ascent computes a lower bound for the general graph, an upper bound of 1.015 times that lower bound as an upper bound for the rest of the computation, until an actual tour is found that is less than that. If no such tour is found, then the computation is restarted after the initial ascent using 1.015 times the previously tried upper bound.

            Number  Ascents    Task List Len   1-Trees  
Instance    Cities  Performed  Avg   Std Dev  Computed  Time (in seconds)
----------  ------  ---------  ----  -------  --------  ----
grid25         25         65    16.4    8.6     675      3.7
dantzig42      42        376    67.9   42.5    3635     31.0
hk48           48         13     8.1    3.6     242      2.8
eil51          51        126    92.1   43.6    1706     29.5
st70           70       1854  1294.4  722.8   30412    982.5
eil76          76        373   328.2  189.9    6998    260.5
kroA100       100       9473  2836.1 2004.1  161288  10078.7
eil101        101       1009   291.3   94.7   10028    713.6
lin105        105         26    21.7   11.1     722     54.7
randA50        50         29     3.5    2.6     240      3.0
randB50        50         22     4.3    2.9     257      3.0
randC50        50         23    12.7    7.8     448      5.0
randD50        50         32     6.4    6.0     518      5.9
randA100      100         80    58.7   37.0    2164     89.8
randB100      100        225   172.5   94.6    4987    194.4
randC100      100         36    29.8   17.1     877     33.7
randD100      100         19    16.3    8.6     573     23.9
randA150      150         42    37.1   20.5    1269    134.8
randB150      150         96    76.1   49.0    2872    273.1
randC150      150         46    43.1   24.7    1690    158.1
randB150      150         21    18.7   10.9     726     70.0
randA200      200         26    25.5   14.5     930    159.7
randB200      200        200   184.3  106.7    9157   1540.9
randC200      200         44    36.4   23.2    1962    332.3
randD200      200         30    29.6   16.8    1396    237.3
randA300      300         57    54.3   30.7    2677   1040.9
randB300      300         86    82.5   47.3    6333   2435.4
randC300      300         40    39.2   22.8    1760    699.4
randD300      300        113   107.7   61.1    5611   2162.2
randA1000    1000         90    89.1   51.8    7204  32579.5

Instances beginning with rand have edge lengths which were drawn from a uniform random distribution over [1,1000].

A posting to comp.theory by and email from Jay Herder (jherder at yahoo dot com) prompted an investigation into grid graphs. He was interested in approximate solutions on graphs where with embedded grids as part of a wiring problem. Instance grid25 is a 5 by 5 grid of points spaced 10 units apart. Arbitrary insertion found an optimal tour in this case, suggesting that it is a good heuristic for these kinds of graphs.

All others were taken from the TSPLIB library of instances.

The compiler was GCC 2.5.8 with no optimization under Linux 1.0.8. The machine is an Intel 486 DX2/66 with 256K 20ns cache and 16MB 70ns main memory. For comparison, this machine is about as fast as a single processor on a KSR-1, and about 3 times faster (for this task) than a SPARC IPC.

The program requires little memory: the program and data on instance eil51.tsp take up about 130 kilobytes on the 486, as reported by top(1) under Linux. Note that this fits entirely within the 256K cache, even though I exclusively use the double type for storage and manipulation of the Lagrangean multipliers and edge lengths.

Note, however, that on Euclidean instances, I do not store the entire cost matrix but instead recompute the cost function on the fly from the stored coordinates. This is done to reduce the working set size, especially for larger instances. I experimented with storing the edge costs but found that this slowed down the program by about 5% even on the relatively small 51 city problem. That is, table lookup was slower than recomputation.

Things to do

• Design and test a parallelization of the BB algorithm.