Direkt zum Inhalt

Lexikon der Mathematik: Ganzzahlige Optimierung

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 = (x1, …, xn) ∈ Xn, 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}

mit x1, …, xr ∈ ℕ0 und \(x_{r+1},\ldots,x_{n}\in\mathbb{R}_{0}^{+}\); in manchen Fällen ist es zudem möglich, nichtlineare Probleme mit Hilfe von Binärvariablen umzuformu-lieren oder doch wenigstens approximativ in derForm (2) zu lösen. Bei der Darstellung des zuläs-sigen Bereichs in der Form Ax = b wurde bereits ausgenutzt, daß sich jede Ungleichung mitHilfe von nichtnegativen Schlupfvariablen als eineGleichungsbedingung schreiben läßt. Diskrete Variablen x1, …, xr, die nur die beiden Werte 0 und1 annehmen können, nennt man binäre Variablen. Enthält ein Problem n Binärvariablen, so sind 2n Kombinationen möglich. Im Prinzip könnte mansich auf gemischt-binäre Probleme beschränken,da sich ganzzahlige Variablen x ∈ {0, …, N} mit Hilfe binärer Variablen xk ∈ {0, 1} als Summenx \(x={\sum}_{k=0}^{\lfloor\log_{2}N\rfloor}2^{k}x_{k}\) von Zweierpotenzen darstellen lassen. Aus numerischen Gründen ist dieses Vor-gehen jedoch nicht empfehlenswert.

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.

Ein Projektplanungssystem

Für die nächsten T Zeitperioden, z. B. T Monate, sollen in einer Firma aus einer möglichen Auswahl von P Projekten solche ausgewählt werden, die einen maximalen Gewinn ermöglichen. In jeder Zeitperiode t steht ein Kapital von Bt Euro zur Verfügung. Wird in der Zeitperiode t das Projekt p bearbeitet, so entstehen dadurch, daß z. B. Personal, Maschinen oder Räume beansprucht werden, Kosten in Höhe von Kpt Euro im Laufe der Periode und ein Erlös in Höhe von Ep Euro am Ende der Periode. Es werden binäre Variablen xp ∈ {0, 1}, p = 1, …, P, eingeführt, die den Wert 1 annehmen, wenn das Projekt p bearbeitet wird, und andernfalls 0 sind, und somit die Durchführung eines Projektes p identifizieren. Die Zielfunktion hat die Gestalt \(\mathop {\max }\limits_{{x_p}} \sum\nolimits_{p = 1}^P {{E_p}{x_p}} \), und die Constraints lauten

\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}

an, und die Constraints lauten

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

begrenzen zusammen mit der x1- und x2-Achse den zulässigen Bereich, in diesem Fall ein sehr langgezogenes schmales Dreieck mit den Lösungen zLP = 8.5(4, 4.5) und zIP = 3(1, 2), wobei sich zLP und zIP sehr deutlich sowohl hinsichtlich des Lösungsvektors als auch des Zielfunktionswertes unterscheiden. Einfache Rundungsverfahren scheiden damit offensichtlich zur Lösung diskreter Probleme aus.

Beim B&B-Verfahren wird die LP-Relaxierung jedoch in folgender Weise ausgenutzt: Ist bei der Lösung xk eines (kontinuierlichen) LP-Unterproblems Pk, k = 0, 1, 2, …, der Wert \(\bar{x}_{j}^{k}\) einer diskreten Variablen xj mit 1 ≤ jr nicht ganzzahlig, so werden zwei disjunkte Unterprobleme \(P_{\mathrm{L}}^{k}\) und \(P_{\mathrm{R}}^{k}\) erzeugt, indem zum Problem Pk 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 Pk 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 Pk bzw. Knoten Kk zu beenden, wenn eines der nachstehenden Verwerfungskriterien (engl.: pruning criteria) erfüllt ist:

  1. Die Lösung xk von Pk erfüllt alle Ganzzahligkeitsbedingungen.
  2. Das lineare (kontinuierliche) Problem Pk ist unzulässig.
  3. Die Lösung x0 = xk von Pk verletzt einige Ganzzahligkeitsbedingungen, und zk = cTxk ist kleiner als der Zielfunktionalwert zu einer eventuell schon existierenden ganzzahlig zulässigen Lösung von (2), bzw. es gilt zkzu + Δ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 zo und zu. Alle aktiven Knoten mit einer Bewertung zzu 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′ ≤ zu 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 zu einer bereits vorliegenden ganzzahligen Lösung sind.

