Suche

Kombinatorische und Diskrete Optimierung


Projektstart: 01.01.2016
Projektträger: Universität Augsburg
Projektverantwortung vor Ort: Harks

Zusammenfassung

In der kombinatorischen Optimierung beschäftigt man sich mit Lösungsverfahren für Probleme, die in der Regel eine problemspezifische kombinatorische Struktur der Lösungsmenge aufweisen. Ein klassisches Beispiel ist das Kürzeste Wege Problem. Hier ist ein Graph gegeben und die Lösungsmenge ist implizit durch die Menge von Wegen, die einen vorgegeben Startknoten mit einem Endknoten verbinden, beschrieben. Häufig sind die jeweiligen Optimierungsprobleme durch eine konkrete Anwendung aus der Praxis motiviert. Im Folgenden sind einige solche Problemklassen aufgeführt:
  • Routing-, und Scheduling-Probleme mit Anwendungen im Verkehr, Telekommunikation und Logistik
  • Standortplanung in der Logistik
  • mehrdimensionale Packungsprobleme in der Logistik
  • Tarifoptimierung in der Transportplanung
  • Matching Probleme mit Budget Schranken und ihre Anwendungen in Wireless Networks
  • Matroid Theorie mit Anwendungen im Netzwerkdesign
  • Polymatroid Theorie mit Anwendungen im Verkehr
  • LP/IP basierte exakte Verfahren

In der Arbeitsgruppe forschen wir sowohl an exakten, als auch an approximativen Verfahren, die in Polynomialzeit optimale Lösungen bzw. solche mit einer garantierten Güte berechnen.