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

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

¶Формальная постановка задачи

Задача целочисленного линейного программирования формулируется следующим образом:

Минимизировать (или максимизировать) линейную целевую функцию:

\[ c^T x = \sum_{j=1}^{n} c_j x_j \]

при ограничениях:

\[ Ax \leq b \] \[ x \in \mathbb{Z}^n \]

Где:

• \( x = (x_1, x_2, \dots, x_n) \) — вектор целочисленных переменных решения;
• \( c = (c_1, c_2, \dots, c_n) \) — вектор коэффициентов целевой функции;
• \( A \) — матрица коэффициентов ограничений размером \( m \times n \);
• \( b = (b_1, b_2, \dots, b_m) \) — вектор правых частей ограничений.

Частным случаем является частично целочисленное линейное программирование (Mixed-Integer Linear Programming, MILP), где часть переменных может быть вещественными, а другая часть — целыми. Ещё один важный подкласс — булево линейное программирование (0-1 ЦЛП), где все переменные принимают значения 0 или 1.

¶Сложность и фундаментальные свойства

Решение задач ЦЛП принципиально сложнее, чем задач ЛП. Основные причины:

1. Дискретность пространства решений: в отличие от непрерывного пространства ЛП, допустимое множество ЦЛП состоит из изолированных точек (целочисленной решётки). Это исключает возможность использования градиентных методов, основанных на непрерывном движении.
2. NP-трудность: задача ЦЛП в общем виде (с произвольными целыми коэффициентами) является NP-трудной. Это означает, что не существует известного алгоритма, решающего любую задачу ЦЛП за полиномиальное время. Однако для некоторых частных случаев (например, задачи с унимодулярной матрицей) существуют эффективные полиномиальные алгоритмы.
3. Отсутствие локальной оптимальности: в ЦЛП понятие локального оптимума не имеет смысла, так как любое изменение переменной на единицу может кардинально изменить значение целевой функции. Поэтому поиск глобального оптимума требует перебора или его эквивалентов.
4. Целочисленный зазор: разница между оптимальным значением релаксированной задачи ЛП (где переменные считаются вещественными) и оптимальным значением исходной задачи ЦЛП называется целочисленным зазором. Этот зазор может быть как нулевым (для задач с унимодулярной матрицей), так и сколь угодно большим.

¶Классификация задач ЦЛП

Задачи ЦЛП классифицируются по нескольким признакам:

¶По типу переменных

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

¶По структуре ограничений

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

¶По направлению оптимизации

• Минимизация: например, минимизация затрат, времени, расстояния.
• Максимизация: например, максимизация прибыли, производительности, надёжности.

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

Для решения задач ЦЛП разработано несколько основных подходов:

¶1. Метод ветвей и границ (Branch and Bound)

Это наиболее распространённый точный метод. Алгоритм:

1. Решается релаксированная задача ЛП (без целочисленности).
2. Если решение целочисленное — задача решена.
3. Если нет — выбирается дробная переменная, и задача разбивается на две подзадачи (ветви): с ограничением \( x_j \leq \lfloor x_j^ \rfloor \) и \( x_j \geq \lceil x_j^ \rceil \).
4. Для каждой подзадачи решается ЛП-релаксация, и процесс повторяется.
5. Используются границы (оценки) для отсечения неперспективных ветвей.

¶2. Метод отсекающих плоскостей (Cutting Planes)

Идея метода заключается в последовательном добавлении дополнительных линейных ограничений (отсечений), которые «отрезают» дробные решения, не затрагивая целочисленные. Наиболее известные типы отсечений:

• Отсечения Гомори (Gomory cuts) — строятся на основе симплекс-таблицы.
• Отсечения для смешанно-целочисленных задач (MIR cuts).
• Кликовые отсечения (clique cuts) — для задач с булевыми переменными.

¶3. Комбинированный метод ветвей и отсечений (Branch and Cut)

Объединяет идеи ветвей и границ и отсекающих плоскостей. На каждом узле дерева ветвления сначала добавляются отсечения, а затем, если решение остаётся дробным, производится ветвление. Этот метод лежит в основе большинства современных коммерческих решателей (CPLEX, Gurobi, Xpress).

¶4. Метод ветвей и цен (Branch and Price)

Используется для задач с очень большим числом переменных (например, задачи маршрутизации транспорта). Вместо явного перечисления всех переменных применяется генерация столбцов — динамическое добавление новых переменных в процессе решения.

