2. Metoda płaszczyzn tnących

2.5. Metoda podziału i odcięć

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^{*}\)