Введение в дискретную оптимизацию: задачи, модели, сложность

Почему дискретная оптимизация везде?

Компания FedEx доставляет 15 миллионов посылок в день. Маршрут каждого грузовика — это последовательность остановок. Как назначить маршруты, чтобы суммарный пробег был минимальным? Это задача маршрутизации транспорта — дискретная задача оптимизации. Или: авиакомпания должна составить расписание полётов, назначив экипажи на рейсы так, чтобы сократить затраты и соблюсти требования к отдыху. Такие задачи возникают в логистике, финансах, производстве, биоинформатике каждый день. Особенность дискретных задач: решения должны быть целыми числами или из конечного множества вариантов. Это делает их принципиально сложнее непрерывных.

Масштаб проблемы

Кажется, что можно просто перебрать все варианты. Но масштаб делает это невозможным. Задача коммивояжёра (найти кратчайший маршрут через n городов): число возможных маршрутов = (n−1)!/2. При n = 20: ≈ 60 квинтиллионов маршрутов. При 1 миллиарде операций в секунду перебор займёт 60 миллиардов лет — больше возраста Вселенной. При n = 200 — полный перебор невозможен физически никогда.

Решение? Умные алгоритмы, которые находят оптимум (или хорошее приближение) за разумное время.

Классические задачи дискретной оптимизации

Задача коммивояжёра (TSP): дано n городов с расстояниями dᵢⱼ между ними. Найти кратчайший маршрут, посещающий каждый город ровно один раз и возвращающийся в начало.

Математически: найти перестановку π ∈ Sₙ, минимизирующую Σᵢ d_{π(i), π(i+1)}.

Задача о рюкзаке (Knapsack): n предметов с ценностями cᵢ и весами wᵢ. Рюкзак вмещает W кг. Выбрать набор предметов максимальной суммарной ценности.

Задача: max Σᵢ cᵢxᵢ при Σᵢ wᵢxᵢ ≤ W, xᵢ ∈ {0,1}.

Задача покрытия множества (Set Cover): дано универсальное множество U и семейство подмножеств S₁,...,Sₘ. Выбрать минимальное подсемейство, покрывающее U. Применения: минимальное число пожарных депо для покрытия всего города.

MAX-CUT: граф G=(V,E). Разбить V на два множества S, V∖S, максимизируя число рёбер между ними. Применения: кластеризация данных, VLSI layout.

Целочисленное линейное программирование (ЦЛП)

Большинство дискретных задач можно записать как ЦЛП:

min cᵀx при Ax ≤ b, x ∈ ℤⁿ (или xᵢ ∈ {0,1})

Пример (TSP как ЦЛП): xᵢⱼ ∈ {0,1} — использование ребра (i,j). Ограничения: Σⱼ xᵢⱼ = 1 (въезд в каждый город), Σᵢ xᵢⱼ = 1 (выезд), yᵢ − yⱼ + n xᵢⱼ ≤ n−1 для i≠j≠1 (устранение подмаршрутов).

Современные ЦЛП-решатели (Gurobi, CPLEX, SCIP) решают реальные задачи с миллионами переменных.

Теория сложности: NP-полнота

Почему некоторые задачи «трудные»? Теория сложности даёт строгий ответ.

Класс P: задачи, решаемые за полиномиальное время O(nᵏ). Примеры: сортировка O(n log n), кратчайший путь в графе O(n²), линейное программирование O(n^{3.5}).

Класс NP: задачи, решение которых можно проверить за полиномиальное время. Например: TSP — данный маршрут можно проверить за O(n). Но найти оптимальный — неизвестно как.

NP-полные задачи: самые «трудные» в NP. Любая NP-задача полиномиально сводится к любой NP-полной. Первая NP-полная задача: SAT (Кук, 1971).

Гипотеза P ≠ NP (Millennium Prize Problem, 1 млн долларов): NP-полные задачи не имеют полиномиальных алгоритмов. Не доказана, но все верят.

Что это значит практически: три стратегии для NP-трудных задач:

1. Точные алгоритмы (Branch-and-Bound): работают для небольших или специальных случаев
2. Аппроксимационные алгоритмы: гарантированно близкое к оптимуму решение
3. Эвристики (SA, GA, Local Search): быстро, без гарантий, работает на практике

Полный разбор: задача о рюкзаке

Данные: W = 10 кг, 4 предмета: (c₁,w₁) = (6,4), (c₂,w₂) = (5,3), (c₃,w₃) = (4,2), (c₄,w₄) = (3,1).

Полный перебор (2⁴ = 16 вариантов): проверяем все подмножества.

{1,2}: w = 7, c = 11; {1,3}: w = 6, c = 10; {1,4}: w = 5, c = 9; {2,3}: w = 5, c = 9; {2,4}: w = 4, c = 8; {3,4}: w = 3, c = 7; {1,2,3}: w = 9, c = 15; {1,2,4}: w = 8, c = 14; {1,3,4}: w = 7, c = 13; {2,3,4}: w = 6, c = 12; {1,2,3,4}: w = 10, c = 18.

Оптимум: {1,2,3,4} с c = 18. Но при n = 50 предметах — 2⁵⁰ > 10¹⁵ вариантов, перебор нереален.

Жадный алгоритм (сортируем по cᵢ/wᵢ): ρ = [6,5,4,3]/[4,3,2,1] = [1.5, 1.67, 2.0, 3.0]. Порядок: предмет 4 (ρ=3.0), 3 (ρ=2.0), 2 (ρ=1.67), 1 (ρ=1.5). Берём: 4 (w=1), 3 (w=3), 2 (w=6), добавляем 1 (w=10 > 10). Результат: {2,3,4}, c=12. Не оптимально! Жадный алгоритм не гарантирует оптимум для рюкзака.