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

Комбинаторная оптимизация — подраздел математической оптимизации, занимающийся поиском оптимального объекта (по заданной целевой функции) из конечного множества объектов, где множество допустимых решений дискретно или может быть сведено к дискретному. Область лежит на стыке исследования операций, теории алгоритмов, теории сложности вычислений и прикладной математики. Многие задачи комбинаторной оптимизации относятся к классу NP-трудных, что означает отсутствие известных полиномиальных алгоритмов точного решения для них в общем случае (если P ≠ NP). Вместе с тем для специальных классов задач — максимального потока, минимального остовного дерева, паросочетаний в графах — существуют эффективные полиномиальные алгоритмы.

Задачи комбинаторной оптимизации обычно формулируются как минимизация (или максимизация) целевой функции $f(x)$ по переменным $x\in X$, где $X$ — конечное или счётное множество допустимых решений (подмножества, перестановки, разбиения и т. д.), а $f$ отражает стоимость или эффективность. Многие задачи эквивалентны целочисленному линейному программированию (ЦЛП).

История и предпосылки

Математическое изучение комбинаторных оптимизационных задач началось задолго до оформления дисциплины. Отдельные задачи рассматривались начиная с XVIII века, однако как целостная область знаний комбинаторная оптимизация сформировалась лишь в 1950-х годах в рамках исследования операций.

XVIII–XIX века: ранние формулировки

В 1784 году Г. Монж сформулировал задачу о назначении в транспортном контексте — как задачу минимизации суммарного расстояния при перемещении грунта между двумя областями равной площади. Монж предложил геометрический метод решения, основанный на непересекающихся маршрутах. Эта работа считается одним из первых примеров комбинаторной оптимизационной задачи в формальной математической постановке.

Начало XX века: теория паросочетаний

В 1912–1931 годах Г. Фробениус, Д. Кёниг и Е. Эгервари заложили основы теории паросочетаний в двудольных графах. Теорема Кёнига (1931) утверждает равенство размера максимального паросочетания и минимального вершинного покрытия в двудольном графе — результат, ставший одним из краеугольных камней комбинаторной оптимизации на графах.

1930–1940-е годы: линейное программирование

Параллельно в нескольких странах развивались подходы к транспортной задаче:

• А. Н. Толстой (1930) предложил эвристики для оптимизации советских грузовых перевозок.
• Л. В. Канторович (1939) сформулировал задачи промышленного планирования и транспортировки в форме, близкой к линейному программированию (ЛП), и предложил метод разрешающих множителей. Канторович впоследствии разделил Нобелевскую премию по экономике (1975) за вклад в теорию оптимального распределения ресурсов.
• Ф. Хичкок (1941) дал формальное математическое описание транспортной задачи.
• Т. К. Купманс (1942–1948) разработал локальный поиск для задач танкерных перевозок во время Второй мировой войны.

В 1947 году Дж. Данциг предложил симплекс-метод для линейного программирования, что объединило разрозненные транспортные, производственные и логистические задачи в единую алгоритмическую рамку.

1950-е годы: расцвет специализированных алгоритмов

В этот период были созданы ключевые алгоритмы, определившие облик дисциплины:

• Задача коммивояжёра (TSP). В 1954 году Данциг, Фалкерсон и Джонсон решили задачу коммивояжёра для 49 американских городов с помощью линейного программирования и метода отсекающих плоскостей (cutting planes), получив оптимальный тур длиной 12 345 миль. Это стало первым крупномасштабным решением TSP и продемонстрировало мощь ЛП-подхода к дискретным задачам.
• Задача о назначении. В 1955 году Г. Кун разработал венгерский метод (Hungarian method), основанный на теоретических работах Эгервари (1931). Алгоритм решает задачу назначения за полиномиальное время; в реализации Мункреса (1957) сложность составляет $O(n^3)$.
• Максимальный поток. В 1954–1956 годах Л. Р. Форд и Д. Р. Фалкерсон сформулировали задачу о максимальном потоке в сети (мотивированную моделированием железнодорожного трафика) и доказали теорему о максимальном потоке и минимальном разрезе (max-flow min-cut theorem).
• Минимальное остовное дерево. Алгоритм Борувки (1926), затем алгоритмы Крускала (1956) и Прима (1957) обеспечили полиномиальные решения этой задачи.
• Кратчайший путь. Алгоритмы Шимбела (1951–1955, матричные методы), Беллмана—Форда и Дейкстры (1959, $O(n^2)$ для плотных графов) завершили формирование базового арсенала графовых алгоритмов.

