Wir freuen uns über Ihr Interesse. Wenn Sie überlegen an der Projektgruppe teilzunehmen, schreiben Sie bitte eine unverbindliche formlose Email bis spätestens 31.03.2021 an Adalat Jabrayilov, damit wir die zu erwartende Teilnehmerzahl abschätzen und Ihnen die Zugangsdaten für die Vorbesprechung zukommen lassen können.

Das Traveling Salesman Problem ist ein klassisches kombinatorisches Optimierungsproblem. Es sucht in einem vollständigen gewichteten Graphen einen Pfad, der jeden Knoten genau einmal besucht und zum Startknoten zurückkehrt. Das Problem ist NP-schwer und wird in der Praxis häufig mit verschiedenen Branch-and-Cut Ansätzen gelöst.

In dieser PG wollen wir eine solche Branch-and-Cut Struktur kennenlernen, implementieren, optimieren und verschiedene Ansätze evaluieren. Als Progammiersprache wird Python benutzt. Voraussetzung ist die Vorlesung Algorithmen und Berechnungskomplexität I. Insbesondere benötigen Sie Kenntnisse der Linearen Programmierung: Was ist ein lineares Programm? Man sollte auch lineare Programm lesen und verstehen können. Man muss jedoch nicht wissen, wie lineare Programm genau gelöst werden.

Weitere Informationen folgen demnächst.

_{DozentInnen: Mutzel, Jabrayilov, Schürmann}