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

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

Приложения

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

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

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

Методы

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

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