Podręcznik

W poszukiwanym rozwiązaniu optymalnym muszą być spełnione następujące warunki optymalności dla zadania ZPL z dodanymi cięciami \(\max\{c^Tx: Ax \leq b, Dx \leq d, x \geq 0\}\)

1. prymalna dopuszczalność (\(y_{i0}\geq 0, i=1, \ldots, m\))
2. całkowitoliczbowość (\(y_{i0}\) całkowite)
3. dualna dopuszczalność (\(y_{0j}\geq 0, j \in N\))

Możliwe są trzy podejścia, w których dwa z powyższych warunków są zawsze spełnione, natomiast trzeci ulega relaksacji. Trzy podstawowe algorytmy metod płaszczyzn tnących są  następujące 

1. algorytm form całkowitych (spełnione warunki 1 i 3)
2. metoda prymalna całkowitoliczbowa (spełnione warunki 1 i 2)
3. metoda dualna całkowitoliczbowa (spełnione warunki 2 i 3)

Ogólny schemat algorytmu form całowitych jest następujący

1. Krok \(t=0\), \(P^t=P\)
2. Rozwiąż ZPL
   \(\max\{c^Tx: x \in P^t \}\)
   Niech \(x^t\) będzie rozwiązaniem na \(P^t\)
   1. Jeżeli spełnione są wszystkie warunki optymalności to STOP
   2. Skonstruuj płaszczyznę tnącą odcinającą \(x^t\) rozwiązując problem separowalności \(x^t\) od \(conv(X)\).
   3. \(t=t+1\), idź do 2 poziom wyżej

Jest to ogólny schemat, który pozostawia otwarte pytanie w jaki sposób generować nowe cięcia.