Diskrete Optimierung ist ein mächtiges Hilfsmittel bei Entscheidungsprozessen unter wirtschaftlichen
Nebenbedingungen, wie optimaler Nutzung von Ressourcen. Für diese Art von Problemen gibt es allerdings keine
universellen `kochrezeptartigen` Lösungsmethoden.
Klassische Methoden verwenden Lineare Optimierung (LO). In den letzten Jahren hat sich allerdings auch
Semidefinite Optimierung (SDO) als Verallgemeinerung von LO als sehr nützliche Alternative zur besseren
Approximation der zugrundeliegenden ganzzahligen Probleme herausgestellt. Die besseren Resultate sind
allerdings nur durch erheblichen Mehraufwand zu erzielen. Im Projekt sollte der SDO Zugang genauer ausgelotet
werden.
Die Grundziele des Projekts bestanden in den folgenden Punkten:
Modellierung:
Untersuchungen, die die Anwendbarkeit von SDO in der kombinatorischen Optimierung weiter vorantreiben.
Algorithmen:
Das Standardvehikel zur Lösung von SDO besteht im Einsatz von Inneren-Punkte Methoden. Es soll
untersucht werden, inwieweit diese Methodik auch in der Praxis brauchbar ist.
Large-Scale Probleme:
Bei großen Problemen sind algorithmische Alternativen zur Inneren-Punkte Methode wichtig.
In allen drei Bereichen konnten wesentliche Fortschritte erzielt werden. Der SDO Ansatz wurde insbesondere bei
Clusterungsproblemen im Telekommunikationsbereich erfolgreich eingesetzt. Bei großen Problemen stellte sich
eine Verbindung von Inneren-Punkte Methoden mit `Bundle Methoden` aus der nichtglatten Optimierung als bisher
mächtigstes Hilfsmittel zur Behandlung `quadratischer Zuordnungsprobleme` heraus. Dies ist eines der
schwierigsten kombinatorischen Optimierungsprobleme.
Der wissenschaftliche Output ist dokumentiert in etwa 15 Publikationen und drei Doktorarbeiten. Die
Projektmitarbeiter konnten die im Rahmen des Projekts erarbeiteten Kenntnisse auch für eine Verbesserung in ihrer
beruflichen Karriere nutzen.
Schließlich sei noch angemerkt, dass dieses Projekt als eines der ersten internationalen Forschungsprojekte den
Zusammenhang von SDO und ganzzahliger Optimierung untersucht. Zwischenzeitlich sind bereits andere
internationale Teams auf diesen Zug aufgesprungen.