Целочисленное программирование: методы ветвей и границ

Метод ветвей и границ работает путем систематического разбиения пространства допустимых решений на подмножества (ветвление) и оценки нижней/верхней границ целевой функции для каждого подмножества (ограничение). Сначала решается ослабленная задача (без требования целочисленности), если полученное решение не является целочисленным, переменная с дробным значением используется для ветвления — создаются две подзадачи с дополнительными ограничениями. Если значение границы в какой-либо ветви оказывается хуже, чем уже найденное целочисленное решение, эта ветвь отсекается.

Для эффективности метода критически важно качество оценок границ. Чем ближе границы к значению целочисленного оптимума, тем меньше ветвей придется исследовать алгоритму. Помимо ветвления, используются методы отсекающих плоскостей (метод Гомори), которые позволяют сужать область допустимых значений путем добавления новых линейных ограничений, не исключающих целочисленные точки. Современные решатели объединяют эти подходы в метод ветвей и отсечений (branch-and-cut), что позволяет справляться с задачами, содержащими десятки тысяч переменных.

Целочисленное программирование лежит в основе решения задач коммивояжера, размещения предприятий, раскроя материалов, составления расписаний и планирования производства. Задачи с булевыми переменными (0-1 программирование) также относятся к этому классу и широко используются для моделирования принятия решений "да/нет". Сложность таких задач требует от исследователя глубокого понимания структуры конкретной задачи для выбора наиболее подходящей эвристики или стратегии ветвления.

Несмотря на вычислительную сложность, развитие аппаратного обеспечения и совершенствование алгоритмов позволяют сегодня решать целочисленные задачи, которые казались неразрешимыми еще десятилетие назад. Целочисленное программирование остается инструментом первой необходимости при оптимизации бизнес-процессов, где дискретность решений является фундаментальным требованием реальности.

Список литературы:
1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
2. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985.
3. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. — М.: Наука, 1979.