This is a branch-and-cut solver for the asymmetric traveling salesman problem (ATSP) written in C. It is based on the framework SCIP which must be obtained additionally to compile the solver.
Currently the following is implemented:
- separation of subtour inequalities using the mincut algorithm of Stoer & Wager including the preprocessing method of Padberg & Rinaldi
- separation of blossom inequalities due to Padberg & Rao including safe-shrinking
- nearest neighbor heuristic
- LP rounding heuristic
The ATSP Solver can solve all of the ATSP instances of the TSPLIB. However, the developing goal was to be able to solve many small instances (< 100 nodes) as subproblems fast.
Like SCIP the ATSP solver is distributed under the ZIB Academic Licence, which allows a free usage for academic purpose.