Алгоритм розв’язування задач цілочислового програмування

Алгоритм розв’язування задач цілочислового програмування наступний:

1. Розв'язують задачу лінійного програмування без обмежень на цілочисельність, наприклад, симплекс-методом.

2. Якщо оптимальне рішення задачі лінійного програмування нецілочисельне, то проводять «велику ітерацію». Будують лінійне обмеження, якому задовольняє будь-яке цілочисельне рішення задачі і не задовольняє отримане оптимальне нецілочисельне значення. Геометрично це означає – провести перетин (гіперплощина), який відсікав би нецілочисельну вершину, не зачіпаючи решту цілочисельних точок. Такий перетин називають правильним. Правильний перетин повинен задовольняти наступним умовам:

1) умова відсікання - оптимальне рішення задачі лінійного програмування не задовольняє умові відсікання;

2) умова правильності - всі цілочисельні рішення задачі задовольняють умові відсікання.

Оскільки для початкової задачі додаткове обмеження (відсікання) даватиме неприпустиме базисне рішення, необхідно провести «малі ітерації» для отримання оптимального рішення. Якщо отримане оптимальне рішення нецілочисельне, то проводять наступне відсікання. В іншому випадку пошук завершений.

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