Podręcznik

Metoda płaszczyzn odcinających jest często stosowana razem z metodą podziału i oszacowań tworząc jeden z najsilniejszych algorytmów optymalizacji liniowej dyskretnej. Taka kombinacja nazywana jest metodą podziału i odcięć (Branch & Cut) i ma następujący schemat:

1. Inicjacja listy problemów $L=P^0$
2. Niech $x^{*}=null$ i $v^{*}=-\infty$
3. Dopóki $L$ niepusty
   1. Wybierz i usuń problem z $L$
   2. Rozwiąż relaksację ciągłą
   3. Idź do 3 jeżeli zadanie sprzeczne. W p.p. oznaczmy rozwiązanie przez $x$ i funkcję celu przez $v$.
   4. Jeżeli $v\leq v^{*}$, idź do 3.
   5. Jeżeli  $x$ całkowitoliczbowe, to $v^{*}\leftarrow v,x^{*}\leftarrow x$ i idź do 3.
   6. W razie potrzeby, znajdź płaszczyzny odcinające $x$. Jeżeli istnieją to dodaje od relaksacji LP i idź do 3.2.
   7. Podziel problem na nowe problemy i dodaj je do $L$. Idź do 3.
4. Zwróć $x^{*}$