Install and run Concorde with CPLEX

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>
}

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!

Installing Concorde TSP with CPLEX in Linux

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.5 (as of november 2012).

In order to link and compile Concorde with CPLEX, you will need to make the following modifications:

Continue reading