После 1960 года: NP-полнота и полиэдральный подход

В 1965 году Дж. Эдмондс предложил алгоритм «бутонов» (blossom algorithm) для задачи общего паросочетания в графах, работающий за полиномиальное время, и развил полиэдральную комбинаторику для паросочетаний и матроидов. В 1971 году С. Кук ввёл концепцию NP-полноты; в 1972 году Р. Карп показал NP-полноту 21 задачи, включая TSP, задачу о клике и покрытии множествами, — тем самым установив фундаментальные границы вычислимости для широкого класса комбинаторных задач. В 1960 году Лэнд и Дойг предложили метод ветвей и границ; в 1987 году Падберг и Ринальди разработали метод ветвей и отсечений (branch-and-cut).

Сводная хронология

Дата	Событие
1784	Г. Монж формулирует задачу назначения в транспортном контексте
1912–1931	Фробениус, Кёниг, Эгервари: теория паросочетаний в двудольных графах; теорема Кёнига
1926	О. Борувка: алгоритм минимального остовного дерева
1930	А. Н. Толстой: эвристики для советских грузовых перевозок
1939	Л. В. Канторович: линейное программирование для транспортной задачи
1941	Ф. Хичкок: математическое описание транспортной задачи
1947	Дж. Данциг: симплекс-метод для линейного программирования
1954	Данциг, Фалкерсон, Джонсон: решение TSP для 49 городов методом cutting planes; Форд, Фалкерсон: задача о максимальном потоке
1955	Г. Кун: венгерский метод для задачи о назначении
1956	Крускал, Прим: алгоритмы минимального остовного дерева
1959	Э. Дейкстра: алгоритм кратчайшего пути
1965	Дж. Эдмондс: blossom algorithm для паросочетаний; полиэдральная комбинаторика
1971	С. Кук: NP-полнота
1972	Р. Карп: NP-полнота 21 комбинаторной задачи
1976	Н. Христофидес: 3/2-аппроксимация для метрической TSP
1987	Падберг, Ринальди: метод ветвей и отсечений (branch-and-cut)
1995	Гоэманс, Уильямсон: 0,878-аппроксимация для Max-Cut через SDP
2006	Concorde solver: оптимальное решение TSP для 85 900 городов (~136 CPU-лет)

Источники: Schrijver (2005); Korte, Vygen (2018); Applegate et al. (2006).

Теоретические основы

Формулировка как целочисленное линейное программирование

Задачи комбинаторной оптимизации часто формулируются как задачи ЦЛП:

$$\begin{gathered} \min \{c^{\mathrm{\top }}x\mid Ax\le b, \\ x\in \{0,1{\}}^n\} \end{gathered}$$

где $c$ — вектор коэффициентов целевой функции, $A$ — матрица ограничений, $b$ — вектор правых частей. Множество допустимых решений — вершины многогранника (полиэдра), представляющего выпуклую оболочку целочисленных точек.

Полиэдральная комбинаторика

Полиэдральная комбинаторика (polyhedral combinatorics) изучает свойства выпуклых оболочек допустимых решений — политопов. Для задач, матрица ограничений которых является тотально унимодулярной (totally unimodular), — в частности, для транспортных задач и задач двудольных паросочетаний — ЛП-релаксация автоматически даёт целочисленные решения в вершинах политопа. Это означает, что такие задачи решаются за полиномиальное время стандартными методами линейного программирования.

Теория матроидов

Матроиды (matroids) — абстрактные комбинаторные структуры, обобщающие понятие линейной независимости. Фундаментальный результат Радо (1957) и Эдмондса (1965) показывает, что жадный алгоритм оптимален для задач минимизации веса базиса матроида. Теория пересечения матроидов позволяет решать задачу о максимальном весе общего независимого множества двух матроидов. Матроидная структура объясняет, почему для минимального остовного дерева жадный подход (алгоритмы Крускала, Прима) даёт точное решение.

Субмодулярные функции

Субмодулярные функции — класс множественных функций с убывающей предельной отдачей. Они играют важную роль в задачах покрытия множества, максимизации влияния в социальных сетях и других приложениях. Для максимизации монотонной субмодулярной функции при кардинальном ограничении жадный алгоритм даёт $(1-1/e)$-аппроксимацию.

Теория сложности вычислений

Теория сложности классифицирует задачи комбинаторной оптимизации по вычислительной трудности:

