The Traveling Salesman Problem: Installing Concorde on Mac Catalina with CPLEX

16 Mar 2020

Long time no post and, unfortunately for the casual reader, this post is mostly describing how to install Concorde optimizer for the Traveling Salesman Problem (TSP) with Mac OS Catalina using the CPLEX backend. If this means nothing to you, click away!

First: CPLEX is a commercial linear programming solver available free for the academic community. I guess the idea is to hook us so that we pay when we leave or convince our organizations to pay for a license when we leave.

Second: Concorde is what the TSP package in R calls state of the art for getting an exact solution to the Traveling Salesman Problem. The only problem is that one must install it separately and since Concorde was last updated in 2003, some things don’t work quite as easily as we would like. For example, it was made to run with CPLEX 8 but the current CPLEX version on my machine is 12.10! Now, on to the actual installation details.

1. Download Concorde
   Concorde can be downloaded from here.

2. Download and Install CPLEX
   See the IBM website for more details
3. Untar the Concorde files
   

   tar xvf co031219.tar
   

4. Enter the Concorde directory
   

   cd /path/to/concorde
   

5. Create a symlink to the CPLEX files
   On my machine, this looks something like:
   

   ln -s /path/to/cplex/include/ilcplex/*.h .
   ln -s /path/to/cplex/lib/x86-64_osx/static_pic/libcplex.a .
   

   note: this is done inside the Concorde directory.

6. Add compiler flags
   

   export CFLAGS="-g -O3 -arch x86_64"
   

7. Change Concorde files
   In “concorde/Makefile.in” change LIBFLAGS to:
   

   LIBFLAGS = @LIBS@ -lpthread
   

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

   LIBFLAGS = @LIBS@ -lpthread -ldl
   

   In “concorde/LP/lpcplex8.c” after #undef  CC_CPLEX_DISPLAY add:
   

   #ifndef CPX_PARAM_FASTMIP
   #define CPX_PARAM_FASTMIP 1017
   #endif
   

   In “concorde/TSP/tsp_call.c” at line 479, change the 0 to a 1 (see this post by one of the designers of Concorde)

8. Run configure
   Note the host option. It gives a warning saying it doesn’t know what “darwin” is on my machine, but won’t run without it ¯_(ツ)_/¯
   

   ./configure --host=darwin --prefix=/path/to/concorde –with-cplex=/path/to/concorde
   

9. Run make
   

   make
   

10. If you can run Concorde without an error, you’re done! The easiest way for me is within the TSP R package. You may need to specify the location of the Concorde TSP files like so:
    

    tsp::concorde_path(path = "/path/to/concorde/TSP")
    

11. And then check the TSP example:
    

    data("USCA312", package = "TSP")
    TSP::solve_TSP(USCA312, method = "concorde", control = list(clo = "-V"))
    

    If that works, then you should be all set!

Details from this post come from this other post by Professor Leandro Coelho and this post by Hà Quang Minh, adapted to what worked on my machine (mid-2019 MacBook Air).