Ansätze zur Lösung von disjunktiven Problemen mit Hilfe der verallgemeinerten semi-infiniten Optimierung
Final Report Abstract
Seit 2003 ist ein Zusammenhang zwischen verallgemeinert semi-infiniten Problemen und disjunktiven Problemen bekannt. In dem Projekt ging es darum, diesen Zusammenhang näher zu untersuchen. Dabei wurde zunächst aufgezeigt, wie sich vergleichsweise allgemeine Formen von DPs als GSIPs schreiben lassen. Diese können unter schwachen Voraussetzungen mit Hilfe von bekannten Techniken in äquivalente übliche (d.h. konjunktive) nichtlineare Probleme reformuliert bzw. durch solche approximiert werden. Die Lösung dieser Probleme mittels Standardsoftware liefert neue Algorithmen zur Behandlung von disjunktiven Problemen. Im Rahmen der Arbeit wurden die entsprechenden Algorithmen hergeleitet, implementiert und getestet. Die nichtlinearen (konjunktiven) Probleme sind geliftete Formulierungen des Originalproblems, deren auf den x-Raum projezierte zulässige Mengen zumindest eine Approximation an die zulässige Menge des disjunktiven Problems darstellen. Umgekehrt lassen sich auch bei der Lösung von GSIPs Techniken der disjunktiven Optimierung anwenden. Allerdings kann zu einem beliebigen GSIP kein äquivalentes disjunktives Problem angeben werden, da die disjunktive Struktur bei GSIPs nicht explizit, sondern lediglich inhärent vorhanden ist. Diskretisierungen von GSIPs ergeben jedoch disjunktive Probleme, welche Relaxierungen des Originalproblems darstellen. Diese können mit Hilfe von Techniken der disjunktiven Optimierung gelöst werden und im Rahmen eines Diskretisierungs-/Branch-and-Bound-Ansatzes die gegebenen Relaxierung sukzessive verbessern, um so global minimale Werte und Optimalpunkte zu approximieren. Überraschend schnell gelang gleich zu Beginn des Projektes die Umformulierung allgemeiner disjunktiver Probleme als GSIPs. Aufwendiger hingegen gestaltete sich der umgekehrte Weg, da die disjunktive Struktur lediglich inhärent im verallgemeinert semi-infiniten Problem vorhanden ist. Um disjunktive Techniken schließlich auf GSIPs anwenden zu können, war einige Vorarbeit zu leisten.
Publications
- Solving disjunctive optimization problems by generalized semi-infinite optimization techniques, Journal of Optimization Theory and Applications, 2016, 365-388
P. Kirst, O. Stein
(See online at https://doi.org/10.1007/s10957-016-0862-9) - Global optimization of disjunctive programs. Journal of Global Optimization, October 2017, Volume 69, Issue 2, pp 283–307
P. Kirst, F. Rigterink, O. Stein
(See online at https://doi.org/10.1007/s10898-017-0526-9)
