Для знаходження оптимальних планів задач цілочислового програмування застосовують наступні групи методів:
• методи відтинання;
• комбінаторні методи;
• наближені методи.
Основою методів відтинання є ідея поступового «звуження» області допустимих розв’язків розглядуваної задачі. Пошук цілочислового оптимуму починається з розв’язування задачі з так званими послабленими обмеженнями, тобто без урахування вимог цілочисловості змінних. Далі введенням у модель спеціальних додаткових обмежень, що враховують цілочисловість змінних, многокутник допустимих розв’язків послабленої задачі поступово зменшуємо доти, доки змінні оптимального розв’язку не набудуть цілочислових значень.
До цієї групи належать:
а) методи розв’язування повністю цілочислових задач (дробовий алгоритм Гоморі);
б) методи розв’язування частково цілочислових задач (другий алгоритм Гоморі, або змішаний алгоритм цілочислового програмування).
Комбінаторні методи цілочислової оптимізації базуються на ідеї перебору всіх допустимих цілочислових розв’язків, однак вони реалізують процедуру цілеспрямованого перебору, під час якої розглядається лише частина розв’язків (досить невелика), а решта враховується одним зі спеціальних методів.
Найпоширенішим у цій групі методів є метод віток і меж.
Починаючи з розв’язування послабленої задачі, він передбачає розбиття початкової задачі на дві підзадачі виключенням областей, що не мають цілочислових розв’язків, і дослідженням кожної окремої частини многокутника допустимих розв’язків.
Для розв’язування задач із бульовими змінними застосовують комбіновані методи, причому оскільки змінні є бульовими, то методи пошуку оптимуму значно спрощуються.
Досить поширеними є також наближені методи розв’язування цілочислових задач лінійного програмування. Оскільки для практичних задач великої розмірності за допомогою точних методів не завжди можливо знайти строго оптимального розв’язку або для розв’язування задачі використовуються наближено визначені, неточні початкові дані, часто в реальних задачах досить обмежитись наближеним розв’язком, пошук якого є спрощеним.
Значна частина наближених алгоритмів базується на використанні обчислювальних схем відомих точних методів, таких, наприклад, як метод віток і меж.
До наближених методів відносяться: метод локальної оптимізації (метод вектора спаду); модифікації точних методів; методи випадкового пошуку та інш.