Метод віток і меж

Метод віток і меж використовують як до повністю цілочисельних задач, так і до частково цілочисельних задач.

Спочатку розв'язують ослаблену задачу без обмежень на цілочисельність:

. (5.14)

повинна бути цілочисельною.

Тоді сферу допустимих рішень розбиваємо на дві підмножини і таким чином, що

:

: . (5.15)

Отже виключається інтервал , який не містить цілочисельних точок.

Початкову задачу розбиваємо на дві підзадачі. У кожній з областей , знаходяться оптимальні точки, якщо вони не задовольняють умові цілочисельності, знову здійснюємо розгалуження. Якщо отриманий оптимум виявляється допустимим (цілочисельним) для даної задачі, він фіксується і наголошується як найкращий. При цьому немає необхідності продовжувати розгалуження цієї підзадачі, оскільки поліпшити це рішення не вдасться.

Як тільки отримане допустиме (цілочисельне) рішення іншої підзадачі виявляється краще, його фіксують замість попереднього.

Процес розгалуження продовжується до тих пір, поки кожна підзадача не приведе до цілочисельного рішення або не буде встановлена неможливість поліпшення наявного рішення. Висновок про необхідність подальшого розбиття задачі робиться на основі введення межі.

Як межу використовуємо значення цільової функції отриманого допустимого цілочисельного рішення. Якщо будь-яке оптимальне рішення підзадачі забезпечує гірше значення цільової функції, ніж наявне рішення (прийняте як межа), то цю під задачу далі розглядати не слід.