User Tools

Site Tools


teaching:ss21:pg-ga

Projektgruppe: Algorithm Engineering

BA-INF 051: Traveling Salesman Problem

Aktuelles

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.

Material tba
Modulhandbuch BA-INF 051
BASIS tba
Formale Anmeldung tba
Veranstalter Prof. Dr. Petra Mutzel, Adalat Jabrayilov, Lukas Schürmann

Termine

Termin Wann Wo
Vorbesprechung 07.04.2021, 12:00 digital (Link wird per Mail verschickt)

Inhalt

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

teaching/ss21/pg-ga.txt · Last modified: 2021/03/31 14:53 by adalat.jabrayilov

Page Tools