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

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

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

Приложения

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

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

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

Методы

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

Задачи комбинаторной оптимизации можно рассматривать как поиск лучшего элемента в некотором дискретном множестве, поэтому, в принципе, могут быть использованы любые алгоритмы поиска или метаэвристические алгоритмы. Однако общие алгоритмы поиска не гарантируют ни оптимального решения, ни быстрого решения (за полиномиальное время). Поскольку некоторые задачи дискретной оптимизации 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