MATHEON-B12: IPSym
Symmetrien in der Ganzzahligen Programmierung
Beschreibung
| Symmetrien treten in natürlicher Weise in ganzzahligen Programmen auf. Häufig gibt es keinen Grund, spezielle Objekte von anderen zu unterscheiden. Zum Beispiel ist die Linien-Nummer eines Busses für die Qualität des Linienplans unerheblich. In den resultierenden Modellen operiert eine möglicherweise große Symmetriegruppe auf der Menge der zulässigen Lösungen, wobei der zugehörige Zielfunktionswert konstant auf jedem Orbit bleibt. Algorithmen, die solche Symmetrien ignorieren, finden häufig die optimale Lösung nicht schnell genug. Das Ziel dieses Projektes ist die Entwicklung struktureller Erkenntnisse, algorithmischer Methoden und Software, um heutige Löser ganzzahliger Optimierungsprobleme zu verbessern. Unsere Projekt-Vision ist, von Symmetrien zu profitieren statt unter ihnen zu leiden. | |
| Weitere Informationen finden sich in der ausführlichen Projektbeschreibung. |
Ansprechpartner
| Timo Berthold |
Mitarbeiter
| Timo Berthold Martin Grötschel |
Partner
|
Finanzierung
| DFG Forschungszentrum Matheon "Mathematik für Schlüsseltechnologien: Modellierung, Simulation und Optimierung realer Prozesse." |
Dauer
| 06/2006 - 05/2009 |