1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления (см. пункт 5). На 0-м шаге возлагаем D(0;1)=D, где D задается условиями (13.2) (13.3).
2. Решаются вспомогательные ЗЛП на множествах D(k;r). Пусть x(k;r) — оптимальные решения указанных ЗЛП.
3. Вычисляются границы на множествах D(k;r) за формулой x(k;r)= ]L(x(k;r))[, где ]z[ — наименьшее целое число, не меньше z.
4. Если существуют k, l такие, что x(k;l) — целочисленное решение и для всех веток r на k-у шаге выполняются соотношения
L(x(k;l))= x(k;l) £ x(k;r)
то x* = x(k;l) — оптимальное решение ЦЗЛП.
5. Разветвление осуществляется по нецелочисленной компоненте xj(k;r) (с минимальным j) решения x(k;r), что отвечает перспективной ветке k;r (если таких веток несколько, то выбирается ветка с минимальным r), добавлением к D(k;r) одного из подмножеств xj£[xj(k;r)] или xj³[xj(k;r)]+1.