Pagetitle:ATSP
Date:April 18, 2019



About

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.

Developer

Licence

Like SCIP the ATSP solver is distributed under the ZIB Academic Licence, which allows a free usage for academic purpose.

Download

atsp-1.0.tar.gz

Documentation

Doxygen Documentation