Einführender Überblick

Optimierung im mathematischen Sinne bedeutet die Bestimmung des Maximums oder Minimums einer reellwertigen Funktion über einem (beschränkten) Bereich oder Zustandsraum S und des Arguments, für das die Funktion diesen Extremwert annimmt. Die klassische, auf der Differentialrechnung beruhende Optimierungstheorie mit ihren Spezialdisziplinen beschränkte kontinuierliche Optimierung, Variationsrechnung und Optimale Steuerung behandelt die Fälle, in denen S kontinuierlich ist, d. h. in jeder noch so kleinen Umgebung eines zulässigen Punktes in S existieren unendlich viele weitere zulässige Punkte. Die ganzzahlige (gemischt-ganzzahlige), manchmal auch synonym, aber nur bedingt zutreffend diskrete oder kombinatorische Optimierung genannt, bis vor 1980 noch ein Randgebiet der Wissenschaft und Teilgebiet der mathematischen Optimierung, spielt eine zunehmend bedeutsamere Rolle und behandelt Optimierungsprobleme, in denen alle (einige) Freiheitsgrade diskret, d. h. z. B. auf die ganzen Zahlen ℤ beschränkt sind. Die Ganzzahligkeits- bedingungen rühren bei praktischen Fragestellungen z. B. daher, daß Null-Eins-Entscheidungen – etwa die Entscheidung, ob ein Arbeitsschritt von einem bestimmten Mitarbeiter zu einem Zeitpunkt bearbeitet wird oder nicht – zu treffen sind, oder zu bestimmende Größen – z. B. die Zahl der Komponenten in einer Mischung oder das Containervolumen – nur ganzzahlige oder nur bestimmte diskrete Werte annehmen können. Einige Spezialfälle der ganzzahligen Optimierung, die Linear-Gemischt- Ganzzahlige Optimierung (MILP; engl. : mixed integer linear programming) und die Nichtlineare- Gemischt-Ganzzahlige Optimierung (MINLP; engl. : mixed integer nonlinear programming) werden zunehmend in den Gebieten Logistik, Transport, Produktionsplanung, Finanzen, Kommunikation und Design eingesetzt, zum Teil auch deshalb, weil sichmit ihrer Hilfe und insbesondere durch die Verwen-dung von Binärvariablen – dies sind Variablen, dienur die Werte 0 und 1 annehmen können – Pro-bleme der kombinatorischen Optimierung wie dasRundreiseproblem (engl.: traveling salesman pro-blem), Maschinenbelegungsprobleme, Reihenfolge-probleme (engl.: sequencing problems), Transport-und Zuordnungsprobleme (engl.: assignment pro-blem) formulieren lassen. Wenn nicht synonym zurganzzahligen Optimierung gebraucht, versteht manunter kombinatorischen Optimierungsproblemenjene Probleme, bei denen erheblich mehr ganzzah-lige als kontinuierliche Variablen vorhanden sind,die ganzzahligen Variablen nur wenige Werte an-nehmen können, die Nebenbedingungen begrifflicheinfach, aber mathematisch schwierig beschreib-bar sind, und sich das Problem eher graphentheo-retisch formulieren läßt [4].

Die Grundlagen der Algorithmen gemischt-ganzzahliger Optimierung sind nach wie vor Ver-zweigungsverfahren (Branch & Bound-Verfahren).Mittlerweile können infolge leistungsfähiger Algo-rithmen, Hardware und Software sehr große Pro-bleme gelöst werden; bekannt sind Probleme miteinigen Tausend Binärvariablen, 200000-300000kontinuierlichen Variablen und 120000 Cons-traints, die in weniger als 15 Minuten auf einemPC gelöst werden. In der gemischt-ganzzahligenOptimierung spielt die Modellbildung ([9], [13])und die Erfahrung eine wesentliche Rolle. DieWahl der richtigen Variablen und die geeigneteFormulierung ihrer Beziehungen zueinander,nicht die Zahl der Variablen und Constraints istsignifikant. Das Kriterium, das eine gute von einerschlechten Formulierung trennt, ist – im Falleder MILP – a) die Distanz der LP-Relaxierung(das ursprüngliche MILP-Problem unter Vernachlässigung der Ganzzahligkeitsbedingungen) vonder konvexen Hülle (das kleinste Polyeder, dassämtliche Zulässigkeitsbedingungen enthält), undb) die Rechenzeit zur Bestimmung der Lösung.

