Ansprechpartner

Diese E-Mail-Adresse ist vor Spambots geschützt! Zur Anzeige muss JavaScript eingeschaltet sein!
Diese E-Mail-Adresse ist vor Spambots geschützt! Zur Anzeige muss JavaScript eingeschaltet sein!
Diese E-Mail-Adresse ist vor Spambots geschützt! Zur Anzeige muss JavaScript eingeschaltet sein!

 

Kurzbeschreibung

Ziel dieses Teilprojekts ist die Analyse und Lösung großer MINLPs, insbesondere aus dem Bereich der instationären Gasnetzoptimierung, mittels adaptiver MIP-Modelle. Hierbei sollen Nichtlinearitäten zunächst stückweise-linear approximiert werden, um daraus MIP-Relaxierungen der MINLPs zu generieren. Dazu sollen theoretische Aussagen über die Komplexität der Relaxierungen, abhängig von strukturellen Eigenschaften der nichtlinearen Funktionen und des Linearisierungsfehlers, bewiesen werden, wobei bekannte Aussagen der Approximationstheorie mit Techniken der polyedrischen Kombinatorik zusammengebracht werden sollen. Weiter sollen Erkenntnisse über die polyedrische Struktur der so entstehenden MIP-Relaxierungen gewonnen werden.
Diese Erkenntnisse sollen genutzt werden, um für das in [1] vorgeschlagene MINLP-Lösungsverfahren geeignete Algorithmen zur adaptiven Verfeinerung der MIP-Relaxierungen zu entwickeln. Dabei ist zu beachten, dass in einem Verfeinerungsschritt dem Problem sowohl Variablen als auch Nebenbedingungen hinzugefügt werden, was im schlimmsten Fall einen Kaltstart des MIP-Lösungsverfahrens notwendig macht. Ein zentraler Punkt bei der Entwicklung der Verfeinerungs-algorithmen stellt daher deren Integrierbarkeit in ein Branch-and-Cut-Verfahren dar.
Die gewonnenen strukturellen Resultate sollen darüber hinaus zur Herleitung von oberen Schranken an die Komplexität von Lösungsverfahren für Klassen von nichtkonvexen MINLPs verwendet werden und in die Weiterentwicklung des in [1] vorgeschlagenen Verfahrens einfließen. Dieses soll schließlich zur Lösung von nichtkonvexen MINLPs aus der instationären Gasnetzoptimierung verwendet werden.

 

Ein Übersichtsposter aus der Begutachtung zu B07 ist hier zu finden.

 

 


[1] B. Geißler, A. Morsi, and L. Schewe. A new algorithm for MINLP applied to gas transport energy cost minimization. In M. Jünger and G. Reinelt, editors, Facets of Combinatorial Optimization, pages 321–353. Springer Berlin Heidelberg, 2013.