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.