Bei gegebenen Freiheitsgraden x = (x₁, …, x_n) ∈ Xⁿ, Zielfunktional f(x) und Beschränkungen oderConstraints g(x) und h(x) heißt ein Optimierungs-problem

\begin{eqnarray}\mathop {\min }\limits_{{\text{x}} \in S} \{ {{\text{c}}^{\text{T}}}{\text{x}}\} \,,\,S: = \,\{ {\text{x}}|{\text{Ax}}\, = \,{\text{b}}\} \end{eqnarray}

Beispiele: Im folgenden soll anhand einiger Bei-spiele verdeutlicht werden, wie praktische Situationen als MILP-Probleme formuliert werden können. Dabei zeigt sich, daß diskrete Variablen im wesentlichen zur Modellierung nichtteilbarer Größen, Minimalgrößen, ja/nein-Entscheidungen und logischer Bedingungen verwendet werden.

\begin{eqnarray}\max Z\, = \,\mathop {\mathop \sum \limits^N }\limits_{j = 1} {P_j}{x_j}\, – \,\mathop {\mathop \sum \limits^N }\limits_{j = 1} ({K_j}{\delta _j} + {C_j}{x_j})\end{eqnarray}

\begin{eqnarray}{g_1}:{x_2} = {x_1} + \frac{1}{2};\,\,{g_2}:{x_2} = 0.8{x_1} + 1.3\end{eqnarray}

Beim B&B-Verfahren wird die LP-Relaxierung jedoch in folgender Weise ausgenutzt: Ist bei der Lösung x^k eines (kontinuierlichen) LP-Unterproblems P^k, k = 0, 1, 2, …, der Wert \(\bar{x}_{j}^{k}\) einer diskreten Variablen x_j mit 1 ≤ j ≤ r nicht ganzzahlig, so werden zwei disjunkte Unterprobleme \(P_{\mathrm{L}}^{k}\) und \(P_{\mathrm{R}}^{k}\) erzeugt, indem zum Problem P^k die Ungleichungen \(x_{j}\le\lfloor\bar{x}_{j}^{k}\rfloor\ \mathrm{bzw}.\ x_{j}\ge\lfloor\bar{x}_{j}^{k}\rfloor+1\) hinzugefügt werden, mit der entier-Funktion (Ganzteilfunktion) \(\lfloor\bar{x}_{j}^{k}\rfloor\), die die Variable \(\bar{x}_{j}^{k}\) auf die größte ganze Zahl abbildet, die \(\bar{x}_{j}^{k}\) nicht überschreitet.

Bei der Lösung der (kontinuierlichen) LP-Unterprobleme \(P_{\mathrm{L}}^{k}\) und \(P_{\mathrm{R}}^{k}\) kann auf die bekannte Lösung P^k zurückgegriffen werden, indem die zusätzlichen Ungleichungen hinzugefügt werden und dann der duale Simplex-Algorithmus eingesetzt wird.

Die Sondierung ermöglicht, eine Verzweigung in einem Unterproblem P^k bzw. Knoten K^k zu beenden, wenn eines der nachstehenden Verwerfungskriterien (engl.: pruning criteria) erfüllt ist:

1. Die Lösung x^k von P^k erfüllt alle Ganzzahligkeitsbedingungen.
2. Das lineare (kontinuierliche) Problem P^k ist unzulässig.
3. Die Lösung x⁰ = x^k von P^k verletzt einige Ganzzahligkeitsbedingungen, und z^k = c^Tx^k ist kleiner als der Zielfunktionalwert z^u einer eventuell schon existierenden ganzzahlig zulässigen Lösung von (2), bzw. es gilt z^k ≤ z^u + Δz mit einem passend gewählten addcut Δz, der eine sinnvolle Trennung der Knoten gewährleistet (Dominanzkriterium).

