Number 42

Die Reise geht weiter…

Für jedes Optimierungsproblem gilt es, die beste Lösungsstrategie zu finden. Das ist nicht immer leicht, wie unsere Blogreihe „Custom Heuristic vs Standard-Solver“ zeigt. Unser OR-Expertenteam hat jedoch die hierfür nötige Erfahrung und beweist dies vor allem bei komplexen Problemen immer wieder aufs Neue.

Nachdem wir im ersten Teil unserer Blogreihe Lösungsverfahren mit dem Ansatz der Custom Heuristic näher beschrieben haben, betrachten wir in diesem Beitrag, wie Optimierungsprobleme mit Hilfe der Mathematik auf analytischem Weg unter Einsatz von Standard-Solvern gelöst werden können. Beide Lösungsstrategien haben ihre Vorteile und können bei komplexen Optimierungsproblemen auch hervorragend miteinander kombiniert werden. Eine kurze Übersicht hierzu gibt es demnächst im dritten Teil dieser Blogreihe mit dem Titel „Custom Heuristic vs Standard-Solver: Teil III – Best of Both Worlds“.

Wann kommen Standard-Solver zum Einsatz?

Solver sind Computerprogramme, die mathematische Probleme lösen können. Unterstützt werden hierbei vor allem lineare Programmierung (LP), quadratische Programmierung (QP) und die gemischt-ganzzahlige lineare Programmierung (MILP). Mathematisch exakte Verfahren sind besonders geeignet für die Lösung dieser Problemarten. Viele reale Problemstellungen können durch Unschärfe in der Modellierung angenähert werden. Das Ergebnis ist ein Modell, das zum Solver passt, und somit geeignet ist für eine schnelle Optimierung durch mathematisch exakte Verfahren.

Rechenzeit und Gap

Die Algorithmen von Standard-Solvern garantieren eine optimale Lösung, die zudem bewiesen ist, also das bewiesene Optimum. Die Rechenzeit hierfür ist aber leider nicht absehbar. An dieser Stelle kommt das Gap ins Spiel! Standard-Solver bieten nach kurzer Rechenzeit eine Lösung – und zusätzlich eine Beurteilung deren Qualität. In Form eines Gaps erfolgt eine Abschätzung wie gut das Optimum ist: Ein Gap von 5 % heißt, dass das globale Optimum 0 % bis 5 % besser ist als die aktuell bekannte Lösung. Wo in diesem Bereich sich die optimale Lösung befindet, ist jedoch nicht bekannt – nur die mathematisch bewiesene Obergrenze. Bei der Beurteilung des Gaps ist zudem folgendes zu berücksichtigen:

  • Die Bewertung ist abhängig von den eingesetzten Werten und somit eine Einzelfallbeurteilung.
  • Die Unschärfe der Daten ist zu berücksichtigen.
  • Ein großer Gap bietet wenig bis keinen Nutzen.
  • Ist die Kurve des Gaps auslaufend flach, kann dies als Kennzeichen für eine sehr gute Lösung gewertet werden, für die lediglich noch der Beweis gesucht wird.

Knapsack problem oder „Wie packe ich das Auto für meine Europareise?“

Übertragen wir nun die beschriebenen Fakten über Solver auf das Rucksackpackproblem bzw. auf die Frage „Wie bepacke ich mein Auto optimal für meine Reise durch Europa?“ aus unserem Blogpost Custom Heuristic. Folgendes Szenario wird vorstellbar: Die mathematisch exakte Methode mit dem Einsatz eines Standard-Solvers liefert mir evtl. schon nach 2 Minuten Rechenzeit eine Lösung mit einem garantieren Gap von 0,1%. Die Rechenzeit für eine bessere Lösung oder für den Beweis dieser Lösung als Optimum jedoch ist nicht bekannt. Möchte ich nun das Gap schließen und hierauf evtl. mehrere Jahre warten? Zudem ist, wie bereits erwähnt, die Unschärfe in den Daten nicht zu vernachlässigen, denn habe ich den Nutzen von Regenschirm, Sonnenhut und Daunenjacke überhaupt richtig geschätzt und die Größen genau gemessen? Oder komme ich letztendlich zu dem Ergebnis, dass ich mit einer Unschärfe von 0,1 % gut leben und meine Europareise wie geplant jetzt starten kann und nicht erst im Rentenalter?

