Implementation Report: The Stem-and-Cycle Ejection Chain Algorithm


Cesar Rego (a)
Fred Glover (a)
Dorabela Gamboa (b)

(a) Hearin Center for Enterprise Science, School of Business
Administration, University of Mississippi, University, MS 38677, USA.
{crego,fglover}@bus.olemiss.edu.

(b) Universidade Portucalense, Departamento de Informatica, Rua Dr.
Antonio Bernardino de Almeida 541-619, 4200 Porto, Portugal.
dgamboa@upt.pt

Algorithm description

We consider a local search algorithm based on the stem-and-cycle ejection chain method proposed in Glover (1992). The current implementation of the stem-and-cycle algorithm is a slight variant of the P-SEC algorithm described in Rego (1998).

The algorithm can be briefly described as follows. Given an initial solution the algorithm attempts to improve the current solution iteratively by means of a subpath ejection chain method, which generates moves coordinated by a reference structure called a Stem-and-Cycle (S&C). The stem-and-cycle procedure is a specialized variable depth neighborhood which implements a dynamic alternating path method (as opposed to static alternating paths produced, for example, by the classical Lin-Kernighan approach). The generation of moves throughout the ejection chain process is based on the definition of a set of rules and legitimacy restrictions on the set of edges that are allowed to be used in subsequent steps of an ejection chain. A couple of implementation improvements in the basic algorithm strategy described in Rego (1998) make the current version more efficient and effective for solving very large scale problems.

The principal change is the use of a two-level tree data structure described in Fredman et al. (1993), and used in some of the most efficient Lin-Kernighan implementations (Johnson and McGeoch, 1997; Appelgate and Cook, 2000; and Helsgaun, 1998) reported in this Challenge. In our algorithm the two-level tree data structure was appropriately adapted to replace the less effective doubly-linked lists previously used to represent both the TSP tours and the S&C reference structures. Another modification consisted of replacing a two-dimension array-based data structure by an n-vector to control "legitimacy restrictions" during the ejection chain construction, substantially reducing the storage space required by the earlier version. We also incorporated the possibility for the algorithm to directly access external neighbor lists in the format used by the Concord system, thus providing additional options to the nearest neighbor list used in the P-SEC algorithm.

The algorithm is implemented as a local search improvement method in the sense that no meta-strategy is used to guide the method beyond local optimality. Also, the method always stops after N iterations of the "re-routing" strategy fail to improve the best solution found so far. (Re-routing consists of starting an S&C ejection chain from a different route node.) This makes our implementation of the S&C algorithm simpler than Lin-Kernighan implementations that make use of additional supplementary techniques such as "don't look bits" strategy, caching distances, and other implementation tricks.

Computational results

We have tested our algorithm on the testbed provided in this 8th DIMACS Challenge. We provide results for the algorithm starting from both randomly generated solutions and solutions provided by Boruvka's construction algorithm (available in the Concorde TSP library). Random solutions were generated by the systematic generator used in Rego (1998) using k=2 and k=5 to provide starting solutions for two runs. Runs were carried out on two different computer systems: a SGI Origin 2000 with six 300 MHz R12000 processors and 24 GB of memory; a Sun Enterprise 3500 with two 400MHz Ultra Sparc processors and 1 GB of memory. (See http://www.mcsr.olemiss.edu/ for more detail on the characteristics of these machines.) Although these are multiprocessor machines, the Stem-and-Cycle is a serial algorithm and no compiler directives for implicit parallelism are used. All runs were performed with a fixed set of algorithm parameters. We use N re-routing iterations of ejection chains of 50 levels (component steps, or "depth"), and 12 quadrant neighbors concatenated with Delaunay triangulations provided by Concorde.

We report computational results for runs starting from randomly generated solutions and from Boruvka's solution, respectively.

References

D. Applegate, R. Bixby, V. Chvatal, W.Cook, CONCORDE: A code for solving Traveling Salesman Problems. [http://www.math.princeton.edu/tsp/concorde.html]

D. Appelgate and W. Cook, Chained Lin-Kernighan for Large Traveling Salesman Problems, Research Report (2000) [http://www.isye.gatech.edu/~wcook/papers/chained_lk.ps]

M. L. Fredman, D. S. Johnson, L. A. McGeoch and G. Ostheimer, Data Structures for Traveling Salesmen, J. Algorithms, 18:3 (1995), pp. 432-479. [Preliminary version: Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms (1993) 145-154.]

F. Glover, New Ejection Chain and Alternating Path Methods for Traveling Salesman Problems, Computer Science and Operations Research (1992) 449-509.

K. Helsgaun, An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic, European Journal of Operational Research (126) 1 (2000) 106-130.

D. S. Johnson and L. A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization, Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra (editors), John Wiley and Sons, Ltd. (1997) 215-310.

S. Lin and B. W. Kernighan, "An Effective Heuristic Algorithm forthe Traveling-Salesman Problem," Operations Research. 21 (1973), 498-516.

C. Rego, Relaxed tours and path ejections for the traveling salesman problem, European Journal of Operational Research, 106 (1998) 522-538.