Andernfalls werden durch Hinzufügung weiterer Ungleichungen zwei Unterprobleme \(P_{\mathrm{L}}^{k}\) und \(P_{\mathrm{R}}^{k}\) generiert. Mit Hilfe der Variablenwahl und der Knotenwahl läßt sich der Algorithmus steuern und die Effizienz der Methode steigern. Die LP-Relaxierung und die im Suchbaum gefundenen Lösungen von (2) dienen als obere und untere Schranken z^o und z^u. Alle aktiven Knoten mit einer Bewertung z ≤ z^u brauchen nicht weiter untersucht zu werden. Sind alle aktiven Knoten abgearbeitet, so ist entweder eine optimale Lösung von (2) bestimmt oder nachgewiesen, daß (2) keine Lösung besitzt. Es sei bemerkt, daß das hier skizzierte B&B-Verfahren auch kein besseres als exponentielles Laufzeitverhalten garantiert, sich aber in der Praxis bewährt hat.

Eine wesentliche Komponente des B&B-Verfah- rens ist es, den Suchbaum so zu durchlaufen, daß möglichst viele Teile davon aufgrund obiger Verwerfungskriterien verworfen werden können. Wird das Dominanzkriterium aktiv, so endet die Verzweigung im Baum, da die Fortführung weitere Constraints einbeziehen und somit zu Zielfunktionswerten z′ ≤ z^u führen würde. Insbesondere die Einführung des addcuts Δz kann sehr nützlich sein. Ist z. B. die Zielfunktion in einem Maximie- rungsproblem ganzzahlig, so werden mit Δz = 1 lediglich noch die Kandidaten betrachtet, die mindestens um eins größer als der Zielfunktionswert z^u einer bereits vorliegenden ganzzahligen Lösung sind.

Separierung und weitere Verzweigungen sind erforderlich, wenn die obigen Verwerfungskriterien nicht auf die optimale Lösung x⁰ des vorliegenden LP zutreffen. Beschränkt man sich auf, binäre‘ Separierung, so wird die für x zulässige Menge \(\mathcal{T}\) in zwei disjunkte Mengen \(\mathcal{T}=\mathcal{T}_{1}\cup\mathcal{T}_{2}\) geteilt, \begin{eqnarray}\begin{array}{l}{{\mathscr{T}}}_{1}={\mathscr{T}}\cap \{x\in {{\mathbb{R}}}_{+}^{n}|{\text{d}}^{\text{T}}\text{x}\le {d}_{0}\}\\ {{\mathscr{T}}}_{2}={\mathscr{T}}\cap \{x\in {{\mathbb{R}}}_{+}^{n}|{\text{d}}^{\text{T}}\text{x}\ge {d}_{0}+1\},\end{array}\end{eqnarray} wobei es sich bei d um einen Vektor und bei d^Tx um das Skalarprodukt handelt. Hierbei wird \((\mathbf{d},d_{0})\in\mathbb{N}_{+}^{n+1}\) so gewählt, daß \begin{eqnarray}{d}_{0}\le {\bf{d}}^{\text{T}}{\bf{x}}^{0}\le {d}_{0}+1\end{eqnarray} ist, und x⁰ somit in beiden Teilproblemen \(\mathcal{T}_{1}(LP)\) und \(\mathcal{T}_{2}(LP)\) unzulässig ist. Beispiel: Sei x⁰ = 1.7. Mit (d, d₀) = (3, 5) erhält man die beiden Teilprobleme: 3x ≤ 4, 3x ≥ 6; mit (d,d₀) = (1, 1) erhält man die beiden Teilprobleme: x ≤ 1, x > 2.

In der Praxis sind zwei spezielle Wahlen von (d, d₀), d.h. Separierungen, in Gebrauch: Die Variablen-(Zwei)Teilung und die General Upper Bound-(Zwei)Teilung; die direkte Teilung (für x_j die separate Betrachtung jeden ganzzahligen Wertes des Intervalls \(0\le x_{j}\ge X_{j}^{+}\)) erweist sich in der Praxis als ineffizient und findet keine Verwendung.

Bei der Variablen-(Zwei)Teilung ([11]) wählt man d = e_j = j-ter Einheitsvektor im ℝⁿ und d₀ = ⌊x⁰⌋. Die Teilung wird also durch die beiden Ungleichungen x_j ≤ d₀ und x_j ≥ d₀ + 1 vorgenommen. Für binäre Variablen x_j, d. h. 0 ≤ x_j ≤ 1 und x_j∉ {0, 1}, liefern diese Verzweigungen sogleich die Bedingungen x_j = 0 und x_j = 1. Ein wesentlicher Vorteil der Variablen-Teilung besteht darin, daß diese nur einfache untere und obere Schranken als weitere Restriktionen zum bestehenden LP- Unterproblem hinzufügt. Damit kann direkt das duale Simplex-Verfahren angewendet werden; die Basis vergrößert sich nicht.