Eine Reise in die Galaxis

Im nächsten Optimierungsproblem unternehmen wir eine noch abenteuerlichere Reise als unsere Autofahrt durch Europa: Im Roman bzw. Reiseführer „Per Anhalter durch die Galaxis“ bezeichnet der Supercomputer Deep Thought die Antwort 42 „mit absoluter Sicherheit als korrekt“. Diese Antwort ist also das bewiesene globale Optimum auf die Frage „nach dem Leben, dem Universum und dem ganzen Rest“. Wir können also davon ausgehen, dass Deep Thought einen Solver zur Berechnung eingesetzt hat, denn mit Heuristiken gilt ein Optimum niemals als bewiesen. Auch nach 7,5 Millionen Jahren nicht – der Rechenzeit, die Deep Thought für die Antwort 42 als bewiesenes Optimum benötigt.

Fun-Fact

Befolgt der interstellare Anhalter die Tipps des Reiseführers, muss er sich zumindest mit dem Rucksackproblem (beschrieben in Custom Heuristic vs Standard-Solver: Teil I – Custom Heuristic) nicht befassen: Ein Handtuch – so heißt es – ist so ungefähr das Nützlichste, was man besitzen kann. (Aus diesem Grund findet in Gedenken an den Autor Douglas Adams am 25. Mai alljährlich der Towel Day statt).

Normalerweise aber hätte die Antwort schon nach einer Rechenzeit von vielleicht 2 Stunden – statt nach 7,5 Millionen Jahren – lauten können: Die beste Lösung dato beträgt 42,2 mit einem garantieren Gap von 1%. Diese Antwort hätte gezeigt, dass das bewiesene Optimum (als Minimum) zwischen 41,778 und 42,2 liegt. Wo genau ist (noch) nicht bekannt und bewiesen. Aber jetzt noch 7,5 Millionen Jahre auf den Beweis warten? Auf jeden Fall wäre schon zu diesem frühen Zeitpunkt klar gewesen, dass 42 als Antwort sinnlos ist.

Fazit zum mathematisch exakten Verfahren mit Standard-Solver

Die mathematische Optimierung mit dem Einsatz von Standard-Solvern steht außer Frage bei geeigneten Modellen. Bei diesen sogenannten Performance Modellen ist die Optimierung sehr schnell und mit Sicherheit werden optimale oder nahezu optimale Ergebnisse geliefert und zusätzlich ein Gap ausgewiesen – basierend auf einer erprobten Technologie.

Diese erprobte Technologie hat zwar ihren Preis – in Form von Lizenzkosten. Jedoch stehen diesen Kosten ein überschaubarer Implementierungsaufwand, sowie ein geringes Projektrisiko (nach kurzem Proof of Concept) und eine kurze Projektlaufzeit, gegenüber.

Custom Heuristic vs Standard-Solver?

Custom Heuristic und Standard-Solver im Vergleich: Wenn Sie mehr über Custom Heuristiken und deren Einsatz erfahren möchten, lesen Sie unseren Beitrag Custom Heuristic vs Standard-Solver: Teil I – Custom Heuristic. Interessiert es Sie zudem, wie aus dem „verus“ ein „und“ wird? Zur Kombination beider Lösungsverfahren erfahren Sie mehr im Beitrag Custom Heuristic vs Standard-Solver: Teil III – Best of Both Worlds.

Profitieren Sie von der jahrelangen Erfahrung unserer OR-Experten:
Auch bei komplexen Optimierungsproblemen wählen sie die beste Lösungsstrategie.

Auch interessant…