Suche

Algorithmen zur gemischt-ganzzahligen quadratischen Optimierung

Dipl.-Math. oec. Matthias Tinkl

Es geht um die Implementierung eines neuen Branch-und-Bound-Algorithmus zur Berechnung von gemischt-ganzzahligen quadratischen Optimierungsproblemen.
erschienen April 2005 in: Augsburg Diplomarbeit im Studiengang Wirtschaftsmathematik an der Universität Augsburg

Verlag: Selbstverlag


Zusätzlich zur Implementierung des Algorithmus werden verschiedene Methoden zur Lösung von quadratischen Optimierungproblemen (lineare Restriktionen und quadratische Zielfunktion) ausgearbeitet und dabei insbesondere auf die Methode des Komplementär-Problems eingegangen.

Für dieses Komplementärproblem wird eine Variante des Simplexalgorithmus dargestellt und deren Endlichkeit bewiesen.

Für den Algorithmus werden zuerst die theoretischen Grundlagen herausgearbeitet und ein Endlichkeitsbeweis geführt. Danach werden die verschiedenen Versionen der Implementierung kurz umrissen und schließlich der Code eingereicht.

Bei der Implementierung kamm die Callable-Libary von Cplex (ILog) zur Anwendung, diese wurde dabei zur Berechnung der Lösungen der quadratischen Unterprobleme während des Branch-und-Bound-Vorgehens genutzt.
Für die Berechnung der Unterschranken der Teilproblem wurde das lineare Komplementär-Problem aufgestellt und mit Hilfe von Cplex das dazugehörige Endtableau des Optimalpunktes des Vaterproblems berechnet.