MAiNGO

Der McCormick-based Algorithm for mixed-integer Nonlinear Global Optimization (MAiNGO) ist eine deterministisch globale Optimierungssoftware zur Lösung von gemischt-ganzzahligen nichtlinearen Programmen (MINLPs)

Jedes (gemischt-ganzzahlige oder kontinuierliche) nichtlineare Programm mit nicht-konvexen Funktionen kann mehrere lokale Optima besitzen. Methoden zur lokalen Optimierung können zu jeder beliebigen lokalen Lösung konvergieren oder bei einer schlechten Wahl des Initialwertes sogar daran scheitern, überhaupt einen zulässigen Punkt zu finden. Heuristische Methoden wie Evolutionäre Algorithmen oder Simulated Annealing konvergieren zum globalen Optimum mit Wahrscheinlichkeit eins nur wenn die Laufzeit gegen unendlich läuft. Im Gegensatz dazu garantieren deterministisch globale Methoden endliche Konvergenz zu einer globalen Lösung für durch den Nutzer spezifizierte, von null verschiedene Toleranzen für Zulässigkeit (δ) und Optimalität (ϵ).

MAiNGO kann MINLPs der Form
minx,yfx,y
s.t.  hx,y=0
        gx,y≤0
        x∈X∈IRnx
        y∈Y⊂Zny

bis zur globalen Optimalität mit Zulässigkeitstoleranz δ und Optimalitätstoleranz ϵ lösen beziehungsweise beweisen, dass kein δ-zulässiger Punkt existiert, wobei IR die Menge aller abgeschlossenen Intervalle in ℝ bezeichnet.

Eine der algorithmischen Besonderheiten von MAiNGO ist die Durchführung der Berechnungen in dem Raum der ursprünglichen Optimierungsvariablen (d.h. es werden keine Hilfsvariablen im Optimierungsprozess eingefügt) mit Hilfe der McCormick Relaxierungen, welche durch die open-source Bibliothek MC++ berechnet werden. Außerdem verfügt MAiNGO über eine Heuristik zur Verbesserung von McCormick Relaxierungen und spezialisierte Relaxierungen für verschiedene Funktionen (einschließlich relevanten Funktionen in der Verfahrenstechnik).

Es wurde gezeigt, dass MAiNGO Vorteile bei Problemen mit einer reduced-space Formulierung aufweist. Solche Probleme finden sich Beispielsweise bei der Fließbildoptimierung für verfahrens- oder energietechnische Prozesse, oder bei der Optimierung von hybriden Modellen mit künstlichen neuronalen Netzwerken.

Die open-source Version von MAiNGO steht hier zur Verfügung: https://git.rwth-aachen.de/avt.svt/public/maingo.git

Kontakt: MAiNGO@avt.rwth-aachen.de

Quelle: Bongartz D, Najman J, Sass S, Mitsos A. MAiNGO – McCormick-based Algorithm for mixed-integer Nonlinear Global Optimization. Technical Report, Process Systems Engineering (AVT.SVT), RWTH Aachen University, 2018. Available at http://permalink.avt.rwth-aachen.de/?id=729717

Danksagung: MAiNGO wurde am Lehrstuhl für Systemverfahrenstechnik (AVT.SVT) der RWTH Aachen mit Mitteln verschiedener öffentlicher Institutionen entwickelt.