Cuts helfen beim Finden einer Lösung eines ILP. Sie sind zusätzliche lineare Nebenbedingungen (Ungleichungen), die
- Keine ganzzahlige Lösung ausschließen und
- Den Simplex-Algorithmus so zu verengen, dass die LP-Relaxion näher an den ganzzahligen Lösungen anliegt
Beispiel
In rot: Die Cut-Beschränkungen, die das Ergebnis des Simplex-Algorithmus auf den grün markierten Punkt zu lenken
Rounding Cuts
Nebenbedingungen der Form
können bei Ganzzahligkeit durch die stärkere Bedingung
ersetzt werden.
GGT Cuts
Nebenbedingungen können durch den größten gemeinsamen Teiler (GGT) der Koeffizienten geteilt werden. Beispiel:
Da