Die letzten 50 Jahre der ganzzahligen linearen Programmierung: Jüngste praktische Fortschritte

 (inria.hal.science)
1 Punkte von GN⁺ 2025-06-16 | 1 Kommentare | Auf WhatsApp teilen
  • Ganzzahlige lineare Programmierung (MILP) hat sich in vielen Industriebereichen als zentrales Werkzeug etabliert
  • Dank der verbesserten Recheneffizienz moderner Solver lassen sich heute auch Probleme, die früher schwer lösbar waren, schnell optimal lösen
  • Dieser Artikel erläutert die jüngsten praktischen Fortschritte bei MILP-Lösungsverfahren mit Fokus auf Verbesserungen der Rechenleistung
  • Als zentrale Methoden werden Branch-and-Cut, Dantzig-Wolfe-Zerlegung und Benders-Zerlegung vorgestellt
  • Anhaltende Herausforderungen im MILP-Bereich und Chancen für künftige Forschung werden zusammengefasst

Einleitung

  • Mixed-Integer Linear Programming (MILP) ist ein unverzichtbares Werkzeug im Operations Research und wird in zahlreichen Industriebereichen erfolgreich eingesetzt
  • Moderne MILP-Solver können heute selbst große Probleme, die früher als unlösbar galten, innerhalb von Sekunden optimal lösen
  • Dadurch hat sich der Einsatz von MILP in Bereichen wie Transport, Supply Chain, Revenue Management, Finanzwesen, Telekommunikation und Fertigung ausgeweitet
  • Dennoch bleiben ungelöste Probleme und neue Herausforderungen bestehen, weshalb die MILP-Forschung weiterhin sehr aktiv ist

Überblick über die Hauptinhalte

  • Die Arbeit konzentriert sich auf jüngste Entwicklungen bei MILP-Lösungsverfahren und praktische Leistungsverbesserungen und analysiert, welchen Beitrag die einzelnen Techniken konkret zur Verbesserung der Rechenleistung geleistet haben
  • Aus der umfangreichen Literatur werden insbesondere Arbeiten behandelt, die auf tatsächlichen Computing-Experimenten beruhen
  • Die Diskussion ist in drei Kernbereiche von MILP-Lösungsverfahren gegliedert
    • Branch-and-Cut-Methode: Ein typischer MILP-Lösungsansatz, der Knotenverzweigung mit Cutting-Plane-Techniken kombiniert
    • Dantzig-Wolfe-Zerlegung: Ein Dekompositionsansatz, der große Probleme in kleinere Teilprobleme zerlegt und so effizient bearbeitet
    • Benders-Zerlegung: Eine Methode, die Variablen und Nebenbedingungen trennt und das Problem iterativ löst, um die Rechenlast bei komplexen Strukturen zu verringern

