Schnittebenenverfahren

Ein Schnittebenenverfahren (engl. cutting plane algorithm) ist in der angewandten Mathematik ein Algorithmus zur Lösung ganzzahliger linearer Optimierungsprobleme. Die Grundidee besteht darin, statt eines ganzzahligen linearen Programms seine LP-Relaxation (also ohne Ganzzahligkeitsbedingungen) zu betrachten und diese durch Hinzufügung weiterer Ungleichungen schrittweise zu verschärfen, bis (im Idealfall) eine ganzzahlige Lösung gefunden wird.

Das in den 1950er Jahren u. a. von Delbert Ray Fulkerson, George Dantzig und später von Egon Balas und Ralph Gomory entwickelte Verfahren ist mit seinen Weiterentwicklungen heute eine der Standardmethoden in der ganzzahligen Optimierung und weiterhin Gegenstand aktueller Forschung. Als alleiniges Lösungsverfahren ist es meist nicht ausreichend, liefert aber gute duale Schranken für die zu lösenden Optimierungsprobleme. Daher wird es oft mit Branch-and-Bound zum sogenannten Branch-and-Cut-Verfahren kombiniert.