Ü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
- Cornelius Schwarz, Universität Bayreuth
- Peter Hoffmann, Universität Chemnitz
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.
