Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis

Frontmatter

1. Einführung: Modelle, Modellbildung und Optimierung

Zusammenfassung

Dieses Kapitel beginnt mit einem kurzen Überblick zur Geschichte der Optimierung, speziell der gemischt-ganzzahligen Optimierung, wobei vorgreifend schon einige Begriffe verwendet, die erst im späteren Verlauf des Buches erläutert werden. Da bei der gemischt-ganzzahligen Optimierung die Modellierung eine besondere Rolle spielt, wird ihr in diesem Kapitel ein eigener Abschnitt unter dem Titel „Zur Bedeutung von Modellen“ gewidmet. Schließlich werden das grundsätzliche Vorgehen bei Optimierungsproblemen und die wesentlichen Elemente eines Optimierungsmodells, das sind die Variablen, die Nebenbedingungen und die Zielfunktion, einführend diskutiert.

Josef Kallrath

2. Einführende motivierende Beispiele

Zusammenfassung

In diesem Kapitel werden einige einführende Beispiele zur Modellbildung linearer, linearer gemischt-ganzzahliger und nichtlinearer kontinuierlicher Optimierungsprobleme gegeben, die den Leser mit den Bausteinen eines Optimierungsmodells, d.h. Daten, Variablen, Nebenbedingungen und Zielfunktion, vertraut werden lassen sollen und ihn in die Lage versetzen sollen, erste Modellformulierung selbständig vorzunehmen. Dabei wird auf die schon in Kapitel 1 gelegten allgemeinen Grundlagen zur Modellbildung Bezug genommen. Bei den noch recht übersichtlichen Problemen, die sich aus echten Problemen ableiten, hier aber dazu dienen, bestimmte Strukturen herauszuarbeiten, ist es noch möglich, die Probleme exakt in einem mathematischen Modell abzubilden. In den später behandelten größeren Problemen wird man bemüht sein, soviel Realität wie nötig und sinnvoll abzubilden, aber doch auch Vereinfachungen vorzunehmen.

Josef Kallrath

3. Optimierung in der Praxis

Zusammenfassung

In diesem Kapitel wird beschrieben, in welcher Weise die Modellbildung im gesamten Projektverlauf in den Lösungsprozess eines realen Problems eingebettet ist. Dabei werden einige Aspekte aufgegriffen, die in der Praxis hilfreich sein können, wenn mathematische Optimierung eingesetzt werden soll. Hierzu zählt, das Problem zu erfassen, die Kommunikation und rege Interaktion mit dem Kunden, wobei auch die Verfügbarkeit und Strukturierung der Daten, die Datenhaltung sowie Fragen nach einer möglichen graphischen Benutzeroberfläche geklärt werden müssen. Diese Aspekte sollten vor allem in der Vor- oder Frühphase eines Projektes in die Strukturierung des Projektes einfliessen. Im Umfeld der Ergebnisdiskussion werden einige Begriffe wie z.B. Schattenpreise und reduzierte Kosten konzeptionell und ohne mathematischen Formalismus eingeführt.

Josef Kallrath

4. Grundlagen der Mathematischen Lösungstechniken

Zusammenfassung

Dieses Kapitel gibt einen einführenden Überblick über den mathematischen und algorithmischen Hintergrund der linearen Programmierung (LP), linearen gemischt-ganzzahligen Programmierung (MILP), nichtlinearen kontinuierlichen Programmierung (NLP), der nichtlinearen gemischt-ganzzahligen Programmierung (MINLP) und schließlich der Globalen Optimierung (GO). Mit diesen Ansätzen lassen sich das Problem (1.8.1) auf Seite 14 oder Spezialfälle davon lösen. Eine strengere und ausführlichere mathematische Behandlung einiger Aspekte ist dem Anhang A vorbehalten. Insbesondere wird der Leser in diesem Kapitel mit den folgenden Themen vertraut gemacht:

• Standardformulierung von LP-Problemen;
• Gebrauch von Schlupf- und Überschussvariablen;
• Simplexverfahren, Abbruchkriterien und Optimalitätsbeweis;
• Innere-Punkte-Methoden (engl: interior point methods, IPM);
• Branch&Bound-Verfahren zur Lösung von MILP- und MINLP-Problemen sowie einigen grundlegenden Prinzipien bei der Verwendung von Branch & Cut-Verfahren;
• Grundlagen der Dualitätstheorie;
• Interpretation dualer Variablen (Schattenpreise) und reduzierter Kosten;
• Bestimmung zulässiger Lösungen von Optimierungsproblemen;
• notwendige und hinreichende Bedingungen bei NLP-Problemen;
• lokale und globale Optima bei nichtkonvexen Optimierungsproblemen.

Josef Kallrath

5. Die Kunst guter Modellierung

Zusammenfassung

In diesem Kapitel wird die Modellierung verschiedener spezieller Konstrakte vorgestellt, die in praktischen Problemen auftreten. Dazu zählen logische Relationen, die sich mit Hilfe von Binärvariablen beschreiben lassen, aber auch bestimmte nichtlineare Strukturen, die in gemischt-ganzzahlige Formulierungen transformiert werden können. Zudem werden Methoden behandelt, mit denen sich die Rechenzeit ganzzahliger Probleme erheblich reduzieren lässt. Hierzu zählen eine gute Modellbildung, die Verwendung spezieller Verzweigungstechniken und eine Kontrolle der Branch & Bound-Strategien.

