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:
1. Edit the ./Makefile and the ./TSP/Makefile and add -lpthread to the end of the line defining LIBFLAGS. Note that Concorde’s documentation misspells it as “lpthreads”.
2. Create simlinks from some CPLEX files to the directory where you want to compile Concorde, e.g.:
/concorde/ > ln -s /path/to/cplex/include/ilcplex/*.h . /concorde/ > ln -s /path/to/cplex/lib/x86-64_sles10_4.1/static_pic/libcplex.a .
(note that the correct path depends on your system)
3. Run the configure, e.g.:
/concorde/ > ./configure --prefix=/path/to/concorde --with-cplex=/path/to/concorde
4. Run make.
You should now be able to run the exact solver from concorde/TSP/concorde, which will use CPLEX as the LP solver.
Enjoy!
This was useful? Buy me a cup of coffee to help me keep this website running!