Schnittebenenverfahren von Gomory / Gomory Cut

Das Schnittebenenverfahren von Gomory (Gomory Cut) ist eine Alternative zu den Branch und Bound Verfahren, liefert also ebenfalls eine Lösung zu ganzzahligen Problemen. Während bei Branch&Bound die Lösungsmenge zerstückelt wird (sodass man mehrere Mengen betrachten muss), wird sie beim Schnittebenenverfahren von Gomory lediglich verkleinert. Dazu löst man erst einmal das relaxierte Problem (in den meisten Fällen erhält man keine ganzzahlige Lösung). Anschließend schränkt man nun die erhaltene Menge der Relaxierung durch Hinzunahme von weiteren Nebenbedingungen (Schnittebenen) schrittweise nach und nach ein. Dies geschieht so lange, bis eine ganzzahlige Lösung gefunden wurde. Die neuen Nebenbedingungen müssen dabei zwei Bedingungen erfüllen:

  1. Durch sie muss die gefundene (nicht ganzzahlige) optimale Lösung von der zulässigen Menge „abgeschnitten“ werden, sodass diese bei der nächsten Iteration nicht mehr beachtet wird
  2. Kein ganzzahliger zulässiger Punkt darf durch die neue Nebenbedingung unzulässig gemacht werden
Sofern vorhanden, kann mit dem Schnittebenenverfahren von Gomory mit einer endlichen Anzahl an Durchgängen die Lösung bestimmt werden. Allerdings kann eine sehr große Anzahl an Durchgängen nötig sein.

Quelle:
  • Nickel, Stein, Waldmann: Operations Research, 2011
  • http://num.math.uni-bayreuth.de/de/teaching/archive/ss_2005/01061/s_allescher.pdf
  • https://de.wikipedia.org/wiki/Schnittebenenverfahren