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

Комбинаторная оптимизация — это раздел математического программирования и дискретной математики, посвящённый поиску оптимального (наилучшего по заданному критерию) решения среди конечного, но, как правило, огромного множества допустимых вариантов, имеющих комбинаторную природу. Задачи комбинаторной оптимизации возникают при необходимости выбора наилучшего набора объектов, их упорядочивания, разбиения на группы или назначения, при этом число возможных вариантов растёт экспоненциально с увеличением размера задачи (например, факториал или 2 в степени n). Ключевая особенность — дискретность переменных: решения принимаются не из непрерывного диапазона, а из конечного множества целых чисел, булевых значений или перестановок.

История

Истоки комбинаторной оптимизации лежат в классических задачах, сформулированных в XVIII–XIX веках: задача о коммивояжёре (Уильям Гамильтон, 1859), задача о назначениях, задача о кратчайшем пути. Однако как самостоятельная дисциплина она оформилась в середине XX века, в первую очередь в связи с развитием вычислительной техники и необходимостью решения практических задач логистики, планирования и проектирования. В 1940–1950-х годах были разработаны первые формальные методы: симплекс-метод (Джордж Данциг, 1947) для линейного программирования, который лёг в основу многих точных алгоритмов, и метод ветвей и границ (А. Лэнд и А. Дойг, 1960). В 1970-х годах, с появлением теории NP-полноты (Стивен Кук, Ричард Карп), стало ясно, что многие задачи комбинаторной оптимизации являются вычислительно сложными, что стимулировало разработку эвристических и приближённых методов. В 1980–1990-х годах широкое распространение получили метаэвристики (генетические алгоритмы, имитация отжига, муравьиные алгоритмы), а также методы целочисленного линейного программирования.

Классификация задач

Задачи комбинаторной оптимизации можно классифицировать по нескольким признакам: по типу переменных, по структуре ограничений и по целевой функции.

По типу переменных

• Булевы задачи — переменные принимают значения 0 или 1 (например, задача о рюкзаке, задача о покрытии множества).
• Задачи на перестановках — решение представляет собой перестановку элементов (например, задача коммивояжёра, задача о назначениях).
• Задачи на разбиениях — требуется разбить множество объектов на группы (например, задача о раскраске графа, задача кластеризации).
• Задачи на целочисленных решётках — переменные являются целыми неотрицательными числами (например, задача о целочисленном потоке).

По структуре ограничений

• Линейные задачи — целевая функция и ограничения линейны (например, задача о рюкзаке, задача о назначениях).
• Нелинейные задачи — хотя бы одно из выражений нелинейно (например, задача квадратичного назначения).
• Сетевые задачи — ограничения заданы в виде графа (например, задача о кратчайшем пути, задача о максимальном потоке, задача о минимальном остовном дереве).

По вычислительной сложности

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

Методы решения

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

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

Точные методы гарантируют нахождение оптимального решения, но их время работы может быть экспоненциальным.

• Метод ветвей и границ — рекурсивный перебор вариантов с отсечением заведомо неоптимальных подмножеств решений на основе оценки нижней (для задачи минимизации) границы.
• Метод отсечений (Гомори) — последовательное добавление линейных неравенств, отсекающих нецелочисленные решения, до получения целочисленного оптимума.
• Динамическое программирование — разбиение задачи на подзадачи и сохранение их решений; эффективно для задач с ограниченным пространством состояний (например, задача о рюкзаке с целыми весами).
• Целочисленное линейное программирование — формулировка задачи в виде системы линейных неравенств с целочисленными переменными и решение с помощью симплекс-метода и методов отсечения (например, пакет CPLEX, Gurobi).

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

Приближённые методы (аппроксимационные алгоритмы) дают решение, гарантированно отличающееся от оптимального не более чем в заданное число раз (коэффициент аппроксимации).

• Жадные алгоритмы — последовательный выбор локально наилучшего варианта; для некоторых задач (например, минимальное остовное дерево) дают точное решение, для других — приближённое.
• Алгоритмы с гарантированной точностью — например, для задачи о рюкзаке существует псевдополиномиальный алгоритм, который может быть преобразован в полностью полиномиальную приближённую схему (FPTAS).

Эвристические и метаэвристические методы

