Scenic view of mountains in Appenzell, Swiss Alps

Und weiter geht die Reise – mit dem Besten zweier Welten als Ziel

Die verschiedenen Strategien zur Lösung eines Optimierungsproblems haben wir im Rahmen unserer Blogreihe „Custom Heuristic vs Standard-Solver“ vorgestellt. Da sind Custom Heuristiken einerseits und mathematisch exakte Verfahren mit dem Einsatz von Standard-Solvern andererseits. Zu entscheiden, inwieweit eine bestimmte Strategie geeignet ist, ein vorgegebenes Optimierungsproblem zu lösen, erfordert sehr viel erfahrungsbasiertes Geschick. Unser OR-Team beweist vor allem bei komplexen Problemen immer wieder aufs Neue seine Expertise. Und manchmal ist das Ergebnis auch eine Kombination beider Lösungsverfahren, wie wir in diesem dritten Teil „Best of Both Worlds“ zeigen.

Eine Wanderung durch Berg und Tal

Doch fassen wir zunächst noch einmal kurz die Fakten beider Lösungsstrategien zusammen. Ein Optimierungsproblem wird gelöst, indem seine Zielfunktion optimiert wird. In der Anschauung stellt die Zielfunktion – unter Berücksichtigung von Parametern – ein Gebirge mit Bergen und Tälern dar. Die Optimierung ist die Suche nach dem höchsten Gipfel (Maximum) bzw. nach dem tiefsten Tal (Minimum). Der Lösungsaufwand ist somit abhängig von der Topografie des Gebirges. Und davon, ob ein lokales Optimum als ausreichend gute Lösung erachtet wird oder ob das globale Optimum gesucht wird. Soll, von einem gegebenen Punkt aus, das nächste lokale Maximum (Gipfel) bzw. Minimum (Tal) in der Nachbarschaft gefunden werden, liefern Custom Heuristiken eine ausreichend gute Lösung. Soll jedoch das absolute Maximum (höchster Gipfel) bzw. das absolute Minimum (tiefstes Tal) bestimmt werden, sprechen wir von einer globalen Optimierung. Die Suche nach dem globalen und zudem bewiesenen Optimum erfolgt durch mathematisch exakte Verfahren und dem Einsatz von Standard-Solvern. Jedoch ist die Rechenzeit für das garantierte globale Optimum nicht absehbar. Wann welcher Lösungsweg der bessere ist, hängt somit zunächst einmal stark von der Topologie der Zielfunktion ab, aber genauso von der erzielbaren Lösungsqualität und dem resultierendem Rechenaufwand.

Best of Both Words – die Kombination führt zum Ergebnis

Eine Vielzahl realer Optimierungsprobleme kann nicht einfach mit einer der beiden genannten Strategien – Custom Heuristiken oder mathematisch exaktes Verfahren mit Solver – gelöst werden. Komplexe Planungsprobleme erfordern mit Hinblick auf die erzielbare Lösungsqualität und den resultierendem Rechenaufwand oftmals eine problemspezifische Verfahrensgestaltung. Wie also ist eine herausfordernde Problemstellung zu lösen? Eine Kombination beider Lösungsverfahren kann zum gewünschten Ergebnis führen.

Kombination 1 – Konstruktionsheuristik und Standard-Solver

„Verwandle große Schwierigkeiten in kleine und kleine in gar keine.“ Diese Weisheit aus China ist Grundlage eines ersten Ansatzes zur Lösung  komplexer Optimierungsprobleme: Das Problem wird im ersten Schritt in Teilprobleme zerlegt. Hierbei kommen zunächst Konstruktionsheuristiken zum Einsatz, wie z. B. das Zufalls- oder das Greedy-Verfahren (siehe Custom Heuristic vs Standard-Solver: Teil I – Custom Heuristic). Folgende Faktoren finden – oftmals als Domänenwissen – bei der Zerlegung eines Problems Berücksichtigung:

  • Zeit (rollierende  oder hierarchische Planung; Grob- und Feinplanung)
  • Geographie (Länder oder Regionen)
  • Sortiments- oder Produktionsstruktur (Produkte oder Produktgruppen)
  • Netzwerk hinsichtlich Montagestufen und Wertschöpfung (Vormontage bis zur Endmontage)

