cuttingplanemethoden

Cutting-Plane-Methoden sind Optimierungstechniken zur Lösung diskreter Probleme, insbesondere ganzzahliger Programme (MILP). Sie verfeinern schrittweise die zulässige Region durch lineare Schnitte. Aus der LP-Relaxation des Problems erhält man oft eine Lösung mit Bruchwerten. Dann wird eine lineare Ungleichung bestimmt, die für alle ganzzahligen Lösungen gilt, die aktuelle LP-Lösung jedoch verletzt. Durch das Hinzufügen solcher Schnitte wird der zulässige Bereich eingeengt, bis eine ganzzahlige Lösung gefunden wird oder die Infeasibilität nachgewiesen ist.

Beispiele für Schnitte sind Gomory-Schnitte, Gomory-Chvátal-Schnitte, Lift-and-Project-Schnitte, Balas-disjunktive Schnitte und MIR-Schnitte. Diese Schnitte nutzen verschiedene Eigenschaften des Problems, etwa Diskretisierung, Konvexität oder Disjunktionen, um gültige Ungleichungen abzuleiten, die die aktuelle fraktionale Lösung ausschließen, ohne zulässige ganzzahlige Lösungen zu eliminieren.

In der Praxis werden Cutting-Plane-Methoden häufig als Bestandteil von Branch-and-Cut-Verfahren eingesetzt. Moderne MILP-Solver kombinieren Schnitte mit Branch-and-Bound, nutzen Separation-Algorithmen, um neue Schnitte zu identifizieren, und berücksichtigen numerische Stabilität und Laufzeit. Ein vollständiges Cut-Set garantiert Konvergenz in theoretischen Modellen; in der Praxis wird es schrittweise erweitert.

Anwendungsbereiche umfassen Logistik, Produktionsplanung, Routing, Netz- und Ressourcenprobleme sowie Komplexitätsfragen der Kombinatorik. Cutting-Plane-Methoden sind ein zentrales Werkzeug der Optimierung, das sowohl in der Forschung als auch in der Praxis kontinuierlich weiterentwickelt wird.