Die GUB-(Zwei)Teilung wird vorgenommen, wenn das Problem eine Bedingung der Form \({\sum}_{j\in Q}x_{j}=1\) enthält. Ist \(\mathcal{Q}\)₁ eine nichtleere Teilmenge von \(\mathcal{Q}\), so erfolgt die Teilung gemäß \({\sum}_{j\in Q_{1}}x_{j}=0\) und \({\sum}_{j\in Q\setminus Q_{1}}x_{j}=0\).

Das B&B-Verfahren läßt sich damit in die folgende Schleifenstruktur mit Schritten 1-5 fassen:

1. Initialisierung der Schranken z^u = −∞, z^o = +∞ und der Knotenliste.
2. Knotenwahl aus der Liste der aktiven Knoten.
3. Lösung des LP-Problems → x⁰ und z⁰.
4. Test der Verwerfungskriterien: evtl. Schrankenverbesserung, → Schritt 2, oder → Schritt 5.
5. Variablenwahl und Wahl der Verzweigungsrichtung, schätze Degradierung der ganzzahligen Lösung und obere Schranke, füge die beiden neuen Unterprobleme zur Liste der aktiven Knoten hinzu → Schritt 2.

Durch geeignete Nutzung der heuristischen Freiheitsgrade (Knotenwahl, Richtungswahl, Variablenwahl) läßt sich die Effizienz des Verfahrens erheblich verbessern.

Die Knotenwahl kann nach zwei komplementären Strategien erfolgen: a priori-Regeln, bei denen man im vorhinein fixiert, wie der Entscheidungsbaum durchlaufen wird, und adaptive Regeln, die Informationen über die aktuellen Knoten mit einbeziehen. Zunächst sei die Tiefensuche (engl.: depth-first search) mit backtracking betrachtet. Kann ein vorliegender Knoten K nicht verworfen werden (pruned), so wird als nächstes einer seiner durch ihn erzeugten Knoten K_L oder K_R (seine Söhne) untersucht. Backtracking bedeutet, daß nach Verwerfung eines Sohnes der Baum zurückverfolgt wird, bis ein noch nicht bearbeiteter Sohn gefunden wird. Beschließt man noch, daß stets K_L vor K_R untersucht wird, so liegt eine vollständige Fixierung der Verzweigungswege im Sinne der a priori-Regel vor. Mit dieser Strategie sind zwei wichtige Vorteile verbunden:

• Die LP-Unterprobleme \(P_{\mathrm{L}}^{k}\) und \(P_{\mathrm{R}}^{k}\) erhält man aus P^k durch Hinzufügen einer einfachen upper oder lower bound constraint. Dieses Problem kann in vielen Fällen direkt mit dem dualen Simplex-Verfahren ohne aufwendige Matrixinversion gelöst werden.
• Bei vielen praktischen Problemen findet man ganzzahlig zulässige Lösungen eher in der Tiefe als in der Breite des Suchbaumes. Dies müssen allerdings nicht notwendigerweise bereits gute Lösungen sein.

Im Gegensatz zur Tiefensuche werden bei der Breitensuche (engl. : breadth-first) zunächst sämtliche Knoten einer bestimmten Ebene untersucht, bevor man zur nächst tieferen Ebene fortschreitet. Ein Nachteil dieser Methode ist, daß man sehr viele Knoten generiert. Innerhalb dieser Strategie oder auch in anderen adaptiven Knotenwahlverfahren können die folgenden heuristischen Auswahlregeln eingesetzt werden:

• Wahl des Knoten mit der größten oberen Schranke in der Hoffnung, daß auch die nachfolgenden Knotengenerationen noch möglichst große Werte liefern und damit, wenn man einen zulässigen Knoten findet, eine möglichst gute untere Schranke gefunden werden kann.
• Das Verfahren der besten Schätzung wählt einen Zweig, der höchstwahrscheinlich die optimale Lösung enthält.
• Beim Forrest-Hirst-Tomlin-Kriterium mit \(\max\frac{U-L}{U-E}\) werden jene Knoten mit möglichst kleiner Differenz U – E ≥ 0 aus oberer Schranke und Schätzung bevorzugt, bzw. auch jene Knoten, bei denen die Schätzung E größer als die untere Schranke L ist.

