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 = @[email protected] -lpthread

In “concorde/TSP/Makefile.in” change LIBFLAGS to:

LIBFLAGS = @[email protected] -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>

}usingnamespacestd;//Receive a symmetric 2D distance matrix (dist) and create a TSP optimal tour (tour)voidsolving_tsp_concorde(vector< vector<int> > * dist, vector<int> * tour){//Creating a sequential tourfor(inti = 0; i < tour->size(); i++)

tour->at(i) = i;if(dist->size() > 4 ){//TSP for more than 4 citiesintrval = 0;//Concorde functions return 1 if something failsdoubleszeit;//Measure cpu timedoubleoptval;//Value of the optimal tourdouble*in_val = (double*)NULL;//Can be used to specify an initial upperbound (it can be NULL)double*timebound = (double*)NULL;;//Run time limitintsuccess;//1 if the run finished normally, and set to 0 if the search was terminated early (by hitting some predefined limit)intfoundtour;//1 if a tour has been found (if success is 0, then it may not be the optimal tour)inthit_timebound = 0;//1 if timebound was reachedint*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 searchstaticintsilent = 1;//Suppress most output if set to a nonzero value

CCrandstate rstate;intseed = rand();

CCutil_sprand(seed, &rstate);//Initialize the portable random number generatorintncount = dist->size();//Number of nodes (cities)intecount = (ncount * (ncount - 1)) / 2;//Number of edgesint*elist =newint[ecount * 2];//Array giving the ends of the edges (in pairs)int*elen =newint[ecount];//Array giving the weights of the edgesintedge = 0;intedgeWeight = 0;for(inti = 0; i < ncount; i++) {for(intj = 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(inti = 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);

}

}intmain(){

//Dataset (distance matrix of a 5 city TSP)

intncities = 5;

intinitialize[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 =newvector< vector<int> >( ncities, vector<int>(ncities) );

for(inti = 0; i < dist->size(); i++)for(intj = 0; j < dist->size(); j++)

dist->at(i)[j] = initialize[i][j];//Tour stores the optimal tour

vector<int> * tour =newvector<int>(ncities, 0);

//Solve TSP

solving_tsp_concorde(dist,tour);//Print solutionfor(inti = 0; i < tour->size(); i++)

cout<<tour->at(i)<<"_";

cout << endl;return0;

}

If main run with no errors, your concorde is setup!

*Thanks Allyson!*