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

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

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

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

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

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

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

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

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

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

• 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

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