Für die Variablenwahl bieten sich vom Modellierer vorgegebene Prioritäten oder geschätzte Degradierung und Penalisierung an. Der Hintergrund des ersten Verfahren ist, daß der Benutzer noch am besten die ökonomische Relevanz und den Einfluß bestimmter Variablen abschätzen kann. Oft zeigt es sich, daß nach der Fixierung einiger weniger frak- tionaler Variablen sämtliche anderen automatisch zulässig werden. Die Abschätzung der Degradierung versucht, ausgehend von einer vorliegenden Variablen x_j = ⌊x_j⌋ + f_j, die Verringerung \(D_{j}^{-}=p_{j}^{-}f_{j}\) und \(D_{j}^{+}=p_{j}^{+}(1-f_{j})\) des Zielfunktionals für den linken und rechten Sohn abzuschätzen, wobei die Koeffizienten \((p_{j}^{-},\ p_{j}^{+})\) z.B. aus Informationen des dualen Simplex-Verfahrens abgeleitet werden können. Ein mögliches Kriterium ist das der maximum integer feasibility\((p_{j}^{-}=p_{j}^{+}=1)\), d.h. max \(\min(D_{j}^{-},D_{j}^{+})\). Dieses Verfahren basiert auf der Annahme, daß jene Variable x_j, deren kleinste Verringerung hinsichtlich ihrer Söhne, also \(\min(D_{j}^{-},D_{j}^{+})\), von allen Variablen die maximale ist, wohl von besonderer Bedeutung sein muß, wenn man Ganzzahligkeit erreichen möchte. In diesem Fall wird man als nächstes auch den Sohn mit der kleineren Degradierung in der Zielfunktion wählen. Das alternative Kriterium max \(\max(D_{j}^{-},D_{j}^{+})\) geht insbesondere bei Kenntnis einer unteren Schranke davon aus, daß jene Variablen, die einen maximalen Abstieg versprechen, leicht zu Zielfunkti onswerten führen können, die unterhalb der unteren Schranke liegen und damit zur Verwerfung des Knotens führen; entsprechend wird man hier den Sohn mit \(\max(D_{j}^{-},D_{j}^{+})\) wählen.

Zulässige Ungleichungen können statisch oder je nach Bedarf dynamisch zum Modell hinzugefügt werden. Bei den dynamischen Verfahren werden cuts gezielt eingesetzt, um in einem B&B Verfahren fraktionale Werte von Variablen, die der Ganzzahligkeitsbedingung unterliegen, abzutrennen. Hierzu zählen Schnittebenen- (engl.: cutting plane methods) und Branch&Cut-Verfahren (B&C), die inzwischen in einigen kommerziellen Softwarepaketen zu finden sind.

Schnittebenenverfahren wurden 1958 von Gomory eingeführt und basieren auf dem Konzept der oben eingeführten cuts. Der B&C Algorithmus kombiniert Grundzüge des B&B-Verfahrens und der Schnittebenenverfahren und verfährt ähnlich wie die B&B Methode, allerdings werden in jedem Schritt weitere cuts hinzugefügt, um sukzessive fraktionale Werte der Variablen auszuschließen. Es handelt sich auch hier um ein Baumsuchverfahren, allerdings tritt zu oder auch anstelle der Verzweigung auf eine bestimmte Variable das Hinzufügen eines weiteren Schnittes. B&C funktioniert in zwei verschiedenen Varianten. Im einfachen Verfahren werden nur cuts im Sinne zulässiger Ungleichungen hinzugefügt; hierbei werden u. U. sehr viele, aber nicht notwendigerweise sehr wirkungsvolle cuts addiert. Im zweiten Verfahren werden nur Ungleichungen (Schnitte) hinzugefügt, die bezüglich eines lokalen Knotens (wegen bereits erfolgter Verzweigungen) eine zulässige Ungleichung darstellen, nicht aber hinsichtlich des ganzen Problems; hierbei wird insbesondere darauf geachtet, einen Schnitt hinzuzufügen, der tatsächlich durch die Annahme fraktionaler Werte verletzt wird; sein Hinzufügen bewirkt, daß fraktionale Werte ausgeschlossen werden. Sinnvollerweise werden cuts, die nicht mehr wirkungsvoll sind, auch wieder dynamisch entfernt. Neben den cuts, die von einem erfahrenen Modellierer konstruiert werden können, bietet kommerzielle MILP Software inzwischen die Möglichkeit an, zu prüfen, ob ein Modell durch bestimmte Standard-cuts, z. B. Gomory cuts, verbessert werden kann.

