TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Informatik
Informatikzentrum

Algorithmikpraktikum: Solving TSP

Modulnr.INF-ALG-09
Veranst.Nr.INF-ALG-023, INF-ALG-024
Studieng.Bachelor Informatik
IBR Gruppe(n)ALG (Prof. Fekete)
ArtVorlesung/Übung
Dozent
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Raum 335
Assistent
PhotoPhillip Keldenich
Wissenschaftlicher Mitarbeiter
keldenich[[at]]ibr.cs.tu-bs.de
+49 531 3913112
Raum 318
LP5
SWS0+3
Beginn Das Vorabtreffen findet am 14.09.2017 um 15:30 Uhr im IZ313 statt (Seminarraum der Algorithmik).
Voraussetzungen Zwingend erforderlich sind der souveräne Umgang mit dem Stoff aus Algorithmen und Datenstrukturen, gute Programmierkenntnisse in C++ (oder die Fähigkeit sie sich anzueignen), sowie Teamfähigkeit. Hilfreich, aber nicht zwingend erforderlich sind Wahlpflichtveranstaltungen der Algorithmik, wie zum Beispiel Algorithmen und Datenstrukturen II, Netzwerkalgorithmen, Einführung in Algorithm Engineering oder Mathematische Methoden der Algorithmik.
SpracheDeutsch
AnmeldungIndividuelle Absprache per E-Mail
Inhalt

In diesem Praktikum geht es darum, das NP-schwere Traveling Salesman Problem (TSP) optimal zu lösen. Das geschieht mit Hilfe mächtiger Tools, guter Software und vor allem durch die Kombination von Theorie und Praxis. Insbesondere werden vorhandene Integer Programming Solver wie IBM CPLEX benutzt. Dies bildet den Kern des Praktikums; darüber hinaus gibt es verschiedene Vertiefungsmöglichkeiten:

  • Den im Praktikum entwickelten Solver so weit wie möglich optimieren, sodass größere und schwerere Instanzen gelöst werden können. In Experimenten auf verschiedenen Instanzen evaluieren, wie sich Optimierungen auf Laufzeit und Speicherverbrauch auswirken.
  • Besonders schwere oder interessante TSP-Instanzen erzeugen und die Performance des Solvers und existierender TSP-Solver darauf evaluieren.
  • Heuristische Ansätze entwickeln, die bei Instanzen zum Einsatz kommen können, die nicht mehr exakt gelöst werden können. Experimente durchführen, um diese heuristischen Ansätze bezüglich verschiedener Kriterien zu vergleichen.
  • Visualisierung von Punktmengen, Touren und experimentellen Ergebnissen.
  • Varianten des Travelling Salesman Problem untersuchen. Es gibt hier sehr viele Möglichkeiten, von denen auch bereits viele schon in der Literatur untersucht wurden. Unter anderem wären die folgenden Varianten denkbar:
    • MaxTSP - die Länge der Tour maximieren, statt sie zu minimieren,
    • MaxScatterTSP - die Länge der kürzesten Kante maximieren (analog z.B. die Länge der längsten Kante minimieren),
    • Polygonvarianten - die Tour muss ein Polygon sein (d.h. keine Kreuzungen), wobei man verschiedene Eigenschaften (Fläche, Umfang) des Polygons optimieren kann,
    • Abbiegekosten - man zahlt nicht nur für die zurückgelegte Strecke, sondern auch für das Abbiegen an Knoten,
    • TSP mit Nachbarschaften - man muss nicht mehr punktförmige Städte besuchen sondern eine Menge von Bereichen betreten,
    • TSP mit Subtouren - eine gewisse Anzahl von Subtouren sind erlaubt, man muss nicht mehr alles mit einer einzigen Tour abdecken.
Literatur/Links

Hinweise zu LP-Solvern

Die Shells von CPLEX und SCIP sind sich recht ähnlich. Ihre wichtigsten Befehle lauten:

CPLEXSCIPEffektAbkürzung
helpZeigt die Hilfe anh
read x.lpLiest Datei x.lp ein
optimizeLöst das gelesene Problemopt
display solution variables -display solutionZeigt die Lösung andi so [va -]
quitBeendet die ShellCTRL-D drücken

aktualisiert am 11.09.2017, 17:13 von Phillip Keldenich
printemailtop