Josef Kallrath

6. Lineare Optimierung in der Praxis

Zusammenfassung

Dieses Kapitel enthält einige Fallstudien zur Linearen Optimierung, die aus realen Problemen hervorgegangen sind und erfolgreich gelöst werden konnten: die Optimierung der Produktion eines chemischen Reaktors, ein augenscheinliches nicht lineares Mischungsproblem, das sich unter Ausnutzung bestimmter Monotonieeigenschaften in ein lineares Problem transformieren lässt, und ein Verschnittproblem aus der Papierindustrie. Sämtliche Probleme besitzen Erweiterungen im Kontext ganzzahliger Optimierung.

Josef Kallrath

7. Gemischt-ganzzahlige lineare Optimierung in der Praxis

Zusammenfassung

Dieses Kapitel enthält Fallstudien zunehmender Komplexität zur gemiseht-ganzzahligen linearen Optimierung und beginnt mit einem Standortplanungsproblem. Die nächste Gruppe von Fallstudien betrachtet ein Vertragsallokationsproblem, ein Metallverschnittproblem und ein Projektplanungsproblem, aus dem ein allgemeiner Projekt-Ressourcen-Planner konzipiert wird. Schließlich wird ein Routenplanungsproblem formuliert.

Josef Kallrath

8. Nichtlineare Optimierung in der Praxis

Zusammenfassung

In diesem Kapitel werden einige typische Probleme beschrieben, die auf nichtlineare, kontinuierliche Formulierungen führen. Hierzu zählen Probleme aus der Mineralölindustrie, insbesondere das Pooling-Problem, für das häufig spezielle Lösungstechniken (Rekursion und Sequentielle Lineare Programmierung) angewendet werden. Weiterhin wird gezeigt, wie man quadratische Optimierungsprobleme als gemischt-ganzzahlige Probleme löst.

Josef Kallrath

9. Gemischt-ganzzahlige nichtlineare Optimierung in der Praxis

Zusammenfassung

Gemischt-ganzzahlige nichtlineare Optimierung wird zunehmend in der Verfahrenstechnik der chemischen Industrie, in der Produktionsplanung und bei Schedulingproblemen in Raffinerien, beim Design von Stromkreisen oder auch bei der Konstruktion von Anlageinstrumenten in der Finanzwelt angewendet. Winter & Zimmermann (2000, [218]) formulieren eine Fragestellung aus dem Verkehrswesen, ein Strassenbahnabfertigungsund Rangierproblem, als quadratisches Zuordnungsproblem und lösen dieses mit Hilfe exakter Methoden (dynamische Optimierung) und Heuristiken.

Josef Kallrath

10. Globale Optimierung in der Praxis

Zusammenfassung

Globale Optimierungstechniken werden überall dort eingesetzt, wo nicht-konvexe NLP-oder MINLP-Probleme auftreten. In der Mineralölindustrie wird versucht, Planungs- und Scheduling-Probleme mit Hilfe von Methoden der globalen Optimierung zu lösen. Das in diesem Kapitel dargestellte Verschnittproblem stammt aus Adjiman (1999, [9]). Weitere Anwendungsbeispiele finden sich in Floudas et al. (1999,[67]) und Floudas (2000,[66]). Besonders erwähnenswert ist auch, dass es mit den Methoden der globalen Optimierung wie in Maranas & Floudas (1994,[203]) möglich ist, sämtliche Nullstellen eines Systems nicht linearer Gleichungen zu bestimmen. Dies findet z.B. Anwendung in der Bestimmung aller stationären Zustände chemischer Reaktoren; Maranas & Floudas (1994, [203]) wenden es auf die Bestimmung möglicher Energieniveaus von Molekülen, Ratschek & Rokne (1993, [178]) auf Schaltkreis-Design-Probleme an. Anwendungen auf Parameterschätzung und Robotik finden wir in Jaulin et al. (2001, [114]).

Josef Kallrath

11. Schlussbetrachtungen und Ausblick

Zusammenfassung

In diesem Kapitel schließen wir mit einigen Schlussbetrachtungen zu dem in diesem Buch vorgestellten Material, einer Diskussion über die Möglichkeiten der parallelen Optimierung und einem Ausblick über die Zukunft der gemischt-ganzzahligen Optimierung.

Josef Kallrath

A. Mathematische Beschreibung der Optimierungsverfahren

Zusammenfassung

Der Anhang beschreibt — einige elementare Kenntnisse in der Analysis und der linearen Algebra voraussetzend — die verwendeten Optimierungsverfahren eingehender und soll tiefere Kenntnisse vermitteln, die in vielen Fällen bei der Modellierung sehr relevant sind.

Josef Kallrath

B. Glossar

Zusammenfassung

Die im Buch verwendeten technischen Begriffe aus dem Umfeld der mathematischen Optimierung sind hier der Übersichtlichkeit wegen noch einmal zusammengefasst; Verweise sind in Fettschrift hervorgehoben.

Josef Kallrath

Backmatter