Bei der Zerlegung der Problemstellung werden einzelne Faktoren nicht immer unabhängig voneinander betrachtet. So wird beispielsweise die zeitliche Planung kombiniert mit geographischen Aspekten. Hierbei erfolgt dann zunächst die Grobplanung mit Konstruktinsheuristiken nach Gebieten (Ländern). Im Anschluss erfolgt die Feinplanung. Hierbei kann das reale Problem durch Unschärfe in der Modellierung angenähert werden. Das Ergebnis ist ein Modell, das zu einem Standard-Solver passt. Infolgedessen ist eine schnelle Optimierung des Teilproblems möglich durch mathematisch exakte Verfahren (siehe Custom Heuristic vs Standard-Solver: Teil II Mathematische Optimierungsverfahren mit Standard-Solver). Die resultierenden Ergebnisse sind bestenfalls optimal oder nahezu optimal und somit weitestgehend verlässlich einschätzbar.

Die Zerlegung der Alpen

Auch unsere Bergtour könnten wir nach diesem Prinzip zerlegen und so die Suche nach dem höchsten Gipfel unter Berücksichtigung geographischer Aspekte strukturieren. Planten wir unsere Bergtour durch die Alpen, müssten wir 8 Länder bei der Zerlegung berücksichtigen. Für jedes Land könnte dann die Suche nach dem höchsten Gipfel als Feinplanung mit dem Einsatz von Standard-Solvern erfolgen. Jedoch seit der Vermessung der Alpen im 19. Jahrhundert ist klar: Der Mont Blanc ist mit 4.810 Metern der höchste Gipfel der Alpen – sozusagen das bewiesene globale Optimum. In diesem Fall führte jedoch nicht die Mathematik zum Ergebnis, sondern die kartographische Vermessung.

Kombination 2 – Verbesserungsheuristik und Standard-Solver

Weitaus seltener ist die Kombination von Verbesserungsheuristiken und mathematisch exakten Verfahren, so dass das exakte Verfahren intern zur Bewertung der Lösung herangezogen wird. Ein Beispiel hierzu ist der Einsatz Genetischer Algorithmen (GAs) als Heuristiken zusammen mit Standard-Solvern, um herausfordernde Optimierungsprobleme, wie beispielsweise die Frage „Welcher Standort soll eröffnet werden?“ in der Netzwerkplanung, zu lösen.

Diese Art der Problemstellung enthält gleich zwei Entscheidungsgrundlagen: Sowohl die Frage nach dem Standort, als auch die Frage nach den Produktionsmengen der jeweiligen Standorte, die zur Bewertung der Standort-Auswahl und ihren Auswirkungen (z.B. der Gesamtkosten der Produktion und Logistik) herangezogen wird.
Genetische Algorithmen sind mit dieser komplexen Fragestellung überfordert. Die Einteilung des Problems in Primär- und Subproblem kann dies auflösen: Eine für dieses Primärproblem gut modellierbare Fragestellung ist beispielsweise „Welche betrachteten Standorte erfüllen die formulierten Anforderungen (Entscheidungskritierien) am besten?“. Das Primärproblem entscheidet, welche von den Standorten geöffnet werden sollen und kann z. B. mit Hilfe eines GAs gelöst werden.

Für die Bewertung der Fitness eines Individuums (synonym eine Lösung des Primärproblems) wird ein exaktes mathematisches Verfahren herangezogen. Dieses muss nun nicht mehr die Standortentscheidung berücksichtigen, da diese bereits vom GA entschieden wurde. Der Solver löst das Subproblem unter Berücksichtigung von Kostenbewertungen und bietet damit eine Antwort auf die Frage „Welche Auswirkungen auf die Produktions- und Logistikkosten hat die Standortentscheidung?“. Die Heuristik des Primärproblems wertet die Lösungen des Subproblems aus und wählt zum Ende die beste Lösung.

Diagram Best of Both Worlds

Abbildung – Best of Both Worlds

Somit kann gesagt werden, dass komplexe Planungsprobleme zwischen Custom Heuristic und Solver aufgeteilt werden können: Jeder macht das, was er am besten kann – Best of Both Worlds.

Custom Heuristic und Standard-Solver

In diesem Blogpost haben wir aufgezeigt, dass aus dem „versus“ auch ein „und“ werden kann zur Erzielung bester Lösungsergebnisse. Unsere Blogreihe mit dem Titel „Custom Heuristic vs Standard-Solver“ beleuchtet beide Lösungsstrategien genauer. Lesen Sie – auch als Grundlage zu diesem Blogpost – nochmals nach:
Custom Heuristic vs Standard-Solver: Teil I – Custom Heuristic
Custom Heuristic vs Standard-Solver: Teil II Mathematische Optimierungsverfahren mit Standard-Solver

Unsere OR-Experten können auf Grund ihrer jahrelangen Erfahrung beurteilen, welche Lösungsstrategie auch bei komplexen Optimierungsproblemen die passende ist.
Und wann aus dem „versus“ ein „und“ werden sollte.

Auch interessant…