Separierung und weitere Verzweigungen sind erforderlich, wenn die obigen Verwerfungskriterien nicht auf die optimale Lösung x0 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 dTx 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 x0 somit in beiden Teilproblemen \(\mathcal{T}_{1}(LP)\) und \(\mathcal{T}_{2}(LP)\) unzulässig ist. Beispiel: Sei x0 = 1.7. Mit (d, d0) = (3, 5) erhält man die beiden Teilprobleme: 3x ≤ 4, 3x ≥ 6; mit (d,d0) = (1, 1) erhält man die beiden Teilprobleme: x ≤ 1, x > 2.

In der Praxis sind zwei spezielle Wahlen von (d, d0), d.h. Separierungen, in Gebrauch: Die Variablen-(Zwei)Teilung und die General Upper Bound-(Zwei)Teilung; die direkte Teilung (für xj 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 = ej = j-ter Einheitsvektor im ℝn und d0 = ⌊x0⌋. Die Teilung wird also durch die beiden Ungleichungen xjd0 und xjd0 + 1 vorgenommen. Für binäre Variablen xj, d. h. 0 ≤ xj ≤ 1 und xj∉ {0, 1}, liefern diese Verzweigungen sogleich die Bedingungen xj = 0 und xj = 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}\)1 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 zu = −∞, zo = +∞ und der Knotenliste.
  2. Knotenwahl aus der Liste der aktiven Knoten.
  3. Lösung des LP-Problems → x0 und z0.
  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 KL oder KR (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 KL vor KR 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 Pk 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 UE ≥ 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 xj = ⌊xj⌋ + fj, 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 xj, 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.

2. B&C – Schnittebenenverfahren

Problemabhängig lassen sich vom Modellierer spezielle zulässige Ungleichungen (engl. : valid inequalities, cuts) ableiten, die einen Teil des zulässigen Gebietes der LP-Relaxierung abtrennen, aber die konvexe Hülle unverändert lassen. Können in einem Modell z. B. Ungleichungen der Form x + B mit positiven Konstanten A und B und Variablen \(x\in \mathbb{R}_{0}^{+}\) und α ∈ ℕ identifiziert werden, so kann das Modell verschärft werden, indem die zulässige Ungleichung \begin{eqnarray}x\ge [B-(C-1)A](C-\alpha )\end{eqnarray} hinzufügt wird, wobei C := 1 + ⌊B/A⌋ die kleinste ganze Zahl bezeichnet, die größer oder gleich dem Verhältnis B/A ist. Die Ungleichung (3) wirkt um so effizienter, je mehr sich C und B/A unterscheiden.

Abtrennen lassen sich auch spezielle Kombinationen von Binärvariablen δ ∈ {0, 1}m des m-dimensionalen Einheitswürfels. Gesucht sei nun eine zulässige Ungleichung, die genau die Kombination \(\delta^{i} :=\{\delta_{j}^{i}\mid j=1,\ldots, m\}\in \{0,\ 1\}^{m}\) mit Indexmengen \(\mathcal{B}_{1}^{i}:=\{j\mid \delta_{j}^{i}=1\}\) und \(\mathcal{B}_{0}^{i}:=\{j\mid \delta_{j}^{i}=0\}\) mit \(|\mathcal{B}_{1}^{i}|+|\mathcal{B}_{0}^{i}|=m\) trennt. Die Ungleichung \begin{eqnarray}\sum _{j\in { {\mathcal B} }_{1}^{i}}{y}_{j}-\sum _{j\in { {\mathcal B} }_{0}^{i}}{y}_{j}\le |{ {\mathcal B} }_{1}^{i}|-1\end{eqnarray} wird nur durch δi und durch keine andere Kombination δkδi verletzt. Beispiel: Sei δ ∈ {0, 1}3 und die Kombination δi = {0, 1, 0} soll ausgeschlossen werden. Dann gilt offensichtlich \(\mathcal{B}_{1}^{i}=\{2\},\ \mathcal{B}_{0}^{i}=\{1,\ 3\},\ |\mathcal{B}_{1}^{i}|=1\) und die Ungleichung lautet y2y1y3 ≤ 0 bzw. y2y1 + y3.

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.

Nichtlineare gemischt-ganzzahlige Optimierung

Bei gegebenen Freiheitsgraden \(\mathcal{N}\)\(\mathcal{P}\).

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(x1) und f(x2) des Graphen der konvexen Funktion f nie „unterhalb” des Graphen liegt, und die Tangente an einem Punkt (x0, f(x0)) des Graphen stets unterhalb von f liegt, d. h. f(x) ≥ f(x0) + f′(x0)(x–x0) 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 yi im Problem zu fixieren, das übrigbleibende, durch yi parametrisierte nichtlineare Problem zu lösen (damit wird ein Paar xi, zi = f(xi, yi) bestimmt), und dann von allen Problemen dasjenige mit kleinstem zi 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.

Exakte Verfahren zur Lösung konvexer MINLP Probleme

Deterministische oder exakte Verfahren (für konvexe Probleme) lassen sich in die folgenden 3 Hauptklassen untergliedern:

  • Branch & Bound (siehe z. B. [2]),
  • Bendersdekomposition (GBD, siehe z. B. [2]),
  • Äußere Approximation (OA, siehe z. B. [2]).

Das B&B-Verfahren für konvexe MINLP Probleme basiert auf denselben Ideen wie das LP-basierte B&B-Verfahren für MILP, besitzt jedoch hier den wesentlichen Nachteil, daß die Knoten der nachfolgenden Generation kaum Struktur ihrer Vorgängergeneration ausnutzen können wie dies bei MILP unter Verwendung des dualen Simplex-Algorithmus der Fall ist; es ist nur schwerlich auf nichtkonvexe MINLP-Probleme erweiterbar.

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 yk) 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 yk) 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].

