Schnittebenenverfahren

Das Schnittebenenverfahren ist eine klassische Technik für ganzzahlige Programmierung (IP) und gemischt-ganzzahlige Programmierung (MIP), die die LP-Relaxation iterativ mit **gültigen Ungleichungen** verschärft, die das fraktionale LP-Optimum abschneiden, ohne irgendeinen ganzzahlig-zulässigen Punkt auszuschließen. Das Verfahren wurde von Gomory (1958) für ganzzahlige Programmierung (Gomory Fractional Cut) und Gomory (1960) für die gemischt-ganzzahlige Variante (Gomory Mixed-Integer Cut) eingeführt. Der Algorithmus läuft so ab: LP-Relaxation lösen; ist die Lösung ganzzahlig, ist das Optimum gefunden; andernfalls einen Schnitt erzeugen, der den fraktionalen Punkt ausschließt, alle ganzzahlig-zulässigen Punkte aber bewahrt, ihn dem Modell hinzufügen und das LP neu lösen; iterieren bis zur Ganzzahligkeit. Schnittfamilien sind problemspezifisch: Knapsack-Cover-Schnitte, Flow-Cover-Schnitte, Clique-Schnitte (Graphfärbung/IP), Mixed-Integer-Rounding (MIR), Chvátal-Gomory-Schnitte, Lift-and-Project-Schnitte (Balas, Ceria und Cornuéjols 1993), Subtour- und Comb-Ungleichungen für TSP (Padberg-Rinaldi 1991). Da reine Gomory-Schnitte in der Praxis langsam konvergieren, kombinieren moderne Implementierungen Schnitte mit Branch and Bound (Branch-and-Cut, Padberg und Rinaldi 1991) — die Grundarchitektur moderner MIP-Solver. Die Schnittgenerierung ist automatisch und für den Anwender weitgehend unsichtbar. Nemhauser und Wolsey (1988), Wolsey (1998) und Cornuéjols (2008) sind Referenzlektüren.