Wenn das Optimierungsmodell nicht liefert
Ihr Optimierungsmodell rechnet stundenlang, oder die Pläne bleiben liegen. Wir bauen das Modell gezielt um, meist auf der Software, die Sie bereits haben.
- Kostenloses 30-Minuten-Gespräch
- Unverbindlich
- Der Code gehört Ihnen
Kurz erklärt: Ein Optimierer, der nicht liefert, rechnet stundenlang. Oder er gibt Pläne aus, die niemand nutzt. Meist liegt es an der Formulierung: daran, wie das Planungsproblem als Mathematik aufgeschrieben ist. Wir schreiben das Modell um, oft auf dem Solver, den Sie schon haben.
Wie sich das Problem zeigt.
Ihr Optimierungsmodell rechnet Stunden, wo Sie Minuten bräuchten. Oder es liefert Pläne, die Ihr Team nicht einsetzen kann. Die Schuld bekommt meist die Software. Die Ursache liegt fast immer in der Formulierung, also darin, wie das Modell geschrieben ist.
Ein Modell, um das Sie herumplanen
Auf Testdaten sah das Modell gut aus. Mit Ihren eigenen Daten ist es noch nicht fertig, wenn Sie den Plan brauchen. Also fangen Sie ohne das Modell an. An anderen Tagen wird es fertig, doch sein Plan ist schlechter als ein Plan, den Sie von Hand erstellen. Manchmal meldet es «unzulässig», also: Kein Plan kann alle Regeln einhalten, und niemand weiss warum. Am Ende kommt die Tabelle zurück, neben einer Software, die Sie weiter bezahlen.
Drei Arten, wie Optimierungsmodelle scheitern
Das Laufzeitproblem: Das Modell rechnet Stunden, wo der Betrieb Minuten braucht. Mehr Rechenleistung hilft selten. Meist lässt das Modell den Solver Optionen verfolgen, die nie die beste sein können. Oder der Solver prüft Pläne, die eigentlich gleich sind.
Das Qualitätsproblem: Das Modell liefert zulässige Pläne, also Pläne, die jede Regel einhalten. Trotzdem sind sie schlechter als Ihre eigenen. Der Grund ist die Zielfunktion. Das ist eine Bewertung, die mögliche Pläne nach Ihren Kriterien beurteilt. Vielleicht zählt sie Kilometer, aber keine Überstunden.
Die Meldung «unzulässig»: Mit Ihren eigenen Daten meldet das Modell «unzulässig», und niemand weiss warum. Manche Regeln im Modell sind strenger als die Regeln, nach denen Sie tatsächlich arbeiten. Andere sind falsch programmiert oder widersprechen sich. Bis Sie den Widerspruch finden, steht die Planung still.
Was jedes Problem Sie kostet
- Laufzeitproblem: Das Modell rechnet Stunden statt Minuten.
Der Plan kommt zu spät. Wenn er fertig ist, sind schon neue Aufträge dazugekommen, und er passt nicht mehr zum Tag.
- Qualitätsproblem: zulässige Pläne, die schlechter sind als Ihre von Hand erstellten Pläne.
Sie bezahlen für Optimierung und verdienen trotzdem weniger, als möglich wäre.
- Meldung «unzulässig»: Mit Ihren eigenen Daten findet das Modell keinen Plan, der alle Regeln einhält. Niemand weiss, welche Regeln sich widersprechen.
Die Planung steht still, und Ihr Team greift wieder zu Excel.
Nach einer sauberen Reparatur
Stand jetzt ist die Optimierung von letzter Nacht noch nicht abgeschlossen, wenn die Frühschicht beginnt. Also planen Sie wieder von Hand. Mit unseren Anpassungen wird das Modell in der Zeit fertig, die Sie für die Planung haben. Es läuft auf dem Solver, den Sie schon besitzen. Sie öffnen einen Plan, prüfen ihn und geben ihn frei.
Die Zielfunktion zählt jetzt, was Sie wirklich bezahlen, und die Pläne ergeben Sinn. Wie viel schneller es wird, hängt von Ihrem Modell ab. Unsere erste Prüfung, die Analyse, zeigt Ihnen, was realistisch ist.
Erst das Solver-Log lesen, dann etwas ändern
Die meisten dieser Modelle sind MIPs, nach dem englischen Mixed-Integer Programming. Ein MIP ist ein Modell, in dem manche Entscheidungen nur Ja oder Nein sein können. Während der Rechnung gibt ein MIP-Solver zwei Zahlen aus. Die eine ist der Wert des besten Plans, den der Solver bisher gefunden hat. Die andere ist der Best Bound, ein Wert, den kein Plan unterbieten kann. Der Support von Gurobi rät zum selben ersten Schritt wie wir: Finden Sie heraus, welche der beiden Zahlen sich nicht mehr bewegt.
Bewegt sich die Schranke eine Stunde lang kaum, ist die Formulierung schwach. Bessere Hardware ändert daran nichts. Bewegt sich der Best Bound gut, aber gute Pläne kommen spät, braucht die Suche Hilfe. Geben Sie dem Solver zum Beispiel den Plan von gestern als Startpunkt, einen Warm Start. Lassen Sie das Modell ausserdem mit mehreren Seeds rechnen. Ein Seed ist eine Startzahl, die den Suchweg des Solvers leicht verändert. Sonst gleiche Durchläufe dauern oft unterschiedlich lang. Gurobi rät, mehrere Durchläufe zu vergleichen, bevor Sie eine Anpassung beurteilen.
Wenn das Modell «unzulässig» meldet
Suchen Sie den Konflikt nicht, indem Sie eine Regel nach der anderen löschen. Gurobi kann ein IIS berechnen, kurz für Irreducible Inconsistent Subsystem. Das ist eine Gruppe von Regeln, die nicht alle gleichzeitig gelten können. Lassen Sie eine beliebige davon weg, können die übrigen gleichzeitig gelten. CPLEX nennt sein Werkzeug Conflict Refiner. Beide machen aus Tausenden Regeln eine Handvoll.
Die Dokumentation nennt zwei Einschränkungen. Ein Modell kann mehrere solche Konflikte enthalten, und der gemeldete ist nicht immer der kleinste. Also beheben Sie einen, rechnen neu und wiederholen das. Wir bauen diese Prüfung ins Modell ein. So sehen Sie in einfachen Worten, welche Regeln sich widersprechen.
Was wir an der Formulierung ändern
Ein Solver misst jede Option an einer Schätzung des besten Plans, der noch möglich ist. Diese Schätzung stammt aus einer vereinfachten Kopie Ihres Modells, die Bruchzahlen erlaubt, etwa einen halben Lastwagen. In der Optimierung nennt man sie LP-Relaxation, und LP steht für lineare Programmierung. Wir formulieren das Modell so um, dass die Schätzung genauer wird und der Solver schlechte Optionen früh verwirft.
Big-M-Terme schwächen diese Schätzung oft. Sie schalten eine Regel mit einer sehr grossen Zahl ein oder aus, dem «M». Wir ersetzen sie durch Indikatorbedingungen, die direkt sagen, wann eine Regel gilt. Symmetrie heisst: Viele Pläne sind eigentlich gleich, etwa wenn zwei baugleiche Lastwagen ihre Touren tauschen. Wir verhindern das mit Zusatzregeln wie «Lastwagen A wird vor Lastwagen B eingesetzt». Und die Zielfunktion schreiben wir so, dass sie die Kosten zählt, die Sie tatsächlich bezahlen.
So läuft ein Projekt ab.
Jede der drei Phasen endet mit etwas, das Sie prüfen können, bevor es weitergeht.
-
Verstehen
Wir beginnen bei Ihrem Betrieb. Was planen Sie, wo treten Probleme auf, und wie sähe eine bessere Planung aus? Dann sagen wir Ihnen offen und ehrlich, ob Optimierung helfen kann. Manchmal lautet die Antwort Nein.
- Eine schriftliche Einschätzung
- Ein klares Ja oder Nein
-
Modellieren
Wir schreiben Ihre Bedingungen, Ziele und Regeln in ein mathematisches Modell. Dies ist eine genaue Beschreibung, wie Ihr Betrieb funktioniert. Dann rechnen wir dieses Modell mit Ihren eigenen Daten. Sie sehen nebeneinander, was jeder Plan kostet und was er bringt. Dann wählen Sie den Plan, der zu Ihren Prioritäten passt.
- Ein dokumentiertes Modell
- Ergebnisse mit Ihren eigenen Daten
-
Umsetzen
Wir testen das Modell mit Ihren Daten und gehen die Ergebnisse mit Ihrem Team durch. Sobald Ihr Team dem Modell vertraut, binden wir es an Ihre Systeme an. Dann läuft es jeden Tag, ohne dass jemand manuell eingreifen muss.
- Quellcode und Dokumentation
- Schulung für Ihr Team
Übliche Fragen.
Etwas anderes? Fragen Sie uns direkt.
Schauen Sie im Log, welche Zahl sich nicht mehr bewegt. Der MIP-Gap ist der Abstand zwischen zwei Zahlen: dem besten Plan bisher, dem Incumbent, und dem Best Bound, einem Wert, den kein Plan unterbieten kann. Bewegt sich der Best Bound kaum, liegt es meist an der Formulierung. Die LP-Relaxation ist schwach, und der Solver kann schlechte Optionen nicht früh verwerfen. Bewegt sich der Best Bound, aber der Incumbent wird erst spät besser, braucht die Suche Hilfe. Geben Sie dem Solver zum Beispiel den Plan von gestern als Startpunkt. Das nennt man Warm Start. Der Support von Gurobi empfiehlt diese Unterscheidung, bevor Sie Parameter anfassen.
Lassen Sie den Solver einen Konflikt suchen. Gurobi berechnet ein IIS. Das ist eine Gruppe von Regeln, die nicht alle gleichzeitig gelten können. Entfernen Sie eine beliebige davon, können die übrigen gleichzeitig gelten. CPLEX bietet dafür den Conflict Refiner. Ein Modell kann mehrere Konflikte enthalten. Also beheben Sie einen, rechnen neu und wiederholen das. Prüfen Sie bei jeder Regel im Konflikt, ob Sie in Ihrem Betrieb tatsächlich so arbeiten.
Kleine Änderungen können den Solver auf einen anderen Suchweg schicken: andere Daten, eine andere Reihenfolge der Regeln oder ein anderer Seed. Ein Seed ist eine Startzahl für die Suche. In der Optimierung nennt man diese Schwankungen Performance Variability. Gurobi rät, mit mehreren Seeds zu rechnen, bevor Sie eine Änderung beurteilen. Schwanken die Laufzeiten stark, liegt es oft an der Formulierung. Dort würden wir ansetzen.
Manchmal, ein wenig. Der Support von Gurobi rät, mit den Standardeinstellungen zu beginnen. Parameter ändern Sie erst, wenn das Log einen Grund zeigt. Parameter ändern, wie der Solver sucht. Aus einer schwachen Formulierung machen sie keine starke. Unserer Ansicht nach bringt ein Nachmittag an der Formulierung meist mehr als eine Woche Feintuning.
Fast nie. Wenn ein Modell Stunden statt Minuten braucht, liegt es meist an der Formulierung. Meist liegt es an einem von drei Dingen. Das Modell schätzt den besten möglichen Plan zu ungenau, das nennt man eine schwache LP-Relaxation. Das Modell prüft viele Pläne, die eigentlich gleich sind, das nennt man Symmetrie. Oder es schaltet Regeln mit sehr grossen Zahlen ein und aus, den Big-M-Termen. Die Schuld bekommt trotzdem der Solver.
Wir beginnen mit einer Analyse: Wir prüfen die Regeln Ihres Modells und die LP-Relaxation. Wir suchen nach Symmetrien, also nach Plänen, die eigentlich gleich sind. Und wir suchen nach gültigen Ungleichungen. Das sind Zusatzregeln, mit denen der Solver genauer schätzt, wie gut der beste Plan sein kann. Sie schliessen keinen zulässigen Plan aus. Ausserdem klären wir, ob eine Benders-Zerlegung hilft: Sie teilt ein grosses Problem in eine Hauptentscheidung und kleinere Teilprobleme. Die meisten Modelle lassen sich gezielt retten, ein Neubau ist die Ausnahme.
Meistens nicht. Wir sind solver-unabhängig und bevorzugen keinen bestimmten Solver. Wir arbeiten mit Gurobi, CPLEX, HiGHS, OR-Tools oder CP-SAT (kurz für Constraint Programming mit Boolean Satisfiability). Wir wählen das Werkzeug, das zur Struktur Ihres Problems passt. Oft ist das der Solver, für den Sie schon bezahlen.
Ähnliche Seiten.
Begriffe auf dieser Seite
Jede Abkürzung in einfachen Worten erklärt, in unserem Beitrag «Metriken und Methoden».
- LPLineare Optimierung
- MILPGemischt-ganzzahlige lineare Optimierung
- LP-Relaxation
- Optimalitätslücke (MIP-Gap)
- CPConstraint-Programmierung
- CP-SATCP-SAT-Solver
- IISIrreduzibel widersprüchliches Teilsystem
- Gurobi
- CPLEXIBM CPLEX
- HiGHSHiGHS
- OR-ToolsGoogle OR-Tools
Erzählen Sie uns, was Sie planen.
In einem kostenlosen 30-Minuten-Gespräch mit einem Spezialisten finden Sie heraus, ob Optimierung Ihnen helfen kann.
- Kostenlos und unverbindlich
- Sie sprechen direkt mit einem Spezialisten
- Ein klares Ja oder Nein