next up previous contents
Next: Polyedrische Beschreibungen von Reihenfolgeplanungsproblemen Up: Jahresbericht 95/96 Previous: Vorwort

Grundlagen der kombinatorischen Optimierung

Viele moderne Lösungsansätze für Fragestellungen aus praktischen Bereichen wie Transportlogistik oder Produktionsplanung verdanken ihre Entstehung einer stark theoretisch motivierten Grundlagenarbeit. Insbesondere beschäftigt man sich dabei mit Maximierungs- bzw. Minimierungsaufgaben, bei denen man es mit diskreten Zulässigkeitsgebieten zu tun hat: So wird eine Maschine eingeschaltet oder auch nicht, eine Verbindung existiert oder nicht, und eine Spedition kann nur ganze LKWs auf den Weg zu ihren Kunden schicken. Daraus ergibt sich in Theorie und Anwendung die Suche nach einem ganzzahligen Vektor, der ein lineares Ungleichungssystem erfüllt und gleichzeitig den Optimalwert bezüglich einer konvexen (oder sogar linearen) Funktion erreicht.

Die kombinatorische Optimierung umfaßt und vereint Aspekte aus Mathematik und Informatik. Forschungsschwerpunkte sind dabei unter anderem das Studium der Struktur des Lösungsraumes und die Entwicklung ,,beweisbar guter`` und in der Praxis erfolgreicher Lösungsstrategien. Im folgenden sind einige Beispiele für die Arbeit unserer Gruppe in diesen Bereichen aufgeführt.









Webmaster <www@zpr.uni-koeln.de>, 7. Apr. 1997