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.