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

Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности. Комбинаторная оптимизация заключается в поиске оптимального объекта в конечном множестве объектов, чем очень похожа на дискретное программирование. Некоторые источники под дискретным программированием понимают целочисленное программирование, противопоставляя ему комбинаторную оптимизацию, имеющую дело с графами, матроидами и похожими структурами. Однако оба термина очень близко связаны и в литературе часто переплетаются. Комбинаторная оптимизация часто сводится к определению эффективного распределения ресурсов, используемых для поиска оптимального решения. Подробный рассказ от - tut.w0.am Комбинаторная оптимизация: Теория, методы и практическое применение Введение Комбинаторная оптимизация (КО) — это область дискретной математики, находящаяся на стыке операционного исчисления, теории графов и теоретической информатики. Её основная цель — нахождение экстремума (минимума или максимума) целевой функции на конечном, но дискретном множестве допустимых решений. В отличие от непрерывной оптимизации, где переменные могут принимать любые значения из интервала, в КО мы имеем дело с объектами, которые можно пересчитать: путями в графе, комбинациями предметов в контейнере или последовательностями операций. 1. Фундаментальная сложность: Почему это трудно? Центральным понятием в КО является комбинаторный взрыв. Классы сложности Большинство интересных для практики задач КО относятся к классу NP-трудных. Это означает, что на данный момент не существует алгоритма, способного найти точное решение за полиномиальное время (быстро). Пример с перестановками: Если у вас есть 20 объектов, которые нужно расставить в ряд, количество комбинаций составит

(факториал), что примерно равно 

. Даже мощный суперкомпьютер будет перебирать их десятилетиями. Проблема P vs NP Вопрос о том, можно ли эффективно решать такие задачи, является одной из «проблем тысячелетия». Пока математики ищут ответ, инженеры используют методы, позволяющие обходить это ограничение. 2. Канонические задачи Для глубокого понимания темы важно рассмотреть «золотой фонд» задач КО: Задача коммивояжера (TSP): Поиск кратчайшего пути, проходящего через все заданные города ровно по одному разу с возвратом в исходную точку. Это фундамент всей логистики. Задача о рюкзаке (Knapsack Problem): Выбор подмножества предметов с заданными весами и стоимостями так, чтобы максимизировать общую ценность при ограничении по весу. Задача о раскраске графа: Минимальное количество цветов, необходимое для раскраски вершин так, чтобы никакие две смежные вершины не имели один цвет (применяется при создании расписаний и проектировании микросхем). Задача о максимальном потоке: Определение максимального объема «груза», который можно передать через сеть (трубопровод, интернет-трафик) с учетом пропускной способности ребер. 3. Методология решения Методы делятся на три большие группы: А. Точные алгоритмы Используются, когда критически важно найти именно глобальный минимум. Метод ветвей и границ (Branch and Bound): Мы систематически перебираем подмножества решений, отсекая («срезая») те ветви дерева поиска, которые заведомо не могут содержать лучшего результата. Динамическое программирование: Разбиение сложной задачи на более мелкие перекрывающиеся подзадачи. Линейное целочисленное программирование: Описание задачи в виде системы линейных неравенств, где переменные должны быть целыми числами. Б. Приближенные методы и эвристики Когда задача слишком велика, мы соглашаемся на «хорошее» решение вместо «идеального». Жадные алгоритмы: На каждом шаге выбирается локально лучшее решение (например, идти в ближайший еще не посещенный город). Локальный поиск: Постепенное улучшение текущего решения путем небольших правок («мутаций»). В. Метаэвристики (Природные алгоритмы) Это сложные стратегии, имитирующие природные процессы: Генетические алгоритмы: Моделируют эволюцию (скрещивание, мутация, отбор). Муравьиные алгоритмы: Имитируют поиск кратчайшего пути муравьями по феромонному следу. Имитация отжига: Моделирует процесс остывания металла, позволяя алгоритму на ранних этапах «выпрыгивать» из локальных ловушек. 4. Сферы применения в современном мире Сегодня КО управляет глобальными процессами «под капотом» цифровой экономики: Логистика 4.0: Оптимизация маршрутов курьеров (Uber, Amazon, Wildberries). Экономия 1% пути в масштабах компании означает миллионы долларов прибыли. Финансы: Балансировка инвестиционных портфелей, где нужно выбрать лучший набор активов при заданном риске. Проектирование систем: Трассировка дорожек на печатных платах процессоров (миллиарды транзисторов должны быть соединены оптимально). Энергетика: Управление Smart Grid — распределение нагрузки в электросетях в реальном времени. 5. Будущее: Нейросети и Кванты Neural Combinatorial Optimization: Использование глубокого обучения (RL — обучение с подкреплением) для того, чтобы нейросеть сама «догадывалась», как решать задачу коммивояжера, обучаясь на опыте. Квантовые вычисления: Квантовые алгоритмы (например, алгоритм Гровера или квантовый отжиг) теоретически могут совершить прорыв в скорости решения NP-трудных задач, сокращая время поиска с миллиардов лет до минут. Заключение Комбинаторная оптимизация — это мост между теоретической математикой и эффективностью реального бизнеса. В мире ограниченных ресурсов умение выбирать наилучший вариант из почти бесконечного множества — это не просто научная задача, а залог выживания и развития цивилизации.

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

Приложения

Комбинаторная оптимизация используется при:

• определении оптимальной сети аэрофлота;
• определении, какая машина из парка такси подберёт пассажиров;
• определении оптимального пути доставки посылок;
• определении правильных атрибутов перед тестированием концепций.

Однако этими примерами приложение комбинаторной оптимизации не ограничивается.

Методы

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

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

Конкретные проблемы

Оптимальный путь коммивояжёра по 15 крупнейшим городам Германии. Это кратчайший путь из 14!/2 (43 589 145 600) возможных

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

См. также

• Математическое программирование

Литература

• Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency (англ.). — Springer. — Vol. 24. — (Algorithms and Combinatorics).
• Glover F., Kochenberger G. A. Handbook of Metaheuristics. New York: Kluwer Academic Publishers, 2003. 560 p.
• Ватутин Э. И., Титов В. С., Емельянов С. Г. Основы дискретной комбинаторной оптимизации. М.: Аргамак-Медиа, 2016. 270 с. ISBN 978-5-00-024057-1
• Карпенко А. П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: МГТУ им. Н. Э. Баумана, 2014. 446 с. ISBN 978-5-7038-3949-2