¶5. Эвристические и метаэвристические методы

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

• Жадные алгоритмы: последовательное принятие локально оптимальных решений.
• Локальный поиск: итеративное улучшение текущего решения путём малых изменений.
• Генетические алгоритмы: эволюционная оптимизация.
• Имитация отжига (Simulated Annealing).
• Муравьиные алгоритмы (Ant Colony Optimization).

¶6. Динамическое программирование

Эффективно для некоторых специальных классов задач, например, для задачи о рюкзаке (Knapsack problem) с целыми весами.

¶Применение

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

¶Производство и логистика

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

¶Транспорт

• Задача коммивояжёра: поиск кратчайшего маршрута, проходящего через все заданные точки.
• Маршрутизация транспорта (Vehicle Routing Problem, VRP): оптимизация маршрутов для парка транспортных средств.
• Расписание движения поездов и самолётов: составление расписаний с учётом ограничений на время, ресурсы и безопасность.

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

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

¶Энергетика

• Планирование режимов работы электростанций: включение/выключение агрегатов (unit commitment problem).
• Оптимизация сетей электроснабжения: размещение подстанций, выбор маршрутов линий электропередачи.

¶Телекоммуникации

• Размещение базовых станций: выбор местоположения с учётом покрытия и затрат.
• Проектирование сетей: оптимизация топологии сети с целочисленными решениями.

¶Информационные технологии

• Задача о назначениях: распределение задач по процессорам или сотрудникам.
• Оптимизация запросов к базам данных: выбор плана выполнения запроса.

¶Примеры известных задач ЦЛП

¶Задача о рюкзаке (Knapsack problem)

Дано \( n \) предметов, каждый с весом \( w_i \) и ценностью \( v_i \). Необходимо выбрать подмножество предметов, чтобы суммарный вес не превышал вместимость рюкзака \( W \), а суммарная ценность была максимальной. Формально: \[ \max \sum_{i=1}^n v_i x_i \] \[ \sum_{i=1}^n w_i x_i \leq W \] \[ x_i \in \{0, 1\} \]

¶Задача коммивояжёра (Traveling Salesman Problem, TSP)

Коммивояжёр должен посетить \( n \) городов, побывав в каждом ровно один раз, и вернуться в исходный город, минимизируя общее расстояние. Формулировка с использованием бинарных переменных \( x_{ij} \) (едет ли он из города \( i \) в город \( j \)) требует дополнительных ограничений (например, ограничения Миллера — Такера — Землина), чтобы исключить подциклы.

¶Задача о назначениях (Assignment problem)

Необходимо назначить \( n \) работников на \( n \) работ, чтобы каждый работник выполнял ровно одну работу, а каждая работа выполнялась ровно одним работником, минимизируя суммарные затраты. Матрица ограничений этой задачи является полностью унимодулярной, поэтому она решается как задача ЛП.

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

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

¶Коммерческие решатели

• IBM ILOG CPLEX — один из наиболее мощных и широко используемых решателей.
• Gurobi Optimizer — современный высокопроизводительный решатель.
• FICO Xpress — коммерческий решатель для MILP.
• MOSEK — решатель, специализирующийся на выпуклой оптимизации, но также поддерживающий MILP.

¶Открытые решатели

• SCIP (Solving Constraint Integer Programs) — один из лучших открытых решателей для MILP.
• GLPK (GNU Linear Programming Kit) — решатель для задач ЛП и ЦЛП.
• CBC (COIN-OR Branch and Cut) — решатель с открытым исходным кодом.
• HiGHS — современный высокопроизводительный решатель с открытым исходным кодом.

¶Языки моделирования

• AMPL — язык для математического программирования.
• GAMS — язык для моделирования оптимизационных задач.
• Pyomo (Python) — библиотека для постановки и решения задач оптимизации.
• JuMP (Julia) — пакет для математического программирования на языке Julia.

¶Источники

1. Волков И.К., Загоруйко Е.А. Исследование операций. — М.: МГТУ им. Н.Э. Баумана, 2002.
2. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. — М.: Наука, 1969.
3. Немхаузер Г., Вулси Л. Целочисленное программирование. — М.: Мир, 1977.
4. Schrijver A. Theory of Linear and Integer Programming. — Wiley, 1998.
5. Wolsey L.A. Integer Programming. — Wiley, 1998.