CONCORDE: A COMPUTER CODE FOR THE TRAVELING SALESMAN PROBLEM Preliminary Version: Lausanne 27.8.97 David Applegate Rice University Computational and Applied Mathematics 6100 Main Street Houston, Texas 77005 Robert Bixby Rice University Computational and Applied Mathematics 6100 Main Street Houston, Texas 77005 Vasek Chvatal Rutgers Unversity Department of Computer Science New Brunswick, New Jersey 08903 William Cook Rice University Computational and Applied Mathematics 6100 Main Street Houston, Texas 77005 ABSTRACT: We give a very brief description of a computer code for the traveling salesman problem (TSP). The code is written in the C-programming language and it is available without cost for research purposes. The implemented algorithms include kd-tree based heuristics, Chained Lin- Kernighan, and a framework for solving the TSP via linear programming methods. ***** ***** ***** ***** ***** These notes are very, very, brief. We will have a more ***** ***** detailed users guide in the near future, when we make the ***** ***** code available on the internet at: ***** ***** ***** ***** http://www.caam.rice.edu/~keck/concorde.html ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** We are distributing this code for research use. The authors ***** ***** reserve all rights to the code. ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** The code is in a gzipped tar file "cc082797.tgz". You can ***** ***** this file using using "tar xzvf cc082797.tgz". ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** ***** WARNINGS ***** ***** ***** ***** 1. The cutting plane routines given in the XSTUFF ***** ***** directory will not be supported in the code. These are ***** ***** quick ports of routines from the old code described in the ***** ***** technical report: "Finding Cuts in the TSP", DIMACS ***** ***** Technical Report 95-05, March 1995. The ports are sloppy ***** ***** and several of the routines are known to have bugs. ***** ***** ***** ***** ***** ***** ***** 1. FILE FORMATS There are several forms of input files that are used by the executable programs. There are three types of data sets: edge set files, distance function files (usually x,y coordinates for the cities), and cycle files. Edge sets have the following form: #nodes #edges end1 end2 weight end1 end2 weight . . . end1 end2 weight where each "end1 end2 weight" line represents the end nodes and weight of an edge. The nodes should be numbered from 0 up to #nodes - 1, and the weight must be integers. There should be #edges "end1 end2 weight" lines in the file. Here is an example of an edge file for a 4 node problem, having 5 edges: 4 5 0 1 13 1 3 26 2 3 45 0 2 19 0 3 10 The program "mincut" permits the weights to be floating point values (to allow it to treat LP solution vectors). Node files (or "dat files") for geometric instances have the form: #nodes x1 y1 x2 y2 . . . x#nodes y#nodes where the x and y's are integers. Different norms can be specified to allow the codes to compute distances from these coordinates. The codes can also read TSPLIB files (for TSP instances) to obtain the distance function information. Cycle files have the form: #nodes p_1 p_2 p_3 .... p_#nodes where the p_i's are integers between 0 and #nodes - 1, specifying a permutation of the nodes. 2. EXECUTABLE PROGRAMS Most of the directories contain main programs that can be used to interact with the functions. It should be possible to use these routines without looking into the source code. a) KDTREE: kd-tree based routines Usage: kdtree [- see below -] [dat_file] -b: dat file in binary-ints -w f use node weights from file -W # use random node weights (0, #) -k # number of nodes for random problem -s # random seed -n # find # nearest graph -q # find quadrant # nearest graph -t nearest neighbor tour -g greedy tour -j quick-boruvka tour -v boruvka tour -f farthest addition tour -z f two_opt the given cycle -Z run two_opt (default: on greedy) -x f 3_opt the given cycle -X run 3_opt (default: on greedy) -h use limited 3-swaps in two_opt -m nearest neighbor 2-matching -p min spanning tree (prim) -o f write the cycle or edge set to f -T node file is a TSPLIB file -0 Max norm for edge lengths -1 Euclidean Ceiling norm -2 Rounded Euclidean norm (default) Examples: I) kdtree -o usa.tree -p -T usa13509.tsp -computes the minimum spanning tree of the TSPLIB instance usa13509.tsp and store the result (as an edge set) in the file usa.tree II) kdtree -s 99 -2 -g -k 10000 -computes a greedy tour for a 10,000 node random geometric instance, using the Euclidean norm (rounded to the nearest integer as the distance function) III) kdtree -t -Z -T usa13509.tsp -runs 2-opt on a nearest neighbor tour. IV) ktree -x usa.tour -T usa13509.tsp -runs 3-opt for the tour given in the cycle file usa.tour. b) LINKERN: Chained Lin-Kernighan usage: linkern [- see below -] [dat_file] -b dat file in binary ints -k # number of nodes for random problem -s # random number seed -n s process name (used for naming output file) -p dump final cycle -S s save tour in S after every 10000 kicks -a # use #-nearest as good edge set -D f edgegen description file -g f good edge file -q # use quad #-nearest as edge set (default 3) -r # number of runs -R # number of kicks in iterated Lin-Kernighan -y f starting cycle -Y f starting cycle (as an edgelist) -u greedy starting cycle (for kd-norms) -j quick-boruvka starting cycle (for kd-norms) -v boruvka starting cycle (for kd-norms) -l random starting cycle -T the dat file is a TSPLIB file -t d running time bound in seconds -h d tour length bound (stop when we hit d) -Q run silently -0 Max norm for edge lengths -1 Ceiling Euclidean norm - from DSJ -2 Rounded Euclidean norm (default) -3 Rounded Euclidean 3D norm -(4 5 6 7 8 9) IBM ATT GEO MATRIX DSJRAND CRYSTAL norm Examples: I) linkern -s 99 -R 100000 -h 143666667 -q 2 -j -T pla85900.tsp -run Chained Lin-Kernighan for 100,000 kicks (or until a tour of length at most 143666667 is reached), using the quad-nearest-2 as the set of "good edges" and starting with the quick-boruvka tour. The random seed is set to 99 (given different seeds, the code will have different behavior). II) linkern -y usa.tour -R 10000 -p -T usa13509.tsp -run for 10,000 kicks starting with the tour specified in the cycle files usa.tour and write the best tour found to the edge file ecycle.out.usa13509.tsp. c) EDGEGEN: routine to generate edge sets usage: edgegen [- see below -] [dat file] -b dat file in binary-ints -w f node weight file -W # use random node weights, from 0 to # - 1 -k # number of nodes for random problem -s # random seed -D f description file -n # find # nearest graph -q # find quadrant # nearest graph -d find Delaunay triangulation -f # find # nearest using f2match reduced costs -U # find # random tours -N # find # nearest neighbor tours -G find greedy tour -(A B C) # find # (2opt, 2.5opt, 3opt) tours -L # find # linkern tours -m # find # linkern matchings -R # use # kicks in linkern (default: 100) -u use greedy starting tour for linkern -v use random starting tours for linkern -x # use # quadnearest in linkern -y # use # nearest in linkern (can use x & y) -M # find # nearest neighbor 2-matchings -S find min spanning tree -F find fractional twomatch (not priced) -o f write the cycle or edge set to f -T the dat file is a TSPLIB file -0 Max norm for edge lengths -1 Ceiling Euclidean norm - from DSJ -2 Rounded Euclidean norm (default) -3 Rounded Euclidean 3D norm -(4 5 6 7 8 9) IBM ATT GEO MATRIX DSJRAND CRYSTAL norm Examples: I) edgegen -A 10 -o usa.edg -T usa13509.tsp -finds the union of 10 2-opt tours and writes the edge file to usa.edg. II) edgegen -D usa.D -o usa.edg -T usa13509.tsp -finds the edge described in usa.D and writes the edge file to usa.edg. For instance, if usa.D contains the commands EDGEGEN NEAREST 5 EDGEGEN GREEDY_TOUR EDGEGEN THREEOPT_TOUR 2 EDGEGEN TREE EDGEGEN LINKERN 10 100 then the edge set will be built from the union of the nearest-5 neighbor graph, a greedy tour, two three opt tours, a minimum spanning tree, and ten Chained Lin-Kernighan runs using 100 kicks per tour. The commands available are: EDGEGEN NEAREST # -find the nearest # edges EDGEGEN QUADNEAREST # -find the quadrant-nearest # edges EDGEGEN FRAC_TWOMATCH_NEAREST # [PRICED] [BASIC] -find the nearest # using the reduced costs of a fractional 2-matching as the edgelengths. If either of the optional arguments PRICED or BASIC is specified then the 2-matching used will be either priced against the complete edgeset or converted to a basic optimal solution (or both). EDGEGEN GREEDY_TOUR -find a greedy tour EDGEGEN NN_TOUR # -find # nearest-neighbor tours EDGEGEN RANDOM_TOUR # -find # random tours EDGEGEN TWOOPT_TOUR # -find # 2-opt tours EDGEGEN TWOPT5_TOUR # -find # 2.5-opt tours EDGEGEN THREEOPT_TOUR # -find # 3-opt tours EDGEGEN LINKERN #1 #2 [QUADNEAREST #3] [NEAREST #4] [GREEDY_START | NN_START | RANDOM_START] -find #1 Iterated Lin-Kernighan tours using #2 kicks. The good edgeset can be specified by the optional arguments QUADNEAREST and NEAREST (the two can be used together). The initial tours can be specified by using one of GREEDY_START or NN_START or RANDOM_START. EDGEGEN NN_TWOMATCH # -find # nearest-neighbor 2-matchings EDGEGEN TREE -find a minimum weight spanning tree. EDGEGEN FRAC_TWOMATCH [PRICED] [BASIC] -find a minimum weight 2-matching (priced against the complete edgeset) (that is a basic optimal solution) d) FMATCH: solves the fractional 2-matching problem usage: fmatch [-see below-] -B find basic optimal solution -b datfile in integer binary format -D f edgegen file for initial edge set -e f edge file - initial edge set -k # number of nodes for random problem -m NN 2-matching as initial edge set -n f dat file - for fmatch on complete graph -q # quad-nearest # as initial edge set (default 2) -s # random seed -T the dat file is a TSPLIB file -x dump matching to match.out -y dump dual solution to dual.out -z dump basic edges to basis.out -0 price out using MAX norm -1 price out using JOHNSON norm -2 price out using EUCLIDEAN norm (default) -3 price out using Rounded Euclidean 3D norm -(4 5 6 7 8 9) IBM ATT GEO MATRIX DSJRAND CRYSTAL norm Examples: I) fmatch -e usa.edg -finds the optimal fractional 2-matching in the graph specified by the edge file usa.edg. II) fmatch -x -T -n usa13509.tsp -finds the optimal fractional 2-matching in the complete graph specified by the TSPLIB instance usa13509.tsp. e) MINCUT: finds minimum st-cuts and global minimum cuts usage: mincut [- below -] edge_file -b: binary input file -c: display all cuts < 2.0 -p: use Padberg-Rinaldi style shrinking -s #: source -t #: sink -S: do not use the TSP shrink routines -C: display the min cut Examples: I) mincut -s 0 -t 100 usa.edg -finds the minimum cut between nodes 0 and 100 in the edge file usa.edg. II) mincut -p usa13509.17140 -finds the global minimum cut in the edge file usa13509.17140. NOTE: The code is tuned for solution vectors of the LP relaxations of TSP instances. f) CONCORDE: solves the TSP (in the TSP directory) usage: concorde [-see below-] [dat_file] -b datfile in integer binary format -B run best-bound branching -c use consecutive ones cuts -d dfs search -D f edgegen file for initial edge set -e f initial edge file -E f full edge file -f don't call tighten for each cut -k # number of nodes for random problem -l use necklace cuts -M f master file -n s problem name (just a name, not a file name) -N f prob file -P f cutpool file -s # random seed -S just solve the subtour polytope -T the dat file is a TSPLIB file -t f tour file (in node node node format) -u v initial upperbound -U permit branching on subtour inequalities -v full list valid (must contain initial list) -(0 1 2 3) price out using (MAX JOHNSON L2 3D) norm -(4 5 6 7 8 9) IBM ATT GEO MATRIX DSJRAND CRYSTAL norm Examples: I) concorde -BUTcl pr76.tsp -solves the TSP for the TSPLIB instance pr76.tsp, using best-bound branching on subtour inequalities and using consecutive ones and necklace cutting plane routines. II) concorde -ST pr76.tsp -optimizes over the subtour polytope. III) concorde -T pr76.tsp -runs cutting plane routines to obtain a good linear programming relaxation of the TSP (it will not do branching, only valid lower and upper bounds will be produced, not necessarily the optimal solution). This will generate the files pr76.mas and pr76.sav. IV) concorde -B -M pr76.mas -N pr76.sav -carries out branching, starting with the LP written by the above command. 3. CALLABLE LIBRARY A large number of functions are exported by concorde. To use these, build concorde.a and concorde.h as per the instructions in the README file included in xxx.tgz. Short descriptions of the functions can be found in the comments at the head of the .c files. 4. SOURCE CODE The source code can be altered as needed. We have supported both ANSI and KR versions of C via ifdef's around the function prototypes.