Šaku ir ribu metodas

Pavyzdys- vagies uzdavinys:

$$\begin{eqnarray}\max_x \sum_{i=1}^m c_i x_i \\ \sum_{i=1}^m g_i x_i \le g,\ x_i =\{0,1\}. \end{eqnarray}$$

Ribos gaunamos iš pagalbiniu LP uzdaviniu:

$$\begin{eqnarray}C_1=c_1 +\max_x \sum_{i=2}^m c_i x_i \\ g_1+\sum_{i=1}^m g_i x... ... C_0=\max_x \sum_{i=2}^m c_i x_i \\ \sum_{i=2}^m g_i x_i \le g \end{eqnarray}$$

"Kertam" šaka $0$, jei $C_0 < c_1$.
Šaka $0$ reiškia neimti 1-jo daikto,
šaka $1$- imti.