• Класс P (полиномиально решаемые): максимальный поток, минимальное остовное дерево, паросочетания в графах, кратчайший путь.
• Класс NP-трудных задач: задача коммивояжёра (TSP), задача о рюкзаке (в общем виде), задача о покрытии множества, задача о раскраске графа, задача о клике, SAT.

Для NP-трудных задач оптимальное решение за полиномиальное время невозможно, если P ≠ NP. Вопрос о равенстве P и NP остаётся одной из главных открытых проблем теоретической информатики.

Методология

Методы комбинаторной оптимизации подразделяются на точные, приближённые, эвристические и современные подходы на стыке с машинным обучением.

Точные методы

Целочисленное линейное программирование (ЦЛП) — базовый формализм. Промышленные солверы (CPLEX, Gurobi) решают задачи с десятками и сотнями тысяч переменных, комбинируя несколько техник.

Метод ветвей и границ (branch-and-bound) — рекурсивное разбиение множества решений с отсечением ветвей, для которых нижняя оценка превышает текущий лучший результат. Предложен Лэндом и Дойгом (1960).

Метод ветвей и отсечений (branch-and-cut) — комбинация branch-and-bound с добавлением отсекающих плоскостей (cutting planes) для ужесточения ЛП-релаксации. Метод Падберга—Ринальди (1987) стал основой солвера Concorde для TSP.

Динамическое программирование — применяется к задачам с оптимальной подструктурой. Алгоритм Хелда—Карпа для TSP имеет сложность $O(n^2\cdot 2^n)$, что эффективнее полного перебора $O(n!)$, но остаётся экспоненциальным.

Генерация столбцов (column generation) — метод для задач с экспоненциальным числом переменных, при котором переменные генерируются итеративно через решение подзадачи ценообразования.

Приближённые алгоритмы

Приближённые алгоритмы обеспечивают гарантированный коэффициент отклонения от оптимума за полиномиальное время:

Алгоритм Христофидеса (1976) — для метрической задачи коммивояжёра даёт решение, стоимость которого не превышает $3/2$ от оптимальной. На протяжении десятилетий это лучший известный коэффициент для данной задачи.

Алгоритм Гоэманса—Уильямсона (1995) — для задачи Max-Cut даёт $0,878$-аппроксимацию через семидефинитное программирование (SDP-релаксацию).

Жадные алгоритмы — для задачи покрытия множества жадный подход даёт приближение $\ln n+1$, где $n$ — число элементов.

LP-округление — получение целочисленного решения из дробного оптимума ЛП-релаксации.

PTAS и FPTAS — полиномиальные схемы приближения. Полностью полиномиальная схема (FPTAS) для задачи о рюкзаке (Ибарра—Ким, 1975) даёт $(1-\epsilon )$-аппроксимацию за время $O(n^2/\epsilon )$.

Эвристики и метаэвристики

Для крупных экземпляров, где точные и приближённые методы неприменимы, используются эвристические подходы без строгих гарантий оптимальности:

• Имитация отжига (simulated annealing) — стохастический метод, моделирующий процесс охлаждения металла.
• Генетические алгоритмы — эволюционный поиск с мутациями, скрещиванием и отбором.
• Поиск с запретами (tabu search) — локальный поиск с памятью запрещённых ходов.
• Муравьиные колонии (ACO) — моделирование коллективного поведения муравьёв для построения решений.
• Локальный поиск — итеративное улучшение текущего решения за счёт малых модификаций.

Современные подходы: машинное обучение

С 2010-х годов активно развиваются подходы на стыке комбинаторной оптимизации и машинного обучения:

Графовые нейронные сети (GNN) с обучением с подкреплением (RL) автоматизируют конструктивные эвристики: модель S2V-DQN (Khalil et al., 2017) превосходит жадные подходы на задачах TSP и Max-Cut для графов до 500 вершин. Pointer networks (Bello et al., 2017) и последующие архитектуры (Kool et al., 2019) достигают отклонения менее 1 % от оптимума на TSPLIB при $n\le 1000$ за секунды на GPU.

Квантовые подходы. Алгоритм QAOA (Quantum Approximate Optimization Algorithm, Farhi et al., 2014) для Max-Cut на 3-регулярных графах при глубине $p=1$ обеспечивает гарантию приближения $\approx 0,6924$. Практическое преимущество квантовых подходов на текущих NISQ-устройствах остаётся дискуссионным.

Стохастические методы. Стохастическая двухэтапная оптимизация с семплированием (Sample Average Approximation, SAA) обеспечивает $(1+\gamma +6\epsilon )$-аппроксимацию с вероятностью $1-\delta$ при условии липшицевости и ограниченного полиэдра.

