Concorde

From IridiaWiki
Revision as of 14:06, 2 May 2008 by Mmanfrin (talk | contribs)
Jump to navigationJump to search

Concorde is a computer code for the traveling salesman problem (TSP) and some related network optimization problems. The code is available for academic research use; for other uses, contact William Cook for licensing options.

Concorde's TSP solver has been used to obtain the optimal solutions to all TSPLIB instances having up to 15,112 cities.


The Concorde ANSI C source code is distributed as a gzipped tar file and is available here


How to install on Mac OS X platform

To unpack, first gunzip the downloaded file, then use tar to unpack the archive:

$ gunzip co031219.tgz 
$ tar xvf co031219.tar 


Unpacking the distribution create a directory, "concorde", and several subdirectories. To configure, create a new directory called concorde_build, and run the configure script from inside there:

$ mkdir concorde_build
$ cd concorde_build
$ ../concorde/configure --host=i*-*-freebsd*

Then, you can compile concorde by using make:

 $ make

This builds the concorde library (concorde.a), header file (concorde.h), and several executable programs, including:

  • TSP/concorde the TSP solver
  • LINKERN/linkern the Lin-Kernighan TSP heuristic
  • EDGEGEN/edgegen generates edge sets
  • FMATCH/fmatch solves fractional 2-matching problems