Комбинаторная оптимизация и TSP

Задача коммивояжёра - объехать 50 городов оптимальным маршрутом. Звучит просто, но число возможных маршрутов - 50!/2 ≈ 10⁶⁴. Перебор займёт дольше возраста Вселенной. Как же UPS и FedEx ежедневно планируют миллионы маршрутов? Как микросхемы проектируются с минимальной длиной проводников? Ответ - в интеллектуальных методах: **branch-and-bound, метод отсечений, Lin-Kernighan и аппроксимирующие алгоритмы с математическими гарантиями**.

• **Логистика**: UPS ежедневно решает миллионы TSP-подобных задач - алгоритм ORION на основе LK экономит 100M миль в год
• **VLSI дизайн**: компоновка микросхем - комбинаторная оптимизация; branch-and-cut в Cadence/Synopsis инструментах решает задачи с 10⁶ переменными
• **Планирование производства**: job-shop scheduling (в какой последовательности обрабатывать детали) - MIP с Gurobi/CPLEX решает задачи, ранее считавшиеся неразрешимыми

Предварительные знания

• Distributed Optimization
• Optimization in ML and Production

Branch and Bound: систематический поиск с отсечением

**Branch and Bound** (B&B) - универсальный алгоритм для задач целочисленной оптимизации. Он систематически исследует пространство решений, отсекая ветви дерева поиска, которые заведомо не могут дать лучшего результата, чем уже найденное решение.

**Выбор следующего узла**: - **Best-First**: узел с наименьшим LB → быстрое нахождение хорошего incumbent - **Depth-First (LIFO)**: уйти глубоко → быстро найти допустимое решение, меньше памяти - **Best-Bound + Depth-First**: гибрид - стандарт в commercial solvers **Выбор переменной для ветвления (branching variable)**: - **Most fractional**: переменная xᵢ с |xᵢ*-0.5| минимальным → наибольшая неопределённость - **Strong branching**: оценить обе ветви → лучший bound, дорого - **Pseudo-costs**: история изменений bound → быстрое приближение к strong branching

Метод отсечений: Gomory Cuts и MIP

**Метод отсечений** (Cutting Planes) улучшает LP relaxation, добавляя **дополнительные неравенства** (cuts), которые отсекают дробные решения LP, но не отсекают ни одного целого решения. Это делает LP bound теснее и ускоряет B&B.

**Branch-and-Cut** = Branch and Bound + Cutting Planes - стандарт в commercial MIP solvers (CPLEX, Gurobi). **Алгоритм**: 1. Решить LP relaxation в узле B&B дерева 2. Если дробное решение - искать violated cuts 3. Добавить cuts → улучшить LP bound → повторить 4. Если cuts не помогают - ветвиться **Реальные задачи** решаемые с Branch-and-Cut: - **TSP**: маршруты с 1000+ городов за секунды - **Scheduling**: расписание больниц, авиарейсов - **Facility Location**: где открывать склады - **Network Design**: проектирование коммуникационных сетей

Продвинутый локальный поиск: Lin-Kernighan для TSP

Для большинства NP-трудных комбинаторных задач точные методы (B&B) слишком медленны при n > 1000. **Локальный поиск** - эффективная эвристика: начать с некоторого решения и итеративно улучшать его, меняя «соседние» конфигурации.

**Or-opt** (Or, 1976): переместить группу из 1, 2 или 3 узлов в другую позицию маршрута - эффективнее 2-opt для несимметричных задач. **Tabu Search**: запрещать обратный переход после каждого move (tabu list). Позволяет выходить из локальных минимумов, двигаясь «вверх». **VNS (Variable Neighborhood Search)**: систематически менять окрестность, переключаясь между 2-opt, 3-opt, Or-opt, когда текущая окрестность истощена. **Качество vs время**:

Аппроксимирующие алгоритмы: гарантированное качество

**Аппроксимирующий алгоритм** - полиномиальный алгоритм с доказанной гарантией качества: результат не хуже чем ρ × OPT, где ρ - **коэффициент аппроксимации**. Это теоретически обоснованная замена точного алгоритма для NP-трудных задач.

**PTAS (Polynomial-Time Approximation Scheme)**: для любого ε>0 существует алгоритм с гарантией (1+ε) за время poly(n). Время может зависеть от ε экспоненциально: O(n^{1/ε}). **FPTAS (Fully Polynomial)**: время poly(n, 1/ε). Для Knapsack задачи. **Примеры**: - Euclidean TSP: PTAS (Arora, 1998) - для геометрической версии! - Metric TSP: нет PTAS (иначе P=NP), но есть 1.5-аппроксимация Christofides - Knapsack: FPTAS через динамическое программирование с масштабированием весов

Ключевые идеи

• **Branch and Bound**: систематический перебор с LP relaxation как нижней оценкой; прунинг отсекает ветви где LB ≥ incumbent
• **Cutting Planes / Gomory Cuts**: добавляют неравенства, отсекающие дробные LP решения не задевая целые; Branch-and-Cut = B&B + Cuts
• **Lin-Kernighan**: переменная глубина k-opt с candidate lists; практически лучший алгоритм для TSP, обычно в 0-2% от оптимума
• **Аппроксимирующие алгоритмы**: Christofides (1.5× для метрического TSP), жадный Set Cover (ln n×), MAX-CLIQUE не аппроксимируем лучше O(n^{1-ε})

Связанные темы

Комбинаторная оптимизация объединяет методы из разных областей:

• Целочисленное программирование — B&B и метод отсечений - основные алгоритмы для решения задач ILP и MIP
• Метаэвристики — Simulated Annealing, Genetic Algorithms - альтернативы локальному поиску при очень больших n или высокой сложности neighborhood
• Байесовская оптимизация — Для дорогостоящих комбинаторных задач (NAS, hyperparameter search) Bayesian Opt - эффективная black-box альтернатива

Вопросы для размышления

• Для задачи с 1000 городами и временем до 1 минуты: какой алгоритм вы выберете - точный B&B, LK или Christofides - и почему?
• Christofides даёт гарантию 1.5. Означает ли это, что на практике результат всегда близок к 1.5×OPT, или реальное качество намного лучше?
• Если задача NP-трудна и нет аппроксимации лучше O(n^{1-ε}), как можно применять её на практике для реальных больших инстанций?

Связанные уроки

• alg-34-approximation