Линейное программирование как основа ЦЛП

Мост между непрерывным и дискретным

Целочисленные задачи по природе своей дискретные. Но ключевой инструмент их решения — линейное программирование, непрерывная задача. Идея: «расслабить» целочисленные ограничения до непрерывных, решить гораздо более простую задачу, и использовать результат для нахождения целочисленного оптимума. Это «LP-релаксация» — фундамент методов Branch-and-Bound, режущих плоскостей и аппроксимационных алгоритмов.

Геометрия линейного программирования

Стандартная форма ЛП: min cᵀx при Ax ≤ b, x ≥ 0.

Допустимое множество — пересечение полупространств — политоп (выпуклый многогранник).

Ключевая теорема: оптимальное решение ЛП всегда достигается в вершине политопа (при наличии оптимума). Вершина — точка, в которой n ограничений «активны» (выполняется равенство).

Число вершин: до C_{m+n}^n ≈ m^n/n! (экспоненциально). Но симплекс-метод на практике работает быстро, обходя лишь O(m) вершин. Метод Кармаркара (1984): полиномиальный — O(n^{3.5}), движется «через центр» политопа.

ЛП-релаксация ЦЛП

ЦЛП: min cᵀx при Ax ≤ b, x ∈ {0,1}ⁿ.

ЛП-релаксация: min cᵀx при Ax ≤ b, 0 ≤ x ≤ 1. (Убираем целочисленность)

Ключевые факты:

1. ЛП-оптимум ≤ ЦЛП-оптимум (нижняя оценка для задачи минимизации!)
2. Если ЛП-оптимум целочисленный → это и есть ЦЛП-оптимум
3. «Зазор целочисленности»: OPT_ЦЛП / OPT_ЛП — показывает «потери» от дробности

Пример: задача рюкзака с W=5, n=3: (c₁,w₁)=(4,3), (c₂,w₂)=(3,2), (c₃,w₃)=(2,1).

ЦЛП-оптимум: x=(0,1,1), c=5. ЛП-релаксация: оптимум x=(0, 1, 1, 2/3) на самом деле достигается при x₁=2/3, x₂=1, x₃=0 по соображениям жадности — нужно считать точнее, но ЛП-оптимум может быть 5.67, ЦЛП = 5. Зазор ≈ 13%.

Totally Unimodular Matrices

Определение: матрица A называется вполне унимодулярной (TU), если определитель каждой квадратной подматрицы ∈ {−1, 0, +1}.

Теорема (Хоффман-Крускал): если A — TU-матрица и b целочисленный, то вершины политопа {x: Ax ≤ b, x ≥ 0} — целочисленные. Следовательно, ЛП-оптимум = ЦЛП-оптимум — решать ЦЛП через ЛП!

Примеры TU-матриц:

• Матрица инцидентности двудольного графа (строки — вершины, столбцы — рёбра)
• Матрица «ограничений» задачи о максимальном потоке
• Матрица «расписания» для задач с упорядоченными отрезками

Следствие: задача максимального паросочетания, задача о максимальном потоке, задача кратчайшего пути — все решаются ЛП!

ЛП-двойственность для аппроксимационных алгоритмов

Двойственность ЛП: для задачи (P): min cᵀx при Ax ≥ b, x ≥ 0 двойственная (D): max bᵀy при Aᵀy ≤ c, y ≥ 0.

Слабая двойственность: любое допустимое y дает bᵀy ≤ cᵀx для любого допустимого x. Следствие: bᵀy — нижняя оценка оптимума (P).

Метод Primal-Dual: строим допустимое целочисленное решение x^ и допустимое двойственное y^ параллельно. Гарантия: cᵀx^ ≤ ρ · bᵀy^ ≤ ρ · OPT → ρ-аппроксимация.

Пример: Set Cover через Primal-Dual

Каждый элемент u ∈ U должен быть покрыт хотя бы одним выбранным множеством. ЦЛП: min Σⱼ cⱼxⱼ при Σⱼ: u∈Sⱼ xⱼ ≥ 1, xⱼ ∈ {0,1}.

Двойственная: max Σᵤ yᵤ при Σᵤ: u∈Sⱼ yᵤ ≤ cⱼ, yᵤ ≥ 0.

Primal-Dual алгоритм: пока существует непокрытый u: увеличиваем yᵤ до тех пор, пока какое-то ограничение двойственной задачи не стало «жёстким» → добавляем это Sⱼ в решение.

Гарантия: ln n-аппроксимация (ln n — максимальная степень вершины в гиперграфе покрытия).

Полный разбор: задача о кратчайшем пути через ЛП

Граф: V = {1,2,3,4}, рёбра: (1,2)=2, (1,3)=4, (2,3)=1, (2,4)=5, (3,4)=2. Найти кратчайший путь от 1 до 4.

ЛП-формулировка потока: xᵢⱼ ≥ 0 — поток по ребру (i,j). Задача: min Σ dᵢⱼ xᵢⱼ при балансных ограничениях (поток 1 из источника, −1 в сток, 0 везде).

Решение: симплекс даёт x₁₂=1, x₂₃=1, x₃₄=1 (путь 1→2→3→4, стоимость = 2+1+2 = 5). Решение целочисленное (матрица сетевых задач — TU)!

Двойственное ЛП — потенциалы вершин: max π₄ − π₁ при πⱼ − πᵢ ≤ dᵢⱼ. Оптимум: π₁=0, π₂=2, π₃=3, π₄=5. Двойственный оптимум = 5 = примальный ✓ (сильная двойственность).

Симплекс-метод: ключевые детали

Симплекс-метод (Данциг, 1947) последовательно перемещается между вершинами политопа, на каждом шаге улучшая значение целевой функции. Алгоритм:

1. Найти стартовую вершину (фаза I)
2. Проверить условие оптимальности: коэффициенты сокращённой стоимости ≥ 0
3. Если нет — выбрать переменную с отрицательной сокращённой стоимостью (правило Бленда, Данцига, наибольшего наклона) и сделать поворот

В худшем случае симплекс посещает экспоненциальное число вершин (пример Кли-Минти, 1972), но на практике обычно требуется лишь O(m+n) шагов. Это явление до сих пор не имеет полного теоретического объяснения — гипотеза Хирша о диаметре политопа была опровергнута лишь в 2010 г.

Внутренние методы

Метод Кармаркара (1984) и его наследники (примал-дуальный метод следящего пути) движутся через внутреннюю часть политопа, имеют гарантированную полиномиальную сложность O(n^{3.5} L), где L — размер записи задачи. На практике для очень больших ЛП (миллионы переменных) внутренние методы конкурируют с симплексом — выбор зависит от структуры разреженности матрицы A.

ЛП в машинном обучении

ЛП лежит в основе многих методов: SVM с L1-штрафом сводится к ЛП, оптимальный транспорт между дискретными распределениями — это ЛП, ранжирование документов через LP-relaxation. Современные нейросети используют ЛП-релаксации внутри слоёв (например, для дифференцируемого решения комбинаторных задач — Pointer Networks).