Dipl.-Math. Cornelius Schwarz

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

Jahr der Mathematik

ATSP

Über den Löser

Dies ist ein branch-and-cut basierter Löser für das asymmetrische Handlungsreisendenproblem (ATSP). Der Löser wurde in C implementiert und verwendet das Framework SCIP, welches zusätzlich heruntergeladen werden muss, um den Löser zu übersetzen.

 

In der derzeitigen Version sind folgende Punkte implementiert:

- Separation von Subtour Ungleichung mittels des Mincut Algorithmus von Stoer & Wagner inklusive Preprocessing nach Padberg & Rinaldi

- Separation von Blütenungleichung nach Padberg & Rao inklusive Safeshrinking

- Nearest Neighbor Heuristik

- LP-Runde Heuristik

 

Mit diesem Code können alle ATSP Instanzen aus der TSPLIB gelöst werden. Das Ziel der Entwicklung lag darin, viele kleine ATSPs (< 100 Knoten) als Subprobleme schnell lösen zu können.

Entwickler

Lizenz

Ähnlich wie SCIP selbst so steht auch der ATSP Löser unter der ZIB Academic Licence, welche eine kostenfreie Nutzung für akademische Zwecke erlaubt.

Download

atsp-1.0.tar.gz

Dokumentation

Doxygen Dokumentation

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

druckfreundliche Ausgabe der Seite