О решении задач целочисленного программирования

Метод приближения непрерывными задачами. В соответствии с ним сначала решается задача линейного программирования без учета целочисленности, а затем в окрестности оптимального решения ищутся целочисленные точки.

Методы направленного перебора. Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х₀ ставится в соответствие число - "граница" А(Х). При решении задачи минимизации необходимо, чтобы А(Х₁) ≥ А(Х₂), если Х₁ входит в Х₂ или совпадает с Х₂ .

Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества Х_С на два - Х_1С и Х_2С . При этом пересечение Х_1С и Х_2С пусто, а их объединение совпадает с Х_С . Затем вычисляют границы А(Х_1С ) и А(Х_2С) и выделяют "ветвь" Х_{С +1} - то из множеств Х_1С и Х_2С , для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа

Для каждой конкретной задачи целочисленного программирования (другими словами, дискретной оптимизации) метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода.