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!

Install CPLEX on linux (without administration privileges)

[update] IBM has changed the website from where CPLEX can be downloaded. It is now ibm.biz/CPLEXonAI.

Following the post on how to download CPLEX for free (academics and students), find here how to install it under linux.

Register with IBM on the hub and download CPLEX 12.9 from https://ibm.onthehub.com/
Select on the menu Data & Analytics –> Software –> CPLEX
For Linux, download option “File: IBM ILOG CPLEX Optimization Studio 12.9 for Linux x86-64 Multilingual (CNZM2ML)”

Note that to install it, you do not need administrator privileges.

bash cplex_studio129.linux-x86-64.bin

Follow on-screen instructions, and when asked about the path to install it, write

/home/username/CPLEX_Studio129

change “username” by your username on the machine

Atter installation, edit the file ~/.bashrc and add the following line at the end:

export PATH=$PATH:/home/username/CPLEX_Studio129/cplex/bin/x86-64_linux

Remember to change username.

Save the file, and execute the commands

source .bashrc
cplex

You should have loaded CPLEX now.

How to: compile C++ with Gurobi in Linux

In order to compile your C++ project with Gurobi, you first need to create the appropriate libgurobi_c++.a compatible with your g++ version. To do so, access the following directory and compile it:

cd [GRB_path]/linux64/src/build
make
The file is now created, so copy it to the lib folder:
cp libgurobi_c++.a ../../lib/
Now you can create your makefile. For example:
CCC = g++ 
FLAGS = -g -Wall -Wextra 
GRBPATH = /[full path to]/gurobi752/ 

exec: code.cpp 
     $(CCC) $(FLAGS) code.cpp -o exec -I$(GRBPATH)/linux64/include -L$(GRBPATH)/linux64/lib -lgurobi_c++ -lgurobi75 

clean: 
     rm -f code *.o *~

You might need to change spaces to tabs in the above makefile.

This was useful? Buy me a cup of coffee to help me keep this website running!



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