CCCO

In diesem Projekt werden polyedrische Strukturen in Verbindung mit kardinalitätsbeschränkten kombinatorischen Optimierungsproblemen untersucht. Meistens werden Kardinalitätsbeschränkungen auf der Menge der zulässigen Lösungen nur in der Form von = k, ≤ k, or ≥ k betrachtet. Hier interessieren wir uns aber für komplexere Kardinalitätsbeschränkungen. Um unser Anliegen besser beschreiben zu können, sei Π = (E, I, w) ein kombinatorisches Optimierungsproblem, wobei E eine endliche Menge ist, I eine Teilmenge der Potenzmenge von E, genannt Menge der zulässigen Lösungen, und w die Zielfunktion. Ziel ist es nun, eine zulässige Lösung zu finden, die die Zielfunktion maximiert (minimiert). Ferner sei c = (c₁, ..., c_m) eine endliche Folge von ganzen Zahlen mit 0 ≤ c₁ < c₂ < ... < c_m ≤ |E|. Dann ist das Problem Π_c: max w(F), F ∈ I, |F| = c_p für ein p offenbar eine kardinalitätsbeschränkte Version von Π. Sei P^c das Polytop assoziiert mit Π_c, d.h. die konvexe Hülle der Inzidenzvektoren der zulässigen Lösungen bzgl. Π_c. Ziel dieses Projektes ist das bessere Verständnis von facettendefinierenden Ungleichungen, die spezifisch für Kardinalitätsbeschränkungen sind.

• Volker Kaibel (U Magdeburg)
• Jean François Maurras (U de la Méditerranée)