Задача о покрытии множества (Set Covering): жадные алгоритмы и лагранжева релаксация

Математическая модель задачи о покрытии множества формулируется в терминах бинарного линейного программирования. Задано базовое множество (Универсум), состоящее из M элементов (районов, рейсов, клиентов). Также задана коллекция из N подмножеств этого универсума (каждое подмножество — это зона покрытия одного потенциального депо или маршрут одного экипажа). Каждое подмножество имеет свою стоимость активации. Искомые переменные являются булевыми (1, если подмножество выбрано, и 0, если отброшено). Целевая функция заключается в минимизации суммарной стоимости выбранных подмножеств. Система ограничений строится в виде матрицы из нулей и единиц и жестко требует: для каждого из M элементов универсума сумма бинарных переменных, покрывающих этот элемент, должна быть строго больше или равна единице.

Существуют три родственные задачи дискретной оптимизации, которые часто путают. В задаче о покрытии (Set Covering) элемент может быть покрыт несколько раз (район могут тушить две соседние пожарные части — это избыточно, но допустимо). В задаче о разбиении множества (Set Partitioning) каждый элемент должен быть покрыт ровно один и только один раз (рейс не могут обслуживать два разных экипажа одновременно, ограничения принимают вид строгих равенств). В задаче об упаковке (Set Packing) элементы могут оставаться непокрытыми, но пересечения строго запрещены (максимизация числа непересекающихся подмножеств). Из-за жесткости ограничений задача о разбиении является самой сложной для алгоритмического решения.

Вычислительная сложность поиска абсолютного оптимума для Set Covering колоссальна. Для крупных графов исследователи применяют аппроксимационные методы, самым известным из которых является Жадный алгоритм (Greedy Algorithm). На каждом шаге жадный алгоритм выбирает из доступных подмножеств то, которое покрывает максимальное количество еще не покрытых элементов универсума с минимальной удельной стоимостью (стоимость подмножества, деленная на число новых покрываемых им элементов). Этот процесс повторяется до тех пор, пока весь универсум не будет перекрыт. Математики строго доказали гарантию аппроксимации: стоимость решения, найденного жадным алгоритмом, никогда не превысит истинный глобальный оптимум более чем в H(M) раз (где H(M) — логарифмическое гармоническое число). Эта алгебраическая теорема делает алгоритм эталоном надежности в сверхбольших сетях.

Для нахождения более точных решений и точных нижних границ в исследовании операций активно используется Лагранжева релаксация (Lagrangian Relaxation). Метод берет жесткие ограничения покрытия и переносит их в целевую функцию с помощью множителей Лагранжа. Возникает парадоксальная ситуация: система позволяет алгоритму нарушать правила (оставлять элементы непокрытыми), но накладывает за каждое нарушение огромный финансовый штраф. Полученная ослабленная задача легко распадается на элементарные независимые подзадачи для каждого столбца. Итеративно обновляя множители Лагранжа с помощью метода субградиентного спуска (Subgradient Optimization), аналитики максимизируют эту нижнюю границу, максимально приближая ее к истинному целочисленному оптимуму. Этот подход стал ядром систем Crew Scheduling в авиации, позволяя компьютерам отсеивать миллиарды неэффективных маршрутов экипажей на стадии генерации столбцов.