Globale Optimierung

Das globale Minimum des Problems (4) kann ohne weitere Annahmen an Konvexität nur mit Methoden der globalen Optimierung ([4], [6], [7], [3]) bestimmt werden. Im Kontext der globalen Optimierung sollen die Variablen x und y noch der Intervallbedingung (x, y) ∈ Ixy := Ix × Iy mit Ix : = [xa,xb] und Iy := [ya,yb] unterliegen. Die exakten oder deterministischen Verfahren der globalen Optimierung verknüpfen Methoden aus der Intervallarithmetik, der Intervallreduzierung oder der konvexen Relaxierung mit B&B-Verfahren, wobei häufig spezielle Strukturen wie z. B. Bilinearformen in Zielfunktionen oder Nebenbedingungen ausgenutzt werden, und bestimmen obere und untere Schranken zo und zu für die Zielfunktion, so daß zu einer vorgegebenen positiven ε-Schranke schließlich zuf(x, y)zo und zozuε gilt. Die obere Schranke zo ergibt sich dabei als Zielfunktionswert zo = f(x, y) eines zulässigen Punktes (x, y), häufig eines lokalen Minimums(x, y), das mit einem Lösungsverfahren zur Bestimmung stationärer Punkte in einem kontinuierlichen nichtlinearen Problem oder einer Heuristik in einem MINLP Problem gewonnen wurde; die Bestimmung der oberen Schranke ist also relativ einfach. Die Bestimmung der unteren Schranke zu ist schwieriger und soll durch die folgende Methode, die auf konvexer Relaxierung beruht und mit konvexen Unterschätzern, konvexifizierten Mengen und einer B&B-Technik arbeitet, veranschaulicht werden. Eine konvexe Funktion fu heißt konvexer Unterschätzer zu einer gegeben Funktion f auf der Menge S, wenn fu(x) ≤ f(x) für alle xS. Eine konvexe Menge Mc heißt Konvexifizierung einer gegebenen Menge M, wenn McM. Die implizit durch die Ungleichungen h(x, y) ≤ 0 beschriebene zulässige Menge S (Gleichungen g(x, y) = 0 wird durch das Ungleichungspaar −δ ≤ g(x, y) ≤ δ mit beliebig kleinem δ > 0 ersetzt) werden in Verbindung mit einem auf die Variablen x bzw. y angewendeten B&B-Verfahren im Knoten k des B&B-Baumes – hier gilt zusätzlich \(({\bf{x}},{\bf{y}}) \in I_{xy}^k\) – durch eine konvexe Menge\(S_c^k\) relaxiert, indem h(x, y) ≤ 0 durch die konvexe Unterschätzung \(\mathbf{h}_{c}^{k}\left( \mathbf{x},\mathbf{y} \right)\le 0\) ersetzt wird. Über \(S_{c}^{k}\mathop{\cap }^{}I_{xy}^{k}\) wird mit Hilfe eines Verfahren, wie z. B. der Äußeren Approximation, die Lösung \(z_c^k\) des konvexen Problems \begin{eqnarray}\mathop{\min }\limits_{({\bf{x}},{\bf{y}})\in {S}_{c}^{k}{\cap }^{\text{}}{I}_{xy}^{k}}{f}_{c}^{k}({\bf{x}},{\bf{y}})\end{eqnarray} berechnet bzw.–wenn man die exakte Minimierung und den damit verbundenen Rechenaufwand vermeiden möchte– \(z_{c}^{k}\) als untere Schranke aus einem zulässigen Punkt des zu \(z_{g}^{u}:={{\min }_{{{k}'}}}z_{c}^{{{k}'}}\) folgt; mit k′ sind alle Knoten einer Generation g bezeichnet, d. h. diejenige, die zur aktuellen Teilung \({{I}_{x}}=\underset{{k}'\in g}{\mathop \cup }\,I_{x}^{{{k}'}}\) und \({{I}_{y}}=\underset{{k}'\in g}{\mathop \cup }\,I_{y}^{{{k}'}}\) der Variablenintervalle gehören. Zu allen Knoten k′ wird entsprechend durch die Bestimmung von zk’ als Zielfunktionswerte der lokalen Minima der Probleme \({{\min }_{\left( \mathbf{x},\mathbf{y} \right)\in S\mathop{\cap }^{}I_{xy}^{k}}}f\left( \mathbf{x},\mathbf{y} \right)\) die obere Schranke zu zo := mink′zk′ bestimmt. Durch immer weitere Verfeinerung der Teilung im B&B- Verfahren und dadurch bessere Anpassung der konvexen Unterschätzer \(f_{c}^{k}\left( \mathbf{x},\mathbf{y} \right)\) und \(\mathbf{h}_{c}^{k}\left( \mathbf{x},\mathbf{y} \right)\) an f(x,y) und h(x, y) wird so eine monoton wachsende ( fallende) Folge von unteren (oberen) Schranken \(z_{g}^{u}\left( z_{g}^{o} \right)\) erzeugt, für die ab einer bestimmten Verfeinerung g schließlich \(z_{g}^{o}-z_{g}^{u}\le \varepsilon \) gilt.

Literatur

[1] Bazaraa, M.; Sheraldi, H.D.,; Shetly, C.M.: Nonlinear Programming. Wiley Chichester (NY), 1993.

[2] Floudas, C.A.: Nonlinear and Mixed Integer Optimization. Oxford University Press Oxford (UK), 1995.

[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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos