Concorde TSP is one of the best solvers for the Traveling Salesman Problem. Its current version was released in 2003, but it is still considered to be the state of the art in its field.
CPLEX is a general purpose solver. It is also considered to be one of the best in its class.
In order to obtain exact solutions with Concorde, one needs to link it to a solver. However, Concorde’s documentation falls short, since in 2003 CPLEX’s version was 8.0, and it is currently under version 12.9 (as of April 2019).
To link and compile Concorde with CPLEX, you will need to follow the instructions below:
1. Download:
Concorde TSP: Concorde-03.12.19 from http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm
CPLEX version 12.9: see instructions to download and install CPLEX.
2. After installing CPLEX, extract concorde files:
gunzip co031219.tgz
tar xvf co031219.tar
3. Change the following concorde files before linking it to CPLEX:
cd concorde
– to avoid undefined reference to ’dlopen’ or ‘pthread’ or similar.
In “concorde/Makefile.in” change LIBFLAGS to:
LIBFLAGS = @LIBS@ -lpthread
In “concorde/TSP/Makefile.in” change LIBFLAGS to:
LIBFLAGS = @LIBS@ -lpthread -ldl
4. Create simlinks from some CPLEX files to the directory where you want to compile Concorde:
ln -s /path/to/cplex/include/ilcplex/*.h .
ln -s /path/to/cplex/lib/x86-64_sles10_4.1/static_pic/libcplex.a .
5. Run the configure:
./configure --prefix=/path/to/concorde –with-cplex=/path/to/concorde
6. Run make
make
7. Change to following concorde files after linking it to CPLEX:
– To avoid error: expected ‘,’ or ‘. . .’ before ‘new’ or ‘class’
In “concorde/concorde.h” use find and replace to change all *new) to *NEW) and all *class) to *CLASS)
– To avoid error: ‘CPX_PARAM_FASTMIP’ undeclared (first use in this function).
In “concorde/LP/lpcplex8.c” after #undef CC_CPLEX_DISPLAY add:
#ifndef CPX_PARAM_FASTMIP
#define CPX_PARAM_FASTMIP 1017
#endif
8. Rename “concorde.a” to “libconcorde.a”
mv concorde.a libconcorde.a
Solving a TSP with concorde using a TSPLIB format file
To solve a TSP with the TSPLIB format using concorde you should put the file “concorde/TSP/concorde” and your .tsp file in the same folder and run:
./concorde filename.tsp
Solving a TSP with concorde in C++
You can find the documentation to all concorde functions in www.math.uwaterloo.ca/tsp/concorde/DOC/concorde_org.html.
A simple file implementing concorde in C++ is below.
Makefile:
TOCONCORDE = /full/path/to/concorde #e.g. /home/username/concorde
TOCPLEX = /full/path/to/cplex #e.g. /home/username/ibm
CPPFLAGS = -DIL_STD -I$(TOCONCORDE)
CXX = g++
LIBS = -L$(TOCONCORDE) -lconcorde -lilicplex -lconcert -lcplex -L$(TOCPLEX)/cplex/lib/x86-64_sles10_4.1/static_pic/ -L$(TOCPLEX)/concert/lib/x86-64_sles10_4.1/static_pic/ -m64 -lm -lpthread -ldl
main: main.o
$(CXX) $(CFLAGS) -o main main.o $(LIBS)
main.cpp:
//This file solves a TSP using concorde given a symmetric 2D distance matrix
//Info about concorde functions: www.math.uwaterloo.ca/tsp/concorde/DOC/concorde_org.html
#include <iostream>
#include <vector>
extern "C" {
#include <concorde.h>
}
using namespace std;
//Receive a symmetric 2D distance matrix (dist) and create a TSP optimal tour (tour)
void solving_tsp_concorde(vector< vector<int> > * dist, vector<int> * tour){
//Creating a sequential tour
for(int i = 0; i < tour->size(); i++)
tour->at(i) = i;
if(dist->size() > 4 ){//TSP for more than 4 cities
int rval = 0; //Concorde functions return 1 if something fails
double szeit; //Measure cpu time
double optval; //Value of the optimal tour
double *in_val = (double *) NULL; //Can be used to specify an initial upperbound (it can be NULL)
double *timebound = (double *) NULL;; //Run time limit
int success; //1 if the run finished normally, and set to 0 if the search was terminated early (by hitting some predefined limit)
int foundtour; //1 if a tour has been found (if success is 0, then it may not be the optimal tour)
int hit_timebound = 0; //1 if timebound was reached
int *in_tour = (int *) NULL; //Gives a starting tour in node node node format (it can be NULL)
int *out_tour = (int *) NULL; //Optimal tour (it can be NULL, if it is not NULL then it should point to an array of length at least ncount).
char *name = (char *) NULL; //Specifes a char string that will be used to name various files that are written during the branch and bound search
static int silent = 1; //Suppress most output if set to a nonzero value
CCrandstate rstate;
int seed = rand();
CCutil_sprand(seed, &rstate); //Initialize the portable random number generator
int ncount = dist->size(); //Number of nodes (cities)
int ecount = (ncount * (ncount - 1)) / 2; //Number of edges
int *elist = new int[ecount * 2]; //Array giving the ends of the edges (in pairs)
int *elen = new int[ecount]; //Array giving the weights of the edges
int edge = 0;
int edgeWeight = 0;
for (int i = 0; i < ncount; i++) {
for (int j = i + 1; j < ncount; j++) {
if (i != j) {
elist[edge] = i;
elist[edge + 1] = j;
elen[edgeWeight] = dist->at(i)[j];
edgeWeight++;
edge = edge + 2;
}
}
}
out_tour = CC_SAFE_MALLOC (ncount, int);
name = CCtsp_problabel("_");
CCdatagroup dat;
//Initialize a CCdatagroup
CCutil_init_datagroup (&dat);
//Convert a matrix of edge lengths to a CCdatagroup
rval = CCutil_graph2dat_matrix (ncount, ecount, elist, elen, 1, &dat);
//Solves the TSP over the graph specified in the datagroup
rval = CCtsp_solve_dat (ncount, &dat, in_tour, out_tour, &in_val, &optval, &success, &foundtour, name, timebound, &hit_timebound, silent, &rstate);
for (int i = 0; i < ncount; i++) {
tour->at(i) = out_tour[i];
}
szeit = CCutil_zeit();
CC_IFFREE (elist, int);
CC_IFFREE (elen, int);
CC_IFFREE (out_tour, int);
CC_IFFREE (name, char);
}
}
int main(){
//Dataset (distance matrix of a 5 city TSP)
int ncities = 5;
int initialize[ncities][ncities]=
{
{0,3,4,2,7},//A
{3,0,4,6,3},//B
{4,4,0,5,8},//C
{2,6,5,0,6},//D
{7,3,8,6,0}//E
};
//Copying initial dataset for the distance structure
vector< vector<int> > * dist = new vector< vector<int> >( ncities, vector<int>(ncities) );
for(int i = 0; i < dist->size(); i++)
for(int j = 0; j < dist->size(); j++)
dist->at(i)[j] = initialize[i][j];
//Tour stores the optimal tour
vector<int> * tour = new vector<int>(ncities, 0);
//Solve TSP
solving_tsp_concorde(dist,tour);
//Print solution
for(int i = 0; i < tour->size(); i++)
cout<<tour->at(i)<<"_";
cout << endl;
return 0;
}
If main run with no errors, your concorde is setup!
Thanks Allyson!