Obwohl MILP-Probleme häufig kombinatorische Optimierungsprobleme mit einer exponentiell wachsenden Anzahl von ganzzahlig-zulässigen Punkten sind, wurden hierzu effiziente, auf LP- Relaxierung beruhende B&B-Verfahren entwickelt, die in endlich vielen Schritten Optimalität beweisen. Algorithmen [1] zur Bestimmung lokaler Lösungen nichtlinearer kontinuierlicher Optimierungsprobleme (NLP-Probleme) beruhen dagegen auf den Konvergenzprinzipien der Analysis, arbeiten iterativ und können nur in Ausnahmefällen in einer endlichen Anzahl von Schritten exakt gelöst werden. Dennoch ist die Lösung von (zumindest konvexen) NLP-Problemen in gewisser Weise einfacher als die Lösung von MILP Problemen, da sich unter Verwendung von sequentieller quadratischer Optimierung oder Innere-Punkte Methoden meist ein Konvergenzverhalten zweiter Ordnung einstellt und somit die Lösung recht schnell bestimmt werden kann.

MINLP Probleme vereinigen die Schwierigkeiten beider Teilklassen: MILP und NLP, aber sie besitzen darüber hinaus noch einige Eigenschaften, die einzigartig in dem Sinn sind, daß sie weder bei NLP noch bei MILP Problemen auftreten. Während bei konvexen NLP Problemen mit der Bestimmung eines lokalen Minimums bereits das globale Minimum bestimmt ist, ist dies bei MINLP Problemen z. B. nicht der Fall.

Lösungsalgorithmen, die das oben gestellte Optimierungsproblem (4) exakt, d. h. bis auf jede vorgegebene ε-Schranke lösen können, werden in der globalen Optimierung entwickelt. Spezielle MINLP Algorithmen wurden konstruiert, die ausnutzen, daß die Menge des zulässigen Bereichs und die Zielfunktion konvex sind. Hierbei wird ausgenutzt, daß die Verbindungsgerade zweier Punkte f(x₁) und f(x₂) des Graphen der konvexen Funktion f nie „unterhalb” des Graphen liegt, und die Tangente an einem Punkt (x₀, f(x₀)) des Graphen stets unterhalb von f liegt, d. h. f(x) ≥ f(x₀) + f′(x₀)(x–x₀) für alle x. Die Lösungsverfahren für das Problem (4) teilen sich in die Klasse der deterministischen oder exakten und heuristischen Methoden. Allen deterministischen Verfahren ist gemeinsam, daß sie sich einer vollständigen Enumerierung eines Such-Baums bedienen bzw. Regeln implementieren, um die Suche durch Unterbäume zu begrenzen oder ganz zu vermeiden. Deterministische Verfahren erbringen den Nachweis, daß eine bestimmte gefundene Lösung optimal ist. Heuristische Verfahren sind nicht in der Lage, diesen Nachweis zu erbringen. Sieht man von den Methoden der globalen Optimierung ab, so können in den meisten Fällen bei nicht-konvexen Problemen nur Heuristiken angewendet werden.

Ein offensichtlich exaktes Verfahren besteht z. B. darin, sämtliche Kombinationen U diskreter Variabler y_i im Problem zu fixieren, das übrigbleibende, durch y_i parametrisierte nichtlineare Problem zu lösen (damit wird ein Paar x_i, z_i = f(x_i, y_i) bestimmt), und dann von allen Problemen dasjenige mit kleinstem z_i auszuwählen (dieses sei mit i^* bezeichnet), sodaß die Lösung des Problems durch das Tripel \(({\bf{x}}* = {{\bf{x}}_{i*}},{\bf{y}} = \,{{\bf{y}}_{i*}},z_i^* = f({{\bf{x}}_{i*}},{{\bf{y}}_{i*}}))\) repräsentiert wird. Dieses Verfahren funktioniert natürlich nur dann, wenn U nur endlich viele Elemente enthält und die nichtlinearen Unterprobleme die Bestimmung des globalen Minimums erlauben. Dies ist zwar bei konvexen (kontinuierlichen) Problemen der Fall, aber auch hier verbieten sich diese Methoden wegen des enormen Rechenaufwandes.

