MILP-Modellierung
Depots, Touren und Schichten sind Ja-oder-Nein-Entscheidungen, und eine Tabelle prüft eine nach der anderen. Ein gut gebautes MILP-Modell wägt alle zusammen ab.
- Kostenloses 30-Minuten-Gespräch
- Unverbindlich
- Der Code gehört Ihnen
Kurz erklärt: Die gemischt-ganzzahlige lineare Optimierung (MILP nach dem englischen Mixed-Integer Linear Programming) ist ein Verfahren für Planungsprobleme mit Ja-oder-Nein-Entscheidungen, etwa ob ein Depot öffnet. Ziel und Regeln sind linear: Alles wächst im gleichen Verhältnis, zwei Lkw kosten also doppelt so viel wie einer. Heraus kommt der beste Plan, der alle Regeln einhält.
Das Problem
Sie entscheiden, welche Depots öffnen, welche Touren fahren und wer welche Schicht übernimmt. Jede Wahl ist ein Ja oder ein Nein, und jede ändert, was die anderen kosten. Eine Tabelle prüft sie einzeln und sieht nie das Ganze. Vielleicht haben Sie schon ein Modell versucht, und es wurde nie rechtzeitig fertig.
Was sich ändert
Stand jetzt prüfen Sie Depots und Schichten einzeln und hoffen, dass die Kombination funktioniert. Unser Modell wägt alle Entscheidungen zusammen ab. Es liefert den günstigsten Plan, der alle Ihre Regeln einhält. Sie prüfen diesen Plan, statt ihn selbst zu erstellen.
So funktioniert es
Für solche Entscheidungen gibt es die gemischt-ganzzahlige lineare Optimierung (MILP). Das Modell hat ein Ziel, etwa die tiefsten Gesamtkosten. In der Optimierung nennt man es Zielfunktion. Dazu kommen Regeln, die man Bedingungen nennt. Beide sind linear: Alles wächst im gleichen Verhältnis, zwei Lkw kosten also doppelt so viel wie einer. Gemischt-ganzzahlig heisst: Manche Entscheidungen lassen sich nicht teilen. Ein Depot ist offen oder zu, nie halb offen.
Die Schwierigkeit liegt in der Formulierung, also darin, wie wir Ihr Problem in Mathematik fassen. Dort liegt bei den meisten gescheiterten Modellen der Fehler, lange bevor Sie eine Solver-Einstellung ändern. Oft sind zwei Pläne gleich, nur sind die Namen vertauscht, etwa Lkw 1 und Lkw 2. Wir ergänzen Regeln, damit die Suche solche Pläne nur einmal prüft. In der Optimierung nennt man das Symmetrien auflösen. Wächst eine Grösse nicht im gleichen Verhältnis, schreiben wir sie in eine lineare Form um. Und bei jeder Ein-aus-Regel sind wir pingelig.
Wie gross darf Big-M sein?
Big-M ist der klassische Weg, eine Regel ein- oder auszuschalten. Ein Beispiel: Ein Depot liefert nur, wenn es offen ist, also Liefermenge ≤ M × offen. M muss mindestens so gross sein wie die grösste mögliche Liefermenge dieses Depots. Ist M zu klein, schneiden Sie echte Pläne ab. Ist M zu gross, wird die Vorschau des Solvers unscharf, und die Suche zieht sich. Diese Vorschau erlaubt halb offene Depots.
Es gibt noch einen tückischeren Effekt. Der Numerik-Leitfaden von Gurobi nennt Big-M-Bedingungen eine regelmässige Quelle von Instabilität. Seine Standardtoleranz wertet einen Binärwert von 0,0000099999 als null. Bei M gleich einer Million liefert ein geschlossenes Depot dann fast zehn Einheiten gratis. Gurobi empfiehlt zudem, die Koeffizienten im Modell innerhalb von sechs Zehnerpotenzen zu halten.
Darum setzen wir M auf den kleinsten Wert, den Ihre Daten zulassen, Depot für Depot. Wo es keinen kleinen Wert gibt, nehmen wir Indikatorbedingungen. Sie geben die Ein-aus-Logik direkt an den Solver weiter. Sie sind numerisch sicherer, manchmal aber langsamer, deshalb vergleichen wir beide. Die Rechenzeit eines Solvers hängt auch vom Zufall ab. Darum rechnen wir jede Variante mehrmals, jedes Mal mit einem anderen zufälligen Startwert. Ein einzelner Lauf pro Variante beweist wenig.
Wir bauen und tunen diese Modelle für Gurobi, CPLEX, HiGHS oder SCIP, je nachdem, was zu Ihrem Problem passt. Die ehrliche Grenze: Nichtlineare Ziele, sehr grosse Probleme oder Echtzeitbedarf verlangen manchmal eine andere Technik. Dann sagen wir es Ihnen und setzen die richtige ein.
Wann diese Methode nicht passt
Die ehrliche Grenze: Nichtlineare Ziele, sehr grosse Probleme oder Echtzeitbedarf verlangen manchmal eine andere Technik. Dann sagen wir es Ihnen und setzen die richtige ein.
Häufige Fragen.
Etwas anderes? Fragen Sie uns direkt.
Schauen Sie auf zwei Zahlen. Erstens: Lassen Sie den Solver die Ja-oder-Nein-Entscheidungen mit Bruchzahlen beantworten, etwa mit einem halb offenen Depot. Diese vereinfachte Version heisst LP-Relaxation (LP steht für das englische Linear Programming). Wie nah liegt ihr Ergebnis am besten umsetzbaren Plan? Je näher, desto weniger Suche bleibt. Zweitens: die Laufzeiten in einem fairen Test. Wählen Sie die realistischen Fälle vorab und rechnen Sie alle auf derselben Maschine. Ein Modell, das nur bei einem Fall gewinnt, hat wenig bewiesen.
Manchmal, und das zeigt nur ein Test. Gültige Ungleichungen sind Zusatzregeln. Sie schliessen Lösungen mit Bruchzahlen aus, aber keinen umsetzbaren Plan. Praktiker auf Operations Research Stack Exchange berichten: Sie bringen am meisten, wenn die LP-Relaxation des Modells schwach ist. Das ist die vereinfachte Version des Modells, die Bruchzahlen erlaubt. Schwach heisst: Ihr Ergebnis liegt weit vom besten umsetzbaren Plan entfernt. Die Ergebnisse ändern sich auch mit jeder Solver-Version, darum testen wir nach Updates neu.
Probieren Sie beides, mit kurzen Zeitlimits. Symmetrie heisst: Viele Pläne unterscheiden sich nur in den Bezeichnungen. Ein Beispiel sind zwei gleiche Lkw, die ihre Touren tauschen. Moderne Solver erkennen einen Teil davon selbst und haben Einstellungen dafür, wie stark sie suchen. Selbst geschriebene Regeln gewinnen bei manchen Modellen trotzdem. Bei anderen stören sie.
Das entscheiden Ihre eigenen Daten. HiGHS löst lineare und gemischt-ganzzahlige Modelle und steht unter der MIT-Lizenz, Sie können es also kostenlos einsetzen. Wir rechnen Ihr Modell mit beiden Solvern und vergleichen die Zeiten anhand Ihrer eigenen Fälle. Wird HiGHS in Ihrem Planungsfenster fertig, bleibt das Lizenzgeld bei Ihnen.
Manchmal schon, und dann sagen wir es. Standardtools sind aber für ein durchschnittliches Problem gebaut. Bei MILP-Modellierung gehen wir von Ihrem Problem aus: von seiner Grösse, seinen Regeln und den Ausnahmen, die nirgends aufgeschrieben sind. Darum passt der Plan besser zu Ihrem Betrieb.
Für den Start brauchen Sie beides nicht. Wir bauen das Modell aus den Daten, die Sie haben, ob ordentlich oder nicht, und das Aufräumen gehört zur Arbeit. Sie erhalten ein dokumentiertes System, das Ihr Team pflegen kann. Wir schulen Ihr Team, bis es das System auch nach dem Projekt selbst betreut.
Am Anfang steht ein kostenloses 30-Minuten-Gespräch über Ihren Betrieb und das passende Modell. Dann bauen wir einen funktionierenden Prototyp und lassen ihn mit Ihren Zahlen rechnen. Sie sehen Ergebnisse, bevor Sie sich auf etwas Grösseres festlegen.
Ä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
- Gurobi
- CPLEXIBM CPLEX
- HiGHSHiGHS
- SCIPSCIP
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