Ключевые результаты и бенчмарки

Результаты основаны на стандартных бенчмарках (TSPLIB, MIPLIB) и первичных публикациях.

Классические задачи: сложность и лучшие методы

Задача	Класс сложности	Лучший точный метод (сложность)	Лучшая аппроксимация	Примечание
Минимальное остовное дерево	P	Крускал / Прим ($O(m\log n)$)	Оптимально	Матроидная структура
Кратчайший путь	P	Дейкстра ($O(n^2)$)	Оптимально	Для неотрицательных весов
Максимальный поток	P	Форд—Фалкерсон ($O(V{E}^2)$)	Оптимально	Целочисленные ёмкости
Общее паросочетание	P	Blossom, Эдмондс ($O(n^3)$)	Оптимально	Полиэдральная комбинаторика
Задача о назначении	P	Венгерский метод ($O(n^3)$)	Оптимально	Тотальная унимодулярность
Метрическая TSP	NP-трудная	Branch-and-cut (Concorde)	$3/2$ (Христофидес, 1976)	APX-полная
Max-Cut	NP-трудная	Branch-and-cut	$0,878$ (Гоэманс—Уильямсон, 1995)	SDP-релаксация
Задача о рюкзаке	NP-трудная	Динамическое программирование	FPTAS	Псевдополиномиальная
Покрытие множества	NP-трудная	Branch-and-cut	$\ln n+1$ (жадный)	—

Источники: Korte, Vygen (2018); Papadimitriou, Steiglitz (1998); Applegate et al. (2006).

Эмпирические достижения

Задача / метод	Результат	Условия
TSP, Concorde solver	Оптимальное решение для 85 900 городов	TSPLIB, ~136 CPU-лет (2006)
TSP 49 городов (1954)	Оптимальный тур 12 345 миль	Данциг, Фалкерсон, Джонсон; cutting planes
TSP, RL-методы (Kool et al., 2019)	Отклонение < 1 % от оптимума	TSPLIB, $n\le 1000$, секунды на GPU
Max-Cut, GNN+RL (Khalil et al., 2017)	Отношение > 0,878	Графы до 500 вершин
Рюкзак, FPTAS	$(1-\epsilon )$-аппроксимация	Время $O(n^2/\epsilon )$

Источники: Applegate et al. (2006); Bello et al. (2017); Mazyavkina et al. (2021).

Применение

Комбинаторная оптимизация находит применение в широком спектре практических областей.

Логистика и транспорт

Маршрутизация транспортных средств (VRP), планирование авиаперевозок, проектирование сетей связи, оптимизация цепочек поставок. Задача VRP является обобщением TSP и относится к числу наиболее практически значимых NP-трудных задач.

Производство и планирование

Составление расписаний (job shop scheduling, nurse scheduling), оптимизация раскроя материалов, размещение оборудования. Эти задачи формулируются как комбинаторные и решаются методами ЦЛП и метаэвристиками.

Электроника и VLSI-дизайн

Размещение и трассировка компонентов в интегральных схемах (VLSI placement and routing) — классические задачи комбинаторной оптимизации, критичные для полупроводниковой промышленности.

Биология и синтетическая биология

Комбинаторная оптимизация применяется для проектирования комбинаторных библиотек ДНК, оптимизации метаболических путей и выбора ферментов. Например, задача выбора 3 ферментов из 1000 для максимизации выхода целевого метаболита в E. coli решается комбинаторными методами in silico с последующей экспериментальной верификацией. Навигация по ландшафту из $4^{30}\approx 10^{18}$ последовательностей ДНК — типичная задача комбинаторного дизайна экспериментов в биологии.

Медицина

Комбинаторные терапии препаратами (поиск оптимальных сочетаний лекарственных средств), планирование лучевой терапии (IMRT), оптимизация протоколов клинических испытаний.

Физика и химия

Поиск основного состояния модели Изинга (формулируется как задача Max-Cut), оптимизация молекулярных структур, задачи статистической физики.

Науки о Земле

Моделирование потоков флюидов в трещиноватых породах методами комбинаторной оптимизации для оценки flow-rates в резервуарах.

Ограничения и открытые проблемы

