Целочисленное программирование

Целочисленное программирование — это раздел математического программирования, в котором на переменные, входящие в целевую функцию и ограничения, накладывается условие целочисленности. Такие задачи возникают, когда переменные по своей природе не могут быть дробными (например, количество единиц продукции, число станков, количество людей) или когда требуется принимать дискретные решения (например, «да/нет»). Целочисленное программирование является одним из ключевых инструментов исследования операций и широко применяется в логистике, планировании производства, управлении проектами, экономике и компьютерных науках.

Основные понятия и классификация

В общем виде задача целочисленного программирования формулируется следующим образом: найти максимум или минимум линейной (или нелинейной) функции при системе линейных (или нелинейных) неравенств и равенств, при этом все или часть переменных должны принимать только целые значения.

Типы задач

По степени целочисленности различают:

• Полностью целочисленное программирование — все переменные задачи должны быть целыми.
• Частично целочисленное программирование — только часть переменных обязана быть целыми.
• Булево (двоичное) программирование — переменные могут принимать только значения 0 или 1. Этот подкласс часто используется для моделирования логических условий, выбора альтернатив, задач о назначениях и покрытиях.

Отличие от непрерывной оптимизации

В отличие от задач линейного программирования (ЛП), где оптимальное решение может быть дробным, в целочисленном программировании даже небольшое изменение условий может привести к существенному изменению решения. Задачи целочисленного программирования, как правило, относятся к классу NP-трудных, то есть для них не известны полиномиальные алгоритмы решения в общем случае.

История развития

Первые постановки задач с целочисленными переменными восходят к работам советского математика Леонида Канторовича (1939 год), который в рамках планирования производства и распределения ресурсов ввёл понятие «целочисленных решений». Однако систематическое развитие целочисленное программирование получило в 1950-х годах.

В 1954 году американские математики Джордж Данциг, Делберт Рэй Фулкерсон и Селмер Джонсон разработали метод отсечений (метод Гомори), который позволял решать полностью целочисленные задачи путём последовательного добавления дополнительных ограничений. В 1960 году Ральф Гомори опубликовал строгое обоснование этого метода.

В 1965 году А. Л. Ланда и А. Г. Дойг предложили метод ветвей и границ, который стал основой для большинства современных коммерческих и открытых решателей (solvers). В 1970-х годах были разработаны методы на основе планов отсечения (cutting plane methods) и комбинированные подходы (branch-and-cut).

В СССР значительный вклад в теорию и практику целочисленного программирования внесли учёные: В. А. Емеличев, В. И. Шевченко, Ю. Ю. Финкельштейн. В 1980-х годах активно развивались методы декомпозиции и эвристические алгоритмы.

Методы решения

Из-за NP-трудности задач целочисленного программирования для их решения применяются как точные, так и приближённые (эвристические) методы.

Точные методы

1. Метод ветвей и границ (Branch and Bound) — наиболее распространённый точный метод. Идея заключается в решении непрерывной релаксации задачи (отбрасывание условия целочисленности) и последующем ветвлении по дробным переменным. Для каждого подмножества решений вычисляется верхняя (или нижняя) граница, и если она хуже уже найденного целочисленного решения, ветвь отсекается.

1. Метод отсечений (Cutting Plane Method) — к исходной задаче последовательно добавляются дополнительные линейные неравенства (отсечения), которые отсекают дробные вершины, не затрагивая целочисленные решения. Наиболее известны отсечения Гомори и отсечения Чвáтала.

1. Метод ветвей и отсечений (Branch and Cut) — комбинация двух предыдущих подходов: на каждом узле дерева ветвления применяются отсечения, что позволяет сократить перебор.

1. Метод ветвей и цен (Branch and Price) — используется для задач с большим числом переменных (например, задачи маршрутизации транспорта). В основе лежит генерация столбцов — переменные добавляются в задачу по мере необходимости.

Приближённые и эвристические методы

Для задач большой размерности, где точные методы требуют неприемлемого времени, применяются:

• Жадные алгоритмы — последовательный выбор наилучшего локального варианта.
• Алгоритмы локального поиска — итеративное улучшение текущего решения путём малых изменений.
• Метаэвристики: генетические алгоритмы, имитация отжига, муравьиные алгоритмы, роевой интеллект.
• Методы релаксации — например, округление дробного решения линейного программирования до целых чисел с последующей корректировкой.

Применение

Целочисленное программирование находит применение в самых разных областях, где требуется принятие дискретных решений.

Логистика и транспорт

• Задача коммивояжёра — поиск кратчайшего замкнутого маршрута, проходящего через заданные города ровно один раз.
• Задача маршрутизации транспорта (VRP) — оптимизация развозки грузов по клиентам с учётом вместимости автомобилей и временных окон.
• Задача о назначениях — распределение работников по рабочим местам с минимальной стоимостью или максимальной эффективностью.

Производственное планирование

• Задача раскроя — минимизация отходов при раскрое листовых материалов или рулонов.
• Планирование загрузки оборудования — распределение заказов по станкам с учётом сроков и производительности.
• Управление запасами — определение оптимальных партий поставок и точек заказа.

Финансы и экономика

• Портфельная оптимизация — выбор набора активов с учётом минимальной доли вложений и ограничений на риски.
• Бюджетирование проектов — выбор проектов для финансирования при ограниченном бюджете (задача о ранце).

Компьютерные науки

• Размещение серверов и баз данных — минимизация задержек при заданной топологии сети.
• Проектирование интегральных схем — размещение элементов на кристалле и трассировка соединений.
• Криптография — некоторые задачи целочисленного программирования используются в криптоанализе.

Энергетика

• Оптимизация режимов работы электростанций — распределение нагрузки между агрегатами с учётом минимальных и максимальных мощностей.
• Планирование ремонтов — составление графиков вывода оборудования в ремонт при ограничениях на резервирование.

Программное обеспечение

Для решения задач целочисленного программирования существует множество программных пакетов:

• Коммерческие решатели: IBM ILOG CPLEX, Gurobi, FICO Xpress, MOSEK — обладают высокой производительностью и поддерживают все основные методы.
• Открытые решатели: SCIP, CBC (COIN-OR Branch and Cut), GLPK (GNU Linear Programming Kit), HiGHS.
• Языки моделирования: AMPL, GAMS, Pyomo (Python), JuMP (Julia) — позволяют формулировать задачи в удобной форме и передавать их решателям.

В России также разрабатываются специализированные решатели, например, в рамках проектов Минобрнауки и Российской академии наук, однако они менее распространены на международном рынке.

Сложность и перспективы

Несмотря на значительные успехи в разработке алгоритмов, решение крупномасштабных задач целочисленного программирования остаётся вычислительно сложным. Современные исследования направлены на:

• Разработку более эффективных отсечений и предобработки (presolve).
• Использование параллельных и распределённых вычислений.
• Применение методов машинного обучения для выбора стратегий ветвления и отсечения.
• Интеграцию целочисленного программирования с другими областями оптимизации (стохастическое программирование, динамическое программирование).

Источники

• Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: алгоритмы и сложность. — М.: Мир, 1985.
• Шевченко В. И. Целочисленное программирование. — М.: Наука, 1981.
• Wolsey L. A. Integer Programming. — 2nd ed. — Wiley, 2020.
• Nemhauser G. L., Wolsey L. A. Integer and Combinatorial Optimization. — Wiley, 1988.
• Канторович Л. В. Математические методы организации и планирования производства. — Л.: Изд-во ЛГУ, 1939.