Abschluss: Herausforderungen und Ausblick

  • Im letzten Teil der Arbeit werden die weiterhin bestehenden Herausforderungen von MILP und künftige Forschungsgelegenheiten beleuchtet
  • Immer komplexere reale Industrieprobleme, wachsende Datenmengen und Grenzen der Solver-Leistung gehören zu den wichtigsten künftigen Forschungsthemen
  • Es ist zu erwarten, dass der MILP-Bereich mit Fortschritten bei Algorithmen, Weiterentwicklungen der Hardware und der Ausweitung auf neue Anwendungsdomänen weiter wachsen wird

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-06-16
Hacker-News-Kommentare

  • Jemand äußert die Frage, ob erklären könne, warum kommerzielle ILP-Solver wie Gurobi so viel besser sind als kostenlose/Open-Source-Solver: Liegt es an der inhärenten Schwierigkeit von ILP, oder daran, dass ein Top-Solver im Grunde eine riesige Sammlung von Heuristiken für bestimmte Teilprobleme ist und allgemein „gute“ Strategien einfach noch nicht in der Public Domain angekommen sind?

    • Kommerzielle Solver arbeiten meist eng mit Kunden zusammen, um problem­spezifische Beschleunigungstechniken zu implementieren, und verfügen über 10 bis 20 Jahre angesammeltes Know-how. Im MILP-Bereich werden gute Heuristiken hervorgehoben, etwa für die Wahl von Startpunkten im Branch-and-Bound oder für effektives Beschneiden des Suchbaums, ebenso wie Custom Cuts, die Teillösungen effizient ausschließen. Forschende im OR-Bereich können oft sogar bessere Ergebnisse als kommerzielle Solver erzielen, wenn sie Probleme selbst auswählen und eigene Cuts und Heuristiken schreiben. Solver-Firmen stellen jedoch Teams mit promovierten Forschenden ein, um so etwas konsistent umzusetzen, und verfolgen Verbesserungen anhand großer Mengen realer Kundendaten.

    • Kommerzielle Solver können enorme Zeit und Ressourcen in die Feinabstimmung der Problemlösungsleistung investieren, weil echte Kunden daran interessiert sind und mithelfen. Das umfasst nicht nur Heuristiken, sondern auch das Erkennen einfacher Teilprobleme oder Approximationsprobleme und das Zurückspeisen dieser Ergebnisse in das Gesamtproblem. Open-Source-Solver stoßen an Grenzen, weil (1) die Einstiegshürde für die Entwicklung moderner Optimizer extrem hoch ist und nur wenige sowohl in Mathematik als auch im Coding sehr stark sind, (2) Menschen mit diesem Fähigkeitsprofil meist in deutlich lukrativere Karrieren wechseln und (3) im Open-Source-Modell Kunden kaum Fälle, Performancedaten oder Profiling zur Verbesserung bereitstellen. Ausnahmen sind etwa SNOPT, das zwar kommerziell ist, aber unkonventionell entwickelt wurde, und akademische Solver, die oft auf bestimmte Anwendungsfelder fokussiert und daher wenig universell sind. In anderen Feldern werden Ökosysteme teils durch Übernahmen oder Förderung großer Unternehmen wie Google aufgebaut, aber im Solver-Bereich ist die Investition zu hoch, um den kompletten Stack von Grund auf zu errichten.

    • Kommerzielle Solver verfügen über eine wirklich große Zahl an Tricks und Mechanismen zur Mustererkennung, um je nach Problem herauszufinden, welche Tricks wirksam sind. Wenn man die Problemstruktur gut kennt, kann man etwas bauen, das sogar schneller ist als ein kommerzieller Solver, aber bei zufälligen Problemen hat man kaum eine Chance.

    • Es gibt die Aussage, ein „Solver = eine Sammlung verschiedenster Heuristiken für spezialisierte Teilprobleme“. Dazu der Hinweis, dass bei NP-harten Problemen fast alles so strukturiert ist. ILP ist äquivalent zu SAT, daher gilt das dort genauso.

    • Außerdem spielen kommerzieller Maßstab und Geschwindigkeit eine Rolle. Die meisten Quant-Trading-Firmen lassen sehr große Optimierungsprobleme so häufig wie möglich laufen; Open-Source-Solver können solche Probleme oft gar nicht lösen oder laufen in Speicherprobleme. So groß ist die Lücke.

  • Jemand erinnert sich an seine Erfahrung beim Bau eines Ressourcenallokations-Tools mit der IBM-ILOG-MILP-Bibliothek: Hätte man ein ähnliches Problem vor 20 Jahren lösen wollen, würde es damals jetzt noch laufen, während es heute in 5 Minuten gelöst ist. Die Computer sind tausendmal schneller geworden und die Algorithmen ebenfalls tausendmal besser, insgesamt also eine millionenfache Verbesserung. Ein guter Gedanke, wenn man über die Zukunft nachdenkt. Die „Ressourcen“ waren in diesem Fall übrigens Diamanten.

  • Frage, wie das in der Praxis tatsächlich genutzt wird: Fällt numerische Optimierung wegen der üblichen datengetriebenen Grenzen wie Vertrauen oder Datenproblemen am Ende nicht oft doch auf wichtige Menschen zurück, die nach „Bauchgefühl“ entscheiden?

    • Im Unternehmen werden Solver über den gesamten Stack hinweg eingesetzt: zur Optimierung des Schedulings von Heimbatterien und EVs, zur optimalen Fahrplanerstellung für Portfolios aus Hunderttausenden Haushalten und sogar für den Handel dieses Portfolios. Auch die europäischen Strom-Spotpreise werden durch einen einzigen gigantischen Lauf des Solvers Euphemia bestimmt. Überall dort, wo es ein klares Optimierungsziel mit direktem Geldbezug gibt, werden Solver breit eingesetzt.

    • Ein praktisches Beispiel aus einem FMCG-Unternehmen: (1) Planung von Vertriebsmitarbeitenden und Lieferwegen, (2) Scheduling von Maschinen, Personal und Material für die Produktion, (3) Bestimmung angemessener Lagerbestände in Distributionszentren. Wegen der Schwierigkeit der Nachfrageprognose ist das nicht vollständig automatisiert.

    • Es werden hilfreiche Case-Study-Links geteilt: Gurobi-Fallstudien, CPLEX-Fallstudien, Hexaly-Fallstudien (früher LocalSolver)

  • Frage, ob jemand echte Preisinformationen teilen kann, da Gurobi ziemlich teuer sein soll.

    • Konkrete Preise sind nicht öffentlich, aber für MIP-Lernzwecke wird empfohlen, keine kommerziellen Solver wie XPRESS/Gurobi/CPLEX zu kaufen, sondern kostenlose Studentenlizenzen oder kostenlose nichtkommerzielle Open-Source-MIP-Solver zu nutzen, etwa HiGHS oder SCIP.

    • Soweit gehört, funktioniert die Preisgestaltung ungefähr nach dem Motto „anrufen und verhandeln“, wobei offenbar berücksichtigt wird, wie viel Geld der Kunde damit verdient, und der Preis entsprechend angesetzt wird.

    • Es wird betont, dass es viel billiger ist als langsame suboptimale Entscheidungen. Für kleine Probleme reichen kostenlose Solver wie GLPK, aber große Probleme im Geschäftsalltag sind damit oft praktisch nicht rechtzeitig lösbar. Daher lohnen sich Premium-Solver durchaus.

    • Vor etwa 10 Jahren lag der Preis nach Erinnerung bei rund 100.000 US-Dollar für eine Lizenz über mehrere Server; an die genaue Zahl der Nutzer oder Serverbeschränkungen erinnert man sich nicht mehr. In der Branche gilt das aber als den Wert wert.

    • Gurobi bietet auch einen Cloud-Service mit stundenbasierter Abrechnung an, und nichtakademische Lizenzen sind sehr teuer.

  • Jemand hat in den 1990er-Jahren selbst Gomory-Cutting-Hyperplanes implementiert und ist erstaunt, wie weit sich das Feld entwickelt hat. Früher dauerte es zwei Monate, ein LP-Problem zu lösen, heute reicht dafür eine Sekunde. Laut einer Arbeit von Bixby wurden CPLEX und Gurobi zwischen 1990 und 2020 unabhängig von der Maschinenleistung fast um den Faktor 4 Millionen schneller.

  • Zwischen 1988 und 2004 wurde Hardware 1600-mal schneller und LP-Solver 3300-mal schneller; schon damals ergab das insgesamt mehr als den Faktor 5 Millionen. Von 2001 bis 2020 wurden kommerzielle MILP-Solver ebenfalls mehr als 1000-mal schneller (50 durch Algorithmen, 20 durch Computer). Es wäre interessant, solche Geschwindigkeitsverbesserungen nach Fachgebieten gesammelt nach Beiträgen von Algorithmen und Rechnerleistung aufzuschlüsseln. Im Compiler-Bereich gibt es mit „Proebstings Gesetz“ ein ähnliches Ergebnis: Compilerfortschritt bringt über 18 Jahre hinweg etwa den Effekt einer Verdopplung der Rechenleistung.

  • Es wirkt so, als würden ML/AI-basierte Ansätze für solche Probleme überraschend wenig eingesetzt. Es gibt zwar Papers, die RL/GNN auf kleinen Problemen ausprobieren, aber am Ende scheint der Kauf einer Gurobi-Lizenz oft die beste Lösung zu sein. Beim Scheduling wurden auch RL-Beispiele gesehen, die tatsächliche Leistung war aber schwach. Für große Probleme scheinen evolutionäre Algorithmen optimal zu sein; insgesamt wirkt ein OR-basierter Ansatz am effizientesten, wenn man das Problem gut formulieren kann.

    • Das hängt von der Problemart ab. Die Entscheidung, welche Kraftwerke an- oder abgeschaltet werden, also Unit Commitment, ist zum Beispiel extrem komplex, aber mit einem MILP-Solver lässt sich eine global optimale Lösung schnell finden. Genetische Algorithmen garantieren nicht einmal, lokalen Minima zu entkommen, und können langsam sein. Neuronale Netze liefern ebenfalls immer nur suboptimale Lösungen.

    • SAT ist ein klassisches GOFAI-Problem, und man kann in jeder Sprache der ML-Familie auch einen SAT-Solver schreiben. Insofern lassen sich „ML/AI“-Ansätze sehr wohl anwenden.

  • Ein Kommentar schlägt vor, im Titel eine PDF-Kennzeichnung zu ergänzen.

  • Jemand meint, Integer Linear Programming sehe nicht so komplex aus.

    • Graph Vertex 3-Coloring (G3C) ist NP und NP-hard und damit NPC. Es gibt ein Resultat, dass man mit allgemeinem ILP auch G3C lösen kann. SAT ist ebenfalls NP-vollständig; wenn man SAT lösen kann, kann man auch G3C lösen, und wenn man G3C lösen kann, dann auch Integer Factorization (FAC). FAC ist zwar nicht NPC, aber in der heutigen Computerwelt enorm wichtig. Daraus folgt: Wer beliebiges ILP lösen kann, könnte zentrale Kryptoverfahren brechen. Das zeigt, wie schwierig ILP ist. Viele verwechseln dabei, dass zufällige Instanzen von NPC-Problemen meist recht leicht lösbar sind; der Anteil wirklich harter Instanzen wird mit wachsender Problemgröße oft sogar kleiner.

    • Auch das Travelling Salesperson Problem (TSP) lässt sich als ILP kodieren, was die Schwierigkeit ebenfalls andeutet.

    • Man muss die ganzen Zahlen finden, die die Bedingungen am besten erfüllen. Das klingt nach reellen Zahlen, ist aber im Kern etwas völlig anderes. Es gibt keine allgemeine Lösungsmethode, sondern nur sehr gute Heuristiken für Spezialfälle.

    • Es ist schwieriger als lineare Programmierung.

    • Oder man kann es als sehr reales Problem betrachten.