• NP-трудность. Большинство задач комбинаторной оптимизации NP-трудны, что приводит к экспоненциальному росту времени точного решения в худшем случае. Точные методы масштабируются плохо для $n>10^4-10^5$.
• Пределы аппроксимации. Для ряда задач доказаны нижние границы аппроксимации (inapproximability results): улучшение коэффициента невозможно, если P ≠ NP. Например, для задачи покрытия множества жадная аппроксимация $\ln n$ по существу оптимальна.
• Интегральный зазор (integrality gap). Разрыв между оптимумом ЛП-релаксации и оптимумом ЦЛП может быть велик, ограничивая эффективность методов LP-округления.
• Обобщаемость ML-методов. Нейросетевые подходы масштабируются лучше классических, но не гарантируют оптимальность и плохо обобщаются на экземпляры задач, существенно отличающиеся от обучающих.
• Стохастические и многокритериальные варианты. Включение неопределённости (стохастическая оптимизация) и нескольких целевых функций (многокритериальная оптимизация) существенно усложняет задачи.
• Открытая проблема P = NP. Центральный нерешённый вопрос теоретической информатики, имеющий прямые последствия для границ комбинаторной оптимизации.

Этические, правовые и регуляторные аспекты

В приложениях комбинаторной оптимизации к медицине и распределению ресурсов возникают вопросы справедливости (fairness) и воспроизводимости результатов. Стандарты PRISMA для систематических обзоров и CONSORT для клинических испытаний применяются при оценке оптимизационных алгоритмов, используемых в медицинском контексте. Регуляторные органы (FDA, EMA) требуют валидации моделей при клиническом использовании. В области ML-подходов к комбинаторной оптимизации обсуждаются вопросы bias в обучающих данных и экологические последствия энергоёмких вычислений. Стандарты ISO/IEC применяются для алгоритмов, используемых в критических системах.

Перспективы и направления исследований

Согласно обзорам (Bengio et al., 2021; Le, 2024), основные направления развития включают:

• Гибридные подходы, сочетающие точные солверы с машинным обучением (learning to optimize): GNN для графовых структур и RL для последовательного построения решений.
• Стохастическую и корреляционно-робастную оптимизацию (boost-and-sample, SAA).
• Квантово-классические гибриды (QAOA, квантовый отжиг, Ising-машины), хотя практическое преимущество на текущем оборудовании остаётся дискуссионным.
• Фокус на крупных реальных экземплярах, многокритериальной оптимизации и explainable AI в комбинаторной оптимизации.
• Мат-эвристики — гибриды математического программирования и метаэвристик для промышленных задач.

См. также

• Целочисленное программирование
• Исследование операций

Литература

• Schrijver A. On the history of combinatorial optimization (till 1960). In: Aardal K., Nemhauser G.L., Weismantel R. (eds.). Handbook of Discrete Optimization. Elsevier, 2005. https://homepages.cwi.nl/~lex/files/histco.pdf
• Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms. 5th ed. Springer, 2018. DOI: 10.1007/978-3-662-56039-6.
• Papadimitriou C.H., Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. Dover, 1998.
• Dantzig G.B., Fulkerson D.R., Johnson S.M. Solution of a Large-Scale Traveling-Salesman Problem. Operations Research, 1954, vol. 2, pp. 393–410.
• Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, CMU, 1976.
• Applegate D.L. et al. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
• Karp R.M. Reducibility among combinatorial problems. In: Complexity of Computer Computations. Plenum Press, 1972.
• Mazyavkina N. et al. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 2021, vol. 134, 105400. arXiv:2003.03600.
• Peng Y. et al. Graph learning for combinatorial optimization: A survey of state-of-the-art. Data Science and Engineering, 2021, vol. 6, pp. 119–141.
• Naseri G. et al. Application of combinatorial optimization strategies in synthetic biology. Nature Communications, 2020, vol. 11, 2449.
• Le P. A survey on combinatorial optimization. arXiv:2409.00075, 2024.
• Farhi E. et al. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028, 2014.
• Bello I. et al. Neural combinatorial optimization with reinforcement learning. arXiv:1611.09940, 2016.
• Hobé A. et al. Estimating fluid flow rates through fracture networks using combinatorial optimization. Advances in Water Resources, 2018, vol. 122, pp. 85–97.
• Handbook of Combinatorial Optimization (eds. Du D.-Z., Pardalos P.M.). Springer, multiple volumes, 1998–2013.

Ссылки

• https://homepages.cwi.nl/~lex/files/histco.pdf — Schrijver, история комбинаторной оптимизации
• https://www.math.uwaterloo.ca/tsp/concorde.html — Concorde TSP Solver
• https://arxiv.org/abs/2409.00075 — Le, обзор комбинаторной оптимизации (2024)
• https://arxiv.org/abs/2003.03600 — Mazyavkina et al., RL для комбинаторной оптимизации (2021)