Software: Cut-and-Solve code for the Asymmetric Traveling Salesman Problem

Sharlee Climer and Weixiong Zhang
Department of Computer Science and Engineering
Washington University in St. Louis, St. Louis, MO 63130, USA
email:  sharlee at climer.us, zhang at cse.wustl.edu

Cut-and-solve is an iterative search strategy for combinatorial optimization problems. At each step in the search, the optimal solution is found for a small (sparse) problem and a relaxed problem is solved. This search is different from traditional tree search as there is no branching. Furthermore, memory requirements are negligible. This method is presented in Cut-and-solve: An iterative search strategy for combinatorial optimization problems. This paper includes a generic algorithm that can be used for any integer linear program. We implemented the generic algorithm for real-world applications of the Traveling Salesman Problem. Cut-and-solve outperformed (sometimes dramatically!) state-of-the-art solvers for five out of seven problem classes. Results of these tests are summarized in this paper.

This code is written in C++ and we have run it on Linux. It requires the use of cplex and we have used cplex version 8.1. The package is a gzipped tar file. Use "gunzip cnsTSP.tar.gz" followed by "tar -xvf cnsTSP.tar". See the README file for details on installation and usage. For the latest version of this code, please contact me at: sharlee at climer.us.