Das auf Bendersdekomposition beruhende Verfahren von Geoffrion (1972) (siehe z. B. [2]) unterteilt die Variablen in zwei Mengen schwieriger und nicht-schwieriger Variablen, wobei die diskreten Variablen des MINLP-Modells meist zu den schwierigen zählen. Dann wird eine Folge von NLP-Unterproblemen (erzeugt durch Fixierung der Binärvariablen y^k) und MILP Master-Problemen im Raum der „schwierigen” Variablen gelöst. Die Unterprobleme liefern eine Folge oberer Schranken \(z_i^u\).

Äußere-Approximations-Verfahren (engl. : outer approximation, OA), wie z. B. das von Grossmann (1986) (siehe z. B. [2]) konstruierte, verwenden ebenfalls eine Folge von NLP Unterproblemen (erzeugt durch Fixierung der Binärvariablen y^k) und MILP Master-Problemen. Der wesentliche Unterschied besteht in der Definition der Master-Probleme. Bei OA werden die Master-Probleme durch „äußere Approximationen” (Linearisierungen) der nichtlinearen Constraints in den Punkten erzeugt, die die optimale Lösungen der NLP-Teilprobleme sind. Bei konvexen MINLP Problemen wird damit eine Obermenge des zulässigen Bereichs erzeugt, sodaß die OA Master-Probleme (MILP Problem in allen Variablen) wieder eine monoton wachsende Folge von unteren Schranken \(z_i^u\) liefern.

GBD und OA terminieren, wenn \(z_i^o – z_i^u\) kleiner als ein vorgegebener, positiver Wert ε wird. Während das GBD Master-Problem kleiner in der Zahl der Variablen und Constraints ist, liefert der OA Algorithmus schärfere untere Schranken und benötigt weniger Iterationen. Für bestimmte Klassen von NLP Problemen kann die Optimalität sogar bewiesen werden, und für GBD und OA existieren inzwischen heuristische Erweiterungen, die die Behandlung nichtkonvexer MINLP Probleme erlauben, nunmehr zwar keine Optimalität mehr beweisen können, aber dennoch in der Praxis erfolgreich Anwendung finden [8].

[3] Floudas, C.A.: Deterministic Global Optimization: Theory, Algorithms and Applications. Nonconvex Optimization and its Applications. Kluwer Academic Publishers Dordrecht, 2000.

[4] Graham, R.; Grötschel, M.; Lovász, L. (eds.): Handbook on Combinatorics. North Holland Dordrecht, 1982.

[5] Horst, R.; Pardalos, P.M.: Handbook of Global Optimization. Kluwer Academic Publishers Dordrecht, 1995.

[6] Horst, R.; Pardalos, P.M.; Van Thoai, N.: Introduction to Global Optimization. Kluwer Academic Publishers Dordrecht, 1996.

[7] Horst, R.; Tuy, H.: Global Optimization: Deterministic Approaches. Springer New York, 1996.

[8] Johnson, E.L.; Ciriani, T.A.; Gliozzi, S.; Tadei, T.: Operational Research in Industry. Macmillan, Houndsmill, Basingstoke (UK), 1999.

[9] Kallrath, J.; Wilson, J.M.: Business Optimisation Using Mathematical Programming. Macmillan Houndsmill, Basingstoke (UK), 1997.

[10] Kallrath J.: Diskrete Optimierung in der Industrie. Vieweg Wiesbaden, 2001.

[11] Nemhauser, G.L.; Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley Chichester (NY), 1988.

[12] Spelluci, P.: Numerische Verfahren der nichtlinearen Optimierung. Birkhäuser Verlag Basel, 1993.

[13] Williams, H.P.: Model Building in Mathematical Programming. Wiley Chichester (NY), 1993.