Cheatsheet
Дискретная оптимизация — all topics on one page
Основы дискретной оптимизации и комбинаторика
Введение в дискретную оптимизацию, классические задачи и теория сложности
Почему дискретная оптимизация везде? → Масштаб проблемы → Классические задачи дискретной оптимизации → Целочисленное линейное программирование (ЦЛП) → Теория сложности: NP-полнота → Полный разбор: задача о рюкзаке
Компания FedEx доставляет 15 миллионов посылок в день. Маршрут каждого грузовика — это последовательность остановок. Как назначить маршруты, чтобы суммарный пробег был минимальным? Это задача маршрутизации транспорта — дискретная задача оптимизации. Или: авиакомпания должна составить расписание п...
Кажется, что можно просто перебрать все варианты. Но масштаб делает это невозможным. Задача коммивояжёра (найти кратчайший маршрут через n городов): число возможных маршрутов = (n−1)!/2. При n = 20: ≈ 60 квинтиллионов маршрутов. При 1 миллиарде операций в секунду перебор займёт 60 миллиардов лет ...
Решение? Умные алгоритмы, которые находят оптимум (или хорошее приближение) за разумное время.
Задача коммивояжёра (TSP): дано n городов с расстояниями dᵢⱼ между ними. Найти кратчайший маршрут, посещающий каждый город ровно один раз и возвращающийся в начало.
Графы как модели реального мира → Максимальный поток → Паросочетания в двудольных графах → Минимальное остовное дерево (MST) → Кратчайшие пути
- •Назначение учителей классам в школе
- •Распределение заказов между водителями такси (Яндекс.Такси — задача паросочетания в реальном времени!)
- •Медицина: совместимость доноров и реципиентов почки
- •Рекомендательные системы: сопоставление пользователей с контентом
Граф — математическая абстракция сети: вершины (узлы) и рёбра (связи). Интернет — граф маршрутизаторов. Социальная сеть — граф пользователей. Транспортная сеть — граф городов и дорог. Многие задачи дискретной оптимизации — это задачи на графах. Три классических класса: задачи потоков (как направи...
Постановка: ориентированная сеть G = (V, E) с пропускными способностями c(e) > 0 на каждом ребре. Источник s, сток t. Найти максимальный поток из s в t.
Поток f: поток на ребре (u,v) ≤ c(u,v), в каждой вершине (кроме s,t) сумма входящих = сумма выходящих потоков.
Разрез (S, V∖S) с s ∈ S, t ∈ V∖S: мощность разреза = сумма пропускных способностей рёбер из S в V∖S. Минимальный разрез = «узкое место» сети.
Мост между непрерывным и дискретным → Геометрия линейного программирования → ЛП-релаксация ЦЛП → Totally Unimodular Matrices → ЛП-двойственность для аппроксимационных алгоритмов → Полный разбор: задача о кратчайшем пути через ЛП → Симплекс-метод: ключевые детали → Внутренние методы → ЛП в машинном обучении
Definitions
- •Матрица инцидентности двудольного графа (строки — вершины, столбцы — рёбра)
- •Матрица «ограничений» задачи о максимальном потоке
- •Матрица «расписания» для задач с упорядоченными отрезками
Целочисленные задачи по природе своей дискретные. Но ключевой инструмент их решения — линейное программирование, непрерывная задача. Идея: «расслабить» целочисленные ограничения до непрерывных, решить гораздо более простую задачу, и использовать результат для нахождения целочисленного оптимума. Э...
Допустимое множество — пересечение полупространств — политоп (выпуклый многогранник).
Ключевая теорема: оптимальное решение ЛП всегда достигается в вершине политопа (при наличии оптимума). Вершина — точка, в которой n ограничений «активны» (выполняется равенство).
Число вершин: до C_{m+n}^n ≈ m^n/n! (экспоненциально). Но симплекс-метод на практике работает быстро, обходя лишь O(m) вершин. Метод Кармаркара (1984): полиномиальный — O(n^{3.5}), движется «через центр» политопа.
Методы ветвей и границ
Branch-and-Bound, Branch-and-Cut и их применение в ЦЛП
Принцип «умного перебора» → Структура алгоритма → Алгоритм Branch and Bound → Стратегии ветвления → Нижние оценки: ЛП и Лагранжева релаксация → Полный разбор: задача о рюкзаке через B&B → Производительность на практике → Эвристики поиска в B&B → Параллелизация → Применения
- •Если ЛП нет решения: отсекаем (задача нед допустима).
- •Если LB ≥ incumbent: отсекаем (не лучше текущего решения).
- •Если ЛП-оптимум целочисленный: обновляем incumbent.
- •Ветвь «вниз»: добавляем xᵢ ≤ ⌊α⌋
- •Ветвь «вверх»: добавляем xᵢ ≥ ⌈α⌉
- •Most Fractional: выбираем xᵢ ближайший к 0.5 (наиболее «дробный»)
- •Strong Branching: решаем ЛП-релаксацию обеих ветвей для нескольких кандидатов, выбираем лучший. Дорого, но даёт меньше узлов.
- •Pseudocost Branching: используем историю прошлых ветвлений для предсказания «полезности»
- •Best-First Search: выбираем узел с минимальной нижней оценкой. Быстро достигает оптимума, но требует много памяти.
- •Depth-First Search: углубляемся по одной ветви. Быстро находим допустимые решения (обновляем incumbent), экономия памяти.
- •Комбинация: depth-first до нахождения incumbent, потом best-first.
- •Эвристики выбора переменной для ветвления: pseudocost branching, strong branching, reliability branching
- •Эвристики выбора узла: best-first, depth-first, best-estimate
- •Презолвинг (presolve): упрощение задачи до начала поиска (фиксирование переменных, агрегирование ограничений)
- •Простейшие эвристики поиска целочисленного решения: feasibility pump, RINS, local branching — позволяют быстро найти incumbent для агрессивного отсечения
Полный перебор всех вариантов невозможен при больших n. Но можно быть умнее: если на каком-то шаге мы знаем, что «дальше ничего хорошего не будет» — отсечём целую ветвь дерева перебора. Метод ветвей и границ (Branch and Bound, B&B) систематизирует эту идею. Это основа всех промышленных ЦЛП-решате...
Дерево поиска: каждый узел — это подзадача с дополнительными ограничениями. Корень — исходная задача без дополнительных ограничений.
Нижняя оценка (lower bound, LB) для узла: минимально возможное значение целевой функции в этом узле. Обычно — оптимум ЛП-релаксации подзадачи.
Лучшее найденное решение (incumbent): лучшее целочисленное решение, найденное на данный момент.
Идея: «срезаем» дробные углы → Что такое режущая плоскость? → Отсечения Гомори → Отсечения для TSP: неравенства подтуров → Branch-and-Cut: алгоритм → Типы отсечений в современных решателях → Полный разбор: подтурные отсечения для TSP → Виды отсекающих плоскостей → Branch-and-Cut workflow → Применения
- •Найти нарушенное неравенство (задача разделения)
- •Добавить его в ЛП
- •Пересчитать ЛП
- •Gomory cuts: общие для любого ЦЛП
- •Cover cuts: специально для задач о рюкзаке (неравенства на покрытия)
- •Clique cuts: для задач с ограничениями кликов
- •Flow cuts: для задач с сетевой структурой
- •MIR cuts (Mixed Integer Rounding): обобщение Гомори
- •MIR-разрезы (Mixed Integer Rounding): обобщение Гомори на смешанные задачи
- •Cover cuts: для задач рюкзака — если подмножество предметов перевешивает W, то не все его элементы можно взять
- •Clique cuts: для конфликтного графа переменных — если в клике K переменных не более одной может быть 1, добавляем Σxᵢ ≤ 1
- •Flow cover cuts: для сетевых задач
- •Lift-and-project cuts (Балас, Сересса, Корнюэжолс): сильные разрезы из 0-1-ограничений
ЛП-релаксация может давать дробные оптимумы (x₁ = 1.5, x₂ = 0.7...). Можно ли добавить «умные» линейные ограничения, которые «срежут» эти дробные решения, не убирая при этом ни одного целочисленного? Именно это делают режущие плоскости (cutting planes). Вместо того чтобы сразу ветвиться, добавляе...
Определение: неравенство aᵀx ≤ b называется *режущей плоскостью* для ЦЛП, если: 1. Оно выполнено для всех целочисленных допустимых точек x ∈ {0,1}ⁿ 2. Оно нарушено для текущего ЛП-оптимума x* (дробного)
Добавляя такое неравенство, мы «отрезаем» дробный x*, но не теряем ни одного целочисленного решения. Новая ЛП-релаксация даёт лучшую (более высокую) нижнюю оценку.
Идея Ральфа Гомори (1958): взять строку симплекс-таблицы для дробной переменной и сгенерировать режущую плоскость.
Принцип оптимальности: разбиваем задачу на подзадачи → Принцип оптимальности Беллмана → Задача о рюкзаке: классическое ДП → Кратчайшие пути: ДП на графе → Наибольшая общая подпоследовательность (НОП/LCS) → TSP через ДП Хелда-Карпа
| i/w | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 4 | 4 | 4 |
| 2 | 0 | 0 | 3 | 4 | 4 | 7 |
| 3 | 0 | 2 | 3 | 5 | 6 | 7 |
- •Не берём i-й предмет: V[i][w] = V[i−1][w]
- •Берём i-й предмет (если w ≥ wᵢ): V[i][w] = V[i−1][w−wᵢ] + cᵢ
- •V[i][w] = max(V[i−1][w], V[i−1][w−wᵢ] + cᵢ) при w ≥ wᵢ
- •s₁[i] = s₂[j]: LCS[i][j] = LCS[i−1][j−1] + 1 (берём совпадение)
- •s₁[i] ≠ s₂[j]: LCS[i][j] = max(LCS[i−1][j], LCS[i][j−1]) (пропускаем один символ)
Динамическое программирование (ДП) — один из самых элегантных методов дискретной оптимизации. Идея проста и глубока одновременно: оптимальное решение большой задачи строится из оптимальных решений меньших подзадач. Это принцип оптимальности Беллмана. ДП «запоминает» результаты подзадач (memoizati...
Формулировка: оптимальное решение содержит оптимальные решения всех своих подзадач.
Когда принцип выполнен? Когда подзадачи независимы (решение одной не мешает другой) и структура оптимального решения допускает рекуррентное разложение.
Когда НЕ выполнен? Когда требуется учёт глобальных ограничений (например, задача о комивояжёре — подзадачи связаны между собой через ограничение «посетить каждый город один раз»). Впрочем, и TSP можно решить ДП за O(2ⁿ n²)!
Аппроксимационные алгоритмы
Теория аппроксимации, жадные алгоритмы и PTAS
Хорошее решение вместо идеального → Коэффициент аппроксимации → Vertex Cover: 2-аппроксимация → APX-трудность и барьеры аппроксимации → Bin Packing: анализ алгоритмов → Полный разбор: метрическая задача о развёртке → Классификация по гарантиям → Нижние границы аппроксимируемости → Применения
- •ρ = 1: точный алгоритм. Существует только для P-задач.
- •ρ = 2: решение не более чем вдвое хуже оптимума.
- •ρ = O(log n): логарифмическая аппроксимация (характерна для Set Cover).
- •Выбрать произвольное непокрытое ребро (u,v)
- •Добавить оба конца в C: C = C ∪ {u,v}
- •Добавить ребро в M: M = M ∪ {(u,v)}
- •Vertex Cover нельзя аппроксимировать лучше чем на (2−ε) при любом ε > 0
- •MAX-CUT нельзя аппроксимировать лучше чем на 0.878
- •Если замена уменьшает стоимость — делаем замену
- •Константная аппроксимация (ρ): ALG ≤ ρ · OPT для некоторого фиксированного ρ. Например, Vertex Cover — 2-аппроксимация (Бар-Йехуда, 1981).
- •Логарифмическая (O(log n)): Set Cover — ln n-аппроксимация через жадный (Йохансон, Ловаш, Чватал).
- •PTAS (Polynomial-Time Approximation Scheme): для любого ε > 0 существует алгоритм с гарантией (1+ε), полиномиальный по n (но возможно экспоненциальный по 1/ε).
- •FPTAS (Fully PTAS): полиномиальный и по n, и по 1/ε. Существует для рюкзака, не существует для TSP (если P ≠ NP).
- •MAX-3SAT: нельзя аппроксимировать лучше 7/8 (Хостад, 1997)
- •Vertex Cover: нельзя лучше 1.36 (Динур-Сафра)
- •Set Cover: нельзя лучше (1−ε) ln n (Файге, Мошковиц)
Если задача NP-трудная, мы не можем (предположительно) найти оптимальное решение за полиномиальное время. Но часто нам не нужна идеальная точность — достаточно «достаточно хорошего» решения. Аппроксимационные алгоритмы находят решения с гарантированным качеством: не более чем в ρ раз хуже оптимум...
Задача Vertex Cover: граф G = (V, E). Найти минимальное по размеру множество вершин C ⊆ V, такое что каждое ребро (u,v) имеет хотя бы один конец в C.
1. C = ∅, M = ∅ (M — паросочетание) 2. Пока существует ребро, не покрытое C: 3. Вернуть C
Доказательство 2-аппроксимации: M — паросочетание (рёбра в M не имеют общих вершин). Следовательно, |M| ≤ OPT (оптимум должен покрыть все рёбра M → нужно ≥ |M| вершин). |C| = 2|M| ≤ 2 · OPT. ✓
Когда жадность оптимальна? → Жадный алгоритм для MST: доказательство → Матроид: определение → Примеры матроидов → Теорема Радо-Эдмондса → Следствия → Пересечение матроидов → Полный разбор: жадный алгоритм для взвешенного матроида
- •Максимальное паросочетание в двудольном графе = пересечение двух матроидов разбиения
- •Раскраска двудольного графа = пересечение двух матроидов (назначение цветов)
Жадный алгоритм принимает локально наилучшее решение на каждом шаге, не пересматривая прошлых решений. Просто и быстро — но не всегда оптимально. Жадный алгоритм для задачи о рюкзаке даёт не оптимум. Жадный алгоритм Крускала для MST — даёт оптимум. Почему? Ответ — матроидная структура задачи. Мат...
Алгоритм Крускала: сортируем рёбра по весу. Жадно добавляем минимальное ребро, не создающее цикл.
Лемма об отсечении (Cut Lemma): для любого разреза (S, V∖S) минимальное ребро через разрез входит в MST.
Доказательство: пусть e* — минимальное ребро через разрез, и T — MST, не включающее e*. Добавим e* в T → образуется цикл, который пересекает разрез как минимум в одном другом ребре e'. Так как e* минимально в разрезе: w(e*) ≤ w(e'). Заменим e' на e* в T → новое дерево T' с весом w(T') ≤ w(T). Но ...
Семейство алгоритмов вместо одного → PTAS: определение и примеры → FPTAS: полиномиальная по 1/ε → Почему TSP на произвольных метриках не имеет PTAS? → Алгоритм Арора для евклидова TSP → PTAS для задач расписания → Идея PTAS на примере рюкзака → Метрический TSP и алгоритм Кристофидеса → Невозможность для общего TSP → Применения
- •Для любого ε > 0 алгоритм Aε находит (1+ε)-аппроксимацию
- •Время работы полиномиально по n (размеру входа) при фиксированном ε
Обычный аппроксимационный алгоритм даёт фиксированную гарантию: например, 2-аппроксимация. Но что, если нам нужно точнее — скажем, 1.01-аппроксимация? PTAS (Polynomial-Time Approximation Scheme) — это не один алгоритм, а целое семейство алгоритмов Aε, параметризованное точностью ε > 0: Aε находит...
Важно: зависимость от ε может быть произвольной. Например, O(n^{1/ε}) — PTAS, но O(2^{1/ε}·n) — тоже PTAS.
1. Находим максимальную ценность cmax = max cᵢ 2. Масштабируем: c̃ᵢ = ⌊cᵢ · n/(ε · cmax)⌋ (округляем вниз) 3. Решаем ДП с масштабированными ценностями: время O(n · Σc̃ᵢ) = O(n · n²/ε) = O(n³/ε) 4. Возвращаем найденный набор предметов
Теорема: это (1+ε)-аппроксимация. Доказательство: потери от масштабирования ≤ ε · OPT/n за предмет, суммарно ≤ ε · OPT.
Метаэвристики
Имитация отжига, генетические алгоритмы и локальный поиск
Идея: движение по ландшафту решений → Базовый локальный поиск → 2-opt для TSP: классика → Variable Neighborhood Search (VNS) → Tabu Search → Полный разбор: 2-opt для 5-городского TSP
- •Начальное решение s (случайное или жадное)
- •Функция окрестности N(s) = множество «соседних» решений
- •Критерий улучшения (first improvement или best improvement)
- •s ← s' (first improvement: берём первое лучшее; best improvement: лучшее из всех)
- •Вычислить улучшение от замены двух рёбер
- •Если улучшение > 0: сделать замену, начать заново
- •s' = random_neighbor(Nᵢ(s))
- •s'' = local_search(s')
- •Если f(s'') < f(s): s = s'', i = 1 (нашли улучшение — начали сначала)
- •Иначе: i++ (переходим к более широкой окрестности)
- •Найти лучшее решение s' ∈ N(s) TabuList
- •Если s' отсутствует → разрешить Tabu (аспирация)
- •Если f(s) < f(BestSolution): BestSolution = s
- •Добавить s в TabuList (удалить старейший, если список полный)
- •Длина TabuList: обычно √n или n. Слишком мало — осцилляция. Слишком много — сильно ограничен поиск.
- •Что хранить: само решение (дорого по памяти) или только «движение» (перемещение переменной)
Представьте «ландшафт» пространства решений: каждое решение — точка, её «высота» — значение целевой функции. Мы хотим найти глубину долину (минимум). Локальный поиск — это «спуск по ландшафту»: начинаем с произвольной точки и итерационно переходим к «соседней» точке с лучшим значением. Просто и б...
Алгоритм: 1. Текущее решение s = s₀ 2. Пока N(s) содержит лучшее решение s': 3. Возврат s (локальный оптимум)
Выбор окрестности — ключевой вопрос: маленькая окрестность → быстрая итерация, но слабое улучшение. Большая → медленная, но качественное улучшение.
Окрестность 2-opt: удаляем 2 ребра из тура и перестраиваем. Для маршрута a→b→c→d→e→a: удаляем (b,c) и (d,e), добавляем (b,d) и (c,e) — перестройка.
Физическая аналогия: медленное охлаждение → Алгоритм Simulated Annealing → Теоретические гарантии → Настройка параметров SA → SA для VLSI Layout → SA vs. другие методы → Тонкости имитационного отжига → Теоретическая сходимость → Параллельные варианты → Гибридные методы
| Метод | Гарантия | Скорость | Простота | Качество |
|---|---|---|---|---|
| Точный B&B | Оптимум | Медленно | Сложно | Отлично |
| Жадный | Нет | Быстро | Просто | Плохо |
| Локальный поиск | Нет | Быстро | Просто | Среднее |
| SA | Нет (практически) | Средне | Просто | Хорошо |
| Tabu | Нет | Средне | Сложно | Хорошо |
| GA | Нет | Медленно | Средне | Хорошо |
- •T₀ — начальная температура (высокая)
- •α ∈ (0,1) — темп охлаждения (обычно 0.9–0.99)
- •Lₖ — число итераций при температуре T_k
- •s' = random_neighbor(s) (случайный сосед)
- •Δ = f(s') − f(s) (изменение цели)
- •Если Δ < 0 (улучшение): s = s' (всегда принимаем)
- •Иначе: s = s' с вероятностью exp(−Δ/T)
- •Решение: координаты каждого компонента на сетке
- •Соседство: swap двух компонентов или перемещение одного компонента
- •Функция стоимости: суммарная длина Steiner-дерева для каждой сети
- •Начальная температура T₀: должна быть достаточно высокой, чтобы исходно принимались почти все ходы (≈ 80% acceptance rate)
- •Расписание охлаждения: классическое геометрическое T_k = α · T_{k-1} с α ∈ [0.85, 0.99]; адаптивные расписания (Lundy-Mees) уменьшают T в зависимости от прогресса
- •Окрестность: должна позволять «достижимость» любой точки. Слишком маленькие ходы — медленная сходимость, слишком большие — потеря локальной структуры
- •Parallel tempering (replica exchange): несколько копий SA с разными температурами обмениваются состояниями. Высокотемпературные копии исследуют, низкотемпературные эксплуатируют.
- •Population SA: многоагентный вариант с обменом информацией
- •GPU реализации: тысячи параллельных запусков SA с разными начальными точками
- •SA + Local Search: после нахождения хорошего решения SA — локальная оптимизация для финальной полировки
- •Memetic algorithms: SA внутри генетических алгоритмов как мутация
- •Variable Neighborhood Search (VNS): SA со сменой окрестности при стагнации
- •VLSI placement: размещение миллионов транзисторов на чипе. SA был стандартом в 1990-е, до сих пор используется в TimberWolf, Cadence
- •TSP: на задачах до 100 000 городов SA даёт решения в пределах 2-3% от оптимума
- •Расписание самолётов и экипажей: Air France, Lufthansa используют SA для динамической перепланировки при сбоях
- •Молекулярный дизайн: предсказание укладки белков, дизайн лекарств — SA на пространстве конформаций
- •Финансовые портфели: оптимизация с дискретными ограничениями (количество акций, сектора, риск-категории)
В металлургии «отжиг» — нагрев металла до высокой температуры и медленное охлаждение. При высокой температуре атомы имеют много энергии и могут «перепрыгивать» через энергетические барьеры, находя лучшую кристаллическую структуру. При медленном охлаждении — оседают в глобальном минимуме энергии (...
Идея метаэвристики Simulated Annealing (SA): имитировать этот процесс! Алгоритм принимает «ухудшающие» шаги с убывающей вероятностью — это позволяет «вырываться» из локальных оптимумов и в итоге найти глобальный.
Алгоритм: 1. s = s₀ (начальное решение), T = T₀, BestS = s₀ 2. Пока T > T_min: a. Повторить Lₖ раз: b. T ← α · T 3. Вернуть BestS
Вероятность принятия ухудшения: exp(−Δ/T). При T → ∞: вероятность → 1 (принимаем любой шаг, случайное блуждание). При T → 0: вероятность → 0 (принимаем только улучшения, обычный ЛП).
Эволюция как алгоритм оптимизации → Структура генетического алгоритма → Операторы для TSP → Теоретические основы: Schema Theorem → Memetic Algorithms (MA) → NSGA-II: многокритериальная оптимизация
- •*Рулеточный отбор*: P(выбрать s) = fitness(s) / Σ fitness. Аналог «вращения рулетки»
- •*Турнирный отбор*: случайно выбираем k особей, побеждает лучшая. Параметр k — «давление отбора»
- •*Swap*: случайно поменять два города местами
- •*Insertion*: вырвать один город и вставить в другое место
- •*Inversion (2-opt)*: обратить случайный подмаршрут
- •Чистый GA: исследует пространство глобально, но решения не «доведены»
- •Чистый LS: застревает в локальных оптимумах
- •MA: глобальный поиск + локальная «полировка»
- •Non-domination rank: решения ранжируются по «уровню доминирования»: ранг 1 = не доминируется никем, ранг 2 = доминируется только рангом 1, и т.д.
- •Crowding distance: расстояние до соседей по фронту. Предпочитаем «менее населённые» зоны — разнообразие.
Природная эволюция решила «задачу оптимизации» колоссальной сложности: создать существ, способных выживать в меняющейся среде. Механизм: случайные мутации, рекомбинация генов (кроссовер), естественный отбор. Генетические алгоритмы (GA) имитируют этот процесс для оптимизации. Вместо одной «частицы...
Хромосома (особь): кодировка решения в виде вектора. Для TSP — перестановка городов. Для задачи рюкзака — бинарная строка.
Приспособленность (fitness): значение целевой функции. В GA обычно работаем с максимизацией, поэтому: fitness = −cost для задач минимизации.
Задача: хромосома = перестановка городов π = (π₁, π₂, ..., πₙ). Кроссовер должен давать корректные перестановки (каждый город ровно один раз).