Dipl.-Math. Cornelius Schwarz

Lehrstuhl für Wirtschaftsmathematik
Mathematisches Institut, Fakultät für Mathematik, Physik und Informatik

Jahr der Mathematik

ATSP

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

© 2005 Lehrstuhl Wirtschaftsmathematik — Imprint
Webmaster
Letztes Update am: 30.09.2013

druckfreundliche Ausgabe der Seite