Erweiterte Formulierungen in der Kombinatorischen Optimierung

Für viele kombinatorische Optimierungsprobleme sind die Beschreibungen der in natürlicher Weise zugeordneten Polytope notwendigerweise sehr kompliziert und groß. In machen Fällen kann man jedoch diese komlizierten Polytope als lineare Projektionen einfach zu beschreibender  höher dimensionaler Polyeder darstellen und mit diesen Darstellungen in der gleichen Weise Theorie und Praxis der Linearen Optimierung für das vorliegende kombinatorische Optimierungsproblem nutzbar machen. In diesem Projekt leiten wir zum einen Methoden zum Aufstellen solcher erweiterter Formulierungen her und untersuchen zum andern, welche grundsätzlichen Grenzen dieser Methodik gesetzt sind.