Комбинаторная оптимизация
Комбинато́рная оптимиза́ция (дискретная оптимизация), раздел математической оптимизации, изучающий задачи о нахождении оптимального объекта из конечного множества объектов, где набор возможных решений является дискретным или может быть сведён к дискретному набору. Типичными задачами комбинаторной оптимизации являются задача коммивояжёра (англ. Traveling Salesman Problem), задача о минимальном остовном дереве (англ. Minimum Spanning Tree) и задача о рюкзаке (англ. Knapsack Problem) (Ахо. 1979[1]; Гэри. 1982[2]; Schrijver. 2002[3]; Кузюрин. 2007[4]).
Задачи оптимизации можно разделить на два класса. К первому классу относятся задачи, решаемые за полиномиальное время относительно длины описания задачи. В частности, к таким задачам относятся те, которые можно сформулировать как задачу линейного программирования. В этом случае число допустимых значений, относительно которых находится оптимум (максимум или минимум) целевой функции, бесконечно. Однако стандартные методы решения этой задачи приводят к выбору вариантов из конечного множества. Во втором классе находятся задачи, в которых возможные допустимые варианты составляют конечное множество. В этом случае задача может быть решена прямым перебором всех возможных вариантов. Однако количество таких вариантов может быть намного больше, чем длина описания задачи (например, задача коммивояжёра). В большинстве случаев такие задачи сводятся к задаче целочисленного программирования. Для задач из второго класса существование полиномиального алгоритма составляет открытую проблему. При этом известно, что наличие полиномиального алгоритма для любой из задач второго класса влечёт за собой существование подобного алгоритма сразу для всех задач из второго класса.
Интерес к задачам комбинаторной оптимизации обусловлен тем, что тысячи прикладных задач, с которыми мы сталкиваемся в жизни, могут быть сформулированы в виде абстрактных комбинаторных задач оптимизации (Корте. 2015[5]). Комбинаторная оптимизация используется при определении оптимальной сети маршрутов авиакомпаний, при определении, какая машина из парка такси подберёт пассажиров; для определения оптимального пути доставки грузов; при решении задач об упаковке в контейнеры; о размещении предприятий, и т. д.
Во многих подобных задачах, таких, как упомянутые выше, исчерпывающий поиск за полиномиальное от длины описания задачи время невыполним, и поэтому приходится прибегать к специализированным алгоритмам, которые быстро исключают большие части пространства поиска, к алгоритмам аппроксимации с гарантированной точностью, а также к вероятностным алгоритмам (Кузюрин. 2007[6]).
Отметим, что ряд авторов (например, Discrete optimization II. 1979[7]) выделяют три раздела дискретной оптимизации: комбинаторная оптимизация, целочисленное программирование и оптимизация с произвольными ограничениями.
Примечания
Литература
- Discrete optimization II : proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium, co-sponsored by IBM Canada and SIAM, Banff, Alta. and Vancouver, B. C., Canada, August 1977 / ed. by P. L. Hammer [et al.]. – New York : North-Holland Pub., 1979. – (Annals of discrete mathematics ; 5).
- Ахо А. В. Построение и анализ вычислительных алгоритмов / А. Ахо, Д. Хопкрофт, Д. Ульман ; пер. с англ. А. О. Слисенко. – Москва : Мир, 1979.
- Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон ; пер. с англ. Е. В. Левнера, М. А. Фрумкина. – Москва : Мир, 1982.
- Schrijver A. Combinatorial Optimization. – Berlin : Springer, 2002. – 3 vol.
- Кузюрин Н. Н. Эффективные алгоритмы и сложность вычислений : учебное пособие / Н. Н. Кузюрин, С. А. Фомин. – Москва : МФТИ, 2007.
- Корте Б. Комбинаторная оптимизация : теория и алгоритмы / Б. Корте, Й. Фиген ; пер. с англ. М. А. Бабенко. – Москва : Издательство МЦНМО, 2015.