« Projekte
Erweiterte Formulierungen in der Kombinatorischen Optimierung
Projektbearbeiter:
Mirjam Friesen
Finanzierung:
Deutsche Forschungsgemeinschaft (DFG) ;
Die meisten für die kombinatorische Optimierung relevanten Polytope haben exponentiell in der Größe der Probleminstanz viele Facetten, so dass für den linearen Optimierungsansatz exponentiell viele Nebenbedingungen beachtet werden müssen. Das Konzept der erweiterten Formulierungen erlaubt es, Polytope als affine Projektionen höher-dimensionaler, aber wesentlich einfacher zu beschreibender Polyeder darzustellen. Das Ziel dieses Projekts ist, das grundlegende Verständnis des Konzepts der erweiterten Formulierungen signifikant zu verbessern und neue Methoden sowohl für die Konstruktion als auch für die Bestimmung unterer Schranken an die kleinste mögliche Größe solcher Formulierungen zu entwickeln.

Anmerkungen

Projektnummer KA 1616/4-1

Schlagworte

Polyedrische Kombinatorik, Projektionen
Kontakt

weitere Projekte

Die Daten werden geladen ...