Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis

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.

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 einfließen. Im Umfeld der Ergebnisdiskussion werden einige Begriffe wie z. B. Schattenpreise und reduzierte Kosten konzeptionell und ohne mathematischen Formalismus eingeführt.

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 nichtlineares 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. Schließlich werden Ziel-Programmierung [engl.: Goal Programming], eine spezielle Technik zur Lösung multikriterieller Optimierungsprobleme, behandelt und einige Grenzen der linearen Programmierung diskutiert.

Dieses Kapitel enthält Fallstudien zunehmender Komplexität zur gemischt-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.

Dieses Kapitel handelt von polylithischen Modellierungs- und Lösungsansätzen. Solche Ansätze erlauben es, die Menge der lösbaren Praxisprobleme sowohl in ihrer Qualität (Struktur) und Größe (Anzahl der Variablen und Constraints) erheblich zu erweitern. Anhand von Problemen aus der Papierindustrie, die mit Hilfe polylithischer Modellierungsund Lösungsansätze gelöst wurden, werden diese Ansätze illustriert. Im Einzelnen werden die Rollenminimierung mit Hilfe eines Spaltenerzeugungsverfahrens, gleichzeitige Minimierung von Verschnitt und Anzahl verwendeter Muster, sowie die Formatproduktion behandelt.

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) formulieren eine Fragestellung aus dem Verkehrswesen, ein Strassenbahnabfertigungsund Rangierproblem, als quadratisches Zuordnungsproblem und lösen dieses mit Hilfe exakter Methoden (dynamische Optimierung) und Heuristiken. In diesem Kapitel werden zwei umfangreiche Probleme behandelt, die sich mit Hilfe gemischt-ganzzahliger nichtlinearer Modelle beschreiben lassen. Bei dem ersteren handelt es sich um ein Netzwerkdesignproblem, beim zweiten um die Auslegung eines Prozesses. Beide Probleme und ihre Modellierung erschienen in einer vorläufigen Form bereits in Kallrath (1999); daher werden hier einige Aspekte verkürzt dargestellt bzw. andere Punkte ergänzt. In diesem Kapitel werden Beispiele für gemischt-ganzzahlige nichtlineare Optimierung vorgestellt, bei denen gute zulässige Lösungen gewonnen wurden, von denen aber letztlich der Nachweis der globalen Optimalität noch aussteht. Dabei lässt sich feststellen, dass diese Probleme recht aufwendig in der Modellierung sein können, spezielle Heuristiken zur Gewinnung guter Startwerte – Homotopie-Verfahren, auf Modellsequenzen angewendet, können ein nützliches Mittel sein – und einen sorgfältigen Umgang mit den vorhandenen Lösungsalgorithmen erfordern und jedes MINLP-Problem seinen speziellen Lösungszugang benötigt.

Globale Optimierungstechniken, siehe beispielsweise Horst & Pardalos (1995), Floudas (2000), Floudas & Gounaris (2009) oder Misener & Floudas (2012), eignen sich zur Lösung nichtkonvexer NLP- oder MINLP-Probleme; wir meinen hierbei deterministische globale Optimierung, bei der ein global-optimaler Zielfunktionswert bis auf ein vorgegebenes ε > 0 berechnet werden kann. Nähert sich ε der Maschinengenauigkeit, so stellen sich grundsätzliche Fragen, die in der Disziplin Reliable Computing besser aufgehoben sind; wir beschränken uns daher hier auf ε > 10⁻⁶, was für die meisten praktischen Probleme auch völlig hinreichend ist. Limitierend wirkt in der Praxis der in der Anzahl der nichtlinear auftretenden Variablen expontiell anwachsende Rechenaufwand. Seit 2002 wurde eine Reihe von kommerziell verfügbaren Solvern, darunter Baron, Lindoglobal und Glomiqo, entwickelt, die systematisch in der Literaturübersicht des Artikels von Misener & Floudas (2012) beschrieben werden.

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.

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.