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

Математически задача формулируется следующим образом: дано базовое множество элементов $U$ (например, все авиарейсы, которые необходимо выполнить за сутки) и семейство $S$ его подмножеств (каждое подмножество — это допустимый график работы одного экипажа). Каждому подмножеству $j$ приписана стоимость $c_j$. Требуется выбрать такие подмножества, чтобы объединение их элементов охватывало все множество $U$, а суммарная стоимость выбранных подмножеств была минимальной. В терминах булевого линейного программирования задача минимизирует $\sum c_j x_j$ при ограничениях $\sum a_{ij} x_j \ge 1$ (для каждого элемента $i$), где $x_j \in \{0,1\}$, а матрица $A$ состоит из нулей и единиц.

SCP относится к классу NP-трудных задач Карпа. Поскольку размерность реальных задач авиакомпаний измеряется миллионами возможных графиков, прямое использование метода ветвей и границ (Branch and Bound) физически невозможно. Для быстрого нахождения приемлемых решений применяются жадные алгоритмы (Greedy Algorithms). На каждом шаге жадная эвристика выбирает то подмножество, которое покрывает наибольшее число еще не покрытых элементов с минимальными удельными затратами. Доказано, что жадный алгоритм дает приближение, которое хуже оптимального не более чем в $\ln(N)$ раз, где $N$ — общее число покрываемых элементов, что является выдающимся математическим результатом теории аппроксимации.

Для нахождения строгих математических оптимумов в логистике используется метод генерации столбцов (Column Generation). Идея в том, что в матрицу задачи не включаются все возможные подмножества сразу (их астрономически много). Вместо этого алгоритм решает усеченную задачу, получает двойственные переменные (оценки стоимости каждого непокрытого элемента) и передает их во вспомогательную задачу поиска кратчайшего пути с ограничениями. Эта вспомогательная задача динамически генерирует новый, наиболее выгодный график работы (столбец матрицы), который добавляется в главную задачу. Интеграция генерации столбцов в метод ветвления породила технологию Branch-and-Price.

Приложения задачи о покрытии не ограничиваются логистикой. В кибербезопасности SCP используется для оптимизации тестовых наборов, проверяющих все программные модули; в анализе данных — для выбора минимального набора классификаторов; в теории графов она эквивалентна задаче о доминирующем множестве. Умение сформулировать производственную проблему в терминах задачи о покрытии и применить передовые методы декомпозиции — это высший пилотаж в прикладном исследовании операций.

Список литературы:
1. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985.
2. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
3. Barnhart C. et al. Branch-and-Price: Column Generation for Solving Huge Integer Programs. — Operations Research, 1998.