Grundlegende Untersuchungen zu Orbitopen

Orbitope sind Polyeder, die erfolgreich zur Ausnutzung von speziellen Symmetrien in ganzzahligen linearen Optimierungsproblemen benutzt werden. In diesem Projekt untersuchen wir grundlegende Fragen zu Orbitopen, also zu konvexen Hüllen von 0/1-Matrizen, die lexikographisch maximal in ihrem Orbit unter einer durch Spaltenpermutation operierenden Gruppe sind. Ziel des Projekts ist es, heraus zu finden, welche Einschränkungen an die 0/1-Matrizen die Orbitope so kompliziert werden lassen, dass man unter komplexitätstheoretischen Annahmen keine brauchbaren Beschreibungen erwarten kann, und andererseits für Klassen, bei denen dies nicht der Fall ist, Ungleichungsbeschreibungen herzuleiten.