Neueste Fortschritte in der gemischt-ganzzahligen linearen Programmierung (MILP)

Gemischt-ganzzahlige lineare Programmierung (MILP) ist dank der gesteigerten Effizienz moderner Solver zu einem Eckpfeiler der Operations Research geworden. Diese Solver können heute global optimale Lösungen in Sekunden finden für Probleme, die vor einem Jahrzehnt noch unlösbar waren. Diese Vielseitigkeit ermöglichte erfolgreiche Anwendungen in vielen Bereichen wie Transport, Logistik, Supply-Chain-Management, Revenue Management, Finanzen, Telekommunikation und Fertigung. Trotz dieses Erfolgs bleiben viele Herausforderungen bestehen, und MILP ist ein lebendiges Forschungsgebiet. Dieser Artikel gibt einen Überblick über die wichtigsten Fortschritte bei MILP-Lösungsmethoden, konzentriert sich auf rechnerische Aspekte und jüngste Verbesserungen der praktischen Leistung und betont Studien mit rechnerischen Experimenten. Die Übersicht gliedert sich in Branch-and-Cut-Methoden, Dantzig-Wolfe-Dekomposition und Benders-Dekomposition und schließt mit einer Diskussion über aktuelle Herausforderungen und zukünftige Entwicklungen.