Эти методы не гарантируют оптимальности, но часто позволяют найти хорошее решение за приемлемое время.

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

Применение

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

• Логистика и транспорт — маршрутизация транспорта (задача коммивояжёра, задача маршрутизации транспортных средств), планирование поставок, оптимизация складских запасов.
• Производство и планирование — составление расписаний (job shop scheduling, flow shop scheduling), раскрой материалов, оптимизация производственных линий.
• Телекоммуникации и сети — проектирование сетей (задача Штейнера, задача о минимальном остовном дереве), распределение частот, маршрутизация пакетов.
• Информатика и искусственный интеллект — обучение деревьев решений, выбор признаков (feature selection), кластеризация, оптимизация нейронных сетей (например, выбор архитектуры).
• Финансы — портфельная оптимизация (выбор акций с ограничениями), задача о назначении активов, оптимизация торговых стратегий.
• Биоинформатика — выравнивание последовательностей ДНК, сборка генома, предсказание структуры белков.
• Энергетика — оптимизация режимов работы электростанций, планирование загрузки энергосетей, размещение возобновляемых источников энергии.

Примеры классических задач

Задача коммивояжёра (TSP)

Дано множество городов и расстояния между ними. Требуется найти кратчайший замкнутый маршрут, посещающий каждый город ровно один раз. Задача NP-трудна, но для малых размеров (до нескольких тысяч городов) решается точными методами, а для больших — приближёнными (например, эвристика Лин-Кернигана).

Задача о рюкзаке (Knapsack)

Дано множество предметов с весом и стоимостью. Требуется выбрать подмножество предметов так, чтобы суммарный вес не превышал вместимость рюкзака, а суммарная стоимость была максимальной. Является NP-трудной, но существует псевдополиномиальный алгоритм динамического программирования.

Задача о назначениях (Assignment Problem)

Дана матрица затрат на выполнение работниками работ. Требуется назначить каждого работника на одну работу так, чтобы суммарные затраты были минимальны. Решается за полиномиальное время венгерским алгоритмом.

Задача о кратчайшем пути (Shortest Path)

В графе с рёбрами, имеющими вес, требуется найти путь между двумя вершинами с минимальным суммарным весом. Решается алгоритмом Дейкстры (для неотрицательных весов) или алгоритмом Беллмана-Форда (для графов с отрицательными весами).

Интересные факты

• Задача коммивояжёра является одной из самых изученных NP-трудных задач. Для неё разработаны точные алгоритмы, способные решать экземпляры с десятками тысяч городов (например, рекорд 2006 года — 85 900 городов).
• В 1972 году Ричард Карп доказал NP-полноту 21 классической задачи комбинаторной оптимизации, включая задачу о рюкзаке, задачу о вершинном покрытии и задачу о выполнимости.
• Метод ветвей и границ лежит в основе многих современных решателей (solvers) для целочисленного программирования, таких как CPLEX, Gurobi и SCIP.
• В России и СССР значительный вклад в развитие комбинаторной оптимизации внесли учёные: Л. В. Канторович (линейное программирование, транспортная задача), В. С. Михалевич (методы ветвей и границ), А. А. Корбут (дискретная оптимизация).

Критика и ограничения

Основная критика комбинаторной оптимизации связана с вычислительной сложностью: для многих практически важных задач точное решение может быть получено только для малых размеров, а для больших — требует неприемлемого времени или ресурсов. Эвристические методы, хотя и дают приемлемые решения, не гарантируют их качества и могут сильно зависеть от начальных параметров. Кроме того, модели комбинаторной оптимизации часто упрощают реальные условия (например, игнорируют неопределённость, динамику или стохастичность), что снижает их практическую ценность. В последние годы активно развиваются методы робастной и стохастической оптимизации, а также гибридные подходы, сочетающие точные и эвристические алгоритмы.

Источники

• Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: алгоритмы и сложность. — М.: Мир, 1985.
• Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. — М.: Наука, 1969.
• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.
• Шкловер В. И. Комбинаторная оптимизация: теория и алгоритмы. — М.: МЦНМО, 2018.
• Cook W. J., Cunningham W. H., Pulleyblank W. R., Schrijver A. Combinatorial Optimization. — Wiley, 1998.