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

Подобласть математической оптимизации

Минимальное остовное дерево взвешенного планарного графа . Поиск минимального остовного дерева — распространенная проблема, связанная с комбинаторной оптимизацией.

Комбинаторная оптимизация — это подобласть математической оптимизации , которая состоит из поиска оптимального объекта из конечного набора объектов, ^[1] где множество возможных решений дискретно или может быть сведено к дискретному множеству. Типичными задачами комбинаторной оптимизации являются задача коммивояжера («TSP»), задача минимального связующего дерева («MST») и задача о рюкзаке . Во многих таких задачах, например упомянутых ранее, исчерпывающий поиск неразрешим, поэтому вместо этого приходится прибегать к специализированным алгоритмам, которые быстро исключают большие части пространства поиска, или к алгоритмам аппроксимации.

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

В некоторой исследовательской литературе ^[2] дискретная оптимизация рассматривается как состоящая из целочисленного программирования вместе с комбинаторной оптимизацией (которая, в свою очередь, состоит из задач оптимизации , связанных со структурами графов ), хотя все эти темы тесно переплетаются в научной литературе. ^{[ нужны разъяснения ]}

Приложения

Приложения комбинаторной оптимизации включают, помимо прочего:

• Логистика ^[3]
• Оптимизация цепочки поставок ^[4]
• Развитие лучшей сети авиалиний по направлениям и направлениям
• Решение о том, какие такси в парке маршрутизировать для получения платы за проезд
• Определение оптимального способа доставки посылок
• Оптимальное распределение рабочих мест между людьми
• Проектирование водопроводных сетей
• Проблемы науки о Земле (например, дебит коллектора ) ^[5]

Методы

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

Для NP-полных задач дискретной оптимизации текущая исследовательская литература включает следующие темы:

• точно решаемые за полиномиальное время особые случаи рассматриваемой проблемы (например, решаемые задачи с фиксированным параметром )
• алгоритмы, которые хорошо работают в «случайных» случаях (например, в задаче коммивояжера )
• алгоритмы аппроксимации , которые работают за полиномиальное время и находят решение, близкое к оптимальному
• параметризованные алгоритмы аппроксимации , которые работают за время FPT и находят решение, близкое к оптимальному
• решение реальных примеров, которые возникают на практике и не обязательно демонстрируют поведение наихудшего случая в NP-полных задачах (например, реальные экземпляры TSP с десятками тысяч узлов ^[6] ).

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

Для каждой задачи комбинаторной оптимизации существует соответствующая проблема принятия решения , которая спрашивает, существует ли допустимое решение для некоторой конкретной меры . Например, если есть граф , который содержит вершины и , задача оптимизации может заключаться в том, чтобы «найти путь от до , который использует наименьшее количество ребер». Ответ этой задачи может быть, скажем, 4. Соответствующей проблемой решения будет вопрос: «Существует ли путь от к , который использует 10 или меньше ребер?» На эту проблему можно ответить простым «да» или «нет». ${\displaystyle m_{0}}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$

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

Задача оптимизации NP

Задача NP-оптимизации (NPO) — это задача комбинаторной оптимизации со следующими дополнительными условиями. ^[9] Обратите внимание, что упомянутые ниже полиномы являются функциями размера входных данных соответствующих функций, а не размера некоторого неявного набора входных экземпляров.

• размер каждого допустимого решения полиномиально ограничен размером данного экземпляра , ${\displaystyle y\in f(x)}$ ${\displaystyle x}$
• языки и могут быть распознаны за полиномиальное время , и ${\displaystyle \{\,x\,\mid \,x\in I\,\}}$ ${\displaystyle \{\,(x,y)\,\mid \,y\in f(x)\,\}}$
• ${\displaystyle m}$вычислима за полиномиальное время .

Это означает, что соответствующая проблема решения находится в NP . В информатике интересные задачи оптимизации обычно обладают вышеуказанными свойствами и, следовательно, являются задачами НКО. Задача дополнительно называется задачей P-оптимизации (ПО), если существует алгоритм, который находит оптимальные решения за полиномиальное время. Часто, имея дело с классом NPO, интересуются задачами оптимизации, для которых варианты решения являются NP-полными . Обратите внимание, что отношения жесткости всегда относятся к некоторому уменьшению. Из-за связи между алгоритмами аппроксимации и задачами вычислительной оптимизации, сокращения, которые в некотором отношении сохраняют аппроксимацию, являются для этого предмета более предпочтительными, чем обычные сокращения Тьюринга и Карпа . Примером такого сокращения может быть L-редукция . По этой причине задачи оптимизации с NP-полными версиями решения не обязательно называются NPO-полными. ^[10]

НКО подразделяются на следующие подклассы по степени их аппроксимируемости: ^[9]

• NPO(I) : Равно FPTAS . Содержит задачу о рюкзаке .
• NPO(II) : Равен PTAS . Содержит задачу планирования Makespan .
• NPO(III) : :Класс задач NPO, которые имеют алгоритмы с полиномиальным временем, которые вычисляют решения со стоимостью, не превышающей в c раз оптимальную стоимость (для задач минимизации) или стоимость, по крайней мере , оптимальную стоимость (для задач максимизации). В книге Хромковича ^{[ какой? ]} , из этого класса исключаются все NPO(II)-задачи, за исключением случая P=NP. Без исключений равно APX. Содержит MAX-SAT и метрику TSP . ${\displaystyle 1/c}$
• NPO(IV) : :Класс задач NPO с алгоритмами с полиномиальным временем, аппроксимирующими оптимальное решение соотношением, полиномиальным по отношению к логарифму размера входных данных. В книге Хромковича из этого класса исключены все NPO(III)-задачи, за исключением случаев, когда P=NP. Содержит проблему с установленной обложкой .
• NPO(V) : :Класс задач NPO с алгоритмами с полиномиальным временем, аппроксимирующими оптимальное решение отношением, ограниченным некоторой функцией от n. В книге Хромковича из этого класса исключены все NPO(IV)-задачи, за исключением случаев, когда P=NP. Содержит задачу TSP и клики .

Задача NPO называется полиномиально ограниченной (PB), если для каждого экземпляра и для каждого решения мера ограничена полиномиальной функцией размера . Класс NPOPB — это класс задач NPO, которые полиномиально ограничены. ${\displaystyle x}$ ${\displaystyle y\in f(x)}$ ${\displaystyle m(x,y)}$ ${\displaystyle x}$

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

Оптимальный тур коммивояжера по 15 крупнейшим городам Германии . Это самый короткий из 43 589 145 600 ^[11] возможных туров, в рамках которых каждый город посещается ровно один раз.

• Проблема с назначением
• Проблема с упаковкой контейнера
• Проблема закрытия
• Проблема удовлетворения ограничений
• Проблема с обрезкой материала
• Задача о доминирующем множестве
• Целочисленное программирование
• График работы цеха
• Задача о рюкзаке
• Минимальные соответствующие переменные в линейной системе
• Минимальное связующее дерево
• Проблема с расписанием работы медсестры
• Установить проблему с обложкой
• Планирование талантов
• Задача коммивояжера
• Проблема с переоформлением автомобиля
• Проблема с маршрутом автомобиля
• Проблема с целеуказанием оружия

Смотрите также

• Составной граф ограничений

Примечания

1. Шрийвер 2003, с. 1.
2. Дискретная оптимизация. Эльзевир. Архивировано из оригинала 5 июля 2013 г. Проверено 8 июня 2009 г.
3. Сбихи, Абделькадер; Эглезе, Ричард В. (2007). «Комбинаторная оптимизация и зеленая логистика» (PDF) . 4ИЛИ . 5 (2): 99–116. дои : 10.1007/s10288-007-0047-3. S2CID  207070217. Архивировано (PDF) из оригинала 26 декабря 2019 г. Проверено 26 декабря 2019 г.
4. Эскандарпур, Маджид; Дежакс, Пьер; Мемчик, Джо; Петон, Оливье (2015). «Проектирование устойчивой сети цепочки поставок: обзор, ориентированный на оптимизацию» (PDF) . Омега . 54 : 11–32. дои : 10.1016/j.omega.2015.01.006. Архивировано (PDF) из оригинала 26 декабря 2019 г. Проверено 26 декабря 2019 г.
5. Хобе, Алекс; Фоглер, Дэниел; Сейболд, Мартин П.; Эбигбо, Анози; Сеттгаст, Рэндольф Р.; Саар, Мартин О. (2018). «Оценка скорости потока жидкости через сеть трещин с использованием комбинаторной оптимизации». Достижения в области водных ресурсов . 122 : 85–97. arXiv : 1801.08321 . Бибкод : 2018AdWR..122...85H. doi :10.1016/j.advwatres.2018.10.002. S2CID  119476042. Архивировано из оригинала 21 августа 2020 г. Проверено 16 сентября 2020 г.
6. Кук 2016.
7. «Приближение-TSP» (PDF) . Архивировано (PDF) из оригинала 1 марта 2022 г. Проверено 17 февраля 2022 г.
8. Аузиелло, Джорджо; и другие. (2003), Сложность и аппроксимация (исправленная редакция), Springer, ISBN 978-3-540-65431-5
9. Хромкович, Юрай (2002), Алгоритмика для сложных задач , Тексты по теоретической информатике (2-е изд.), Springer, ISBN 978-3-540-44134-2
10. Канн, Вигго (1992), Об аппроксимируемости задач NP-полной оптимизации , Королевский технологический институт, Швеция, ISBN 91-7170-082-Х
11. Возьмите один город и заберите все возможные приказы остальных 14 городов. Затем разделите на два, потому что не имеет значения, в каком направлении во времени они следуют друг за другом: 14!/2 = 43 589 145 600.

Рекомендации

• Бизли, Дж. Э. «Целочисленное программирование» (конспект лекций).

• Кук, Уильям Дж .; Каннингем, Уильям Х.; Пуллибланк, Уильям Р .; Шрийвер, Александр (1997). Комбинаторная оптимизация . Уайли. ISBN 0-471-55894-Х.

• Кук, Уильям (2016). «Оптимальные туры ТСП». Университет Ватерлоо . (Информация о крупнейших на сегодняшний день случаях TSP.)

• Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Вегингер, Герхард (ред.). «Сборник задач оптимизации NP». (Это постоянно обновляемый каталог результатов аппроксимации задач NP-оптимизации.)

• Дас, Арнаб; Чакрабарти, Бикас К. , ред. (2005). Квантовый отжиг и связанные с ним методы оптимизации . Конспект лекций по физике. Том. 679. Спрингер. Бибкод : 2005qnro.book.....D. ISBN 978-3-540-27987-7.

• Дас, Арнаб; Чакрабарти, Бикас К. (2008). «Коллоквиум: квантовый отжиг и аналоговые квантовые вычисления». Преподобный Мод. Физ . 80 (3): 1061. arXiv : 0801.2193 . Бибкод : 2008RvMP...80.1061D. CiteSeerX  10.1.1.563.9990 . doi : 10.1103/RevModPhys.80.1061. S2CID  14255125.

• Лоулер, Юджин (2001). Комбинаторная оптимизация: сети и матроиды . Дувр. ISBN 0-486-41453-1.

• Ли, Джон (2004). Первый курс комбинаторной оптимизации. Издательство Кембриджского университета. ISBN 0-521-01012-8.

• Пападимитриу, Христос Х.; Стейглиц, Кеннет (июль 1998 г.). Комбинаторная оптимизация: алгоритмы и сложность . Дувр. ISBN 0-486-40258-4.

• Шрийвер, Александр (2003). Комбинаторная оптимизация: многогранники и эффективность. Алгоритмы и комбинаторика. Том. 24. Спрингер. ISBN 9783540443896.

• Шрийвер, Александр (2005). «К истории комбинаторной оптимизации (до 1960 г.)» (PDF) . В Аардале, К .; Немхаузер, Г.Л.; Вейсмантель, Р. (ред.). Справочник по дискретной оптимизации . Эльзевир. стр. 1–68.

• Шрийвер, Александр (1 февраля 2006 г.). Курс комбинаторной оптимизации (PDF) .

• Сиерксма, Жерар; Гош, Диптеш (2010). Сети в действии; Текстовые и компьютерные упражнения по оптимизации сети . Спрингер. ISBN 978-1-4419-5512-8.

• Жерар Сиерксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика . ЦРК Пресс. ISBN 978-1-498-71016-9.

• Пинтеа, CM. (2014). Достижения в области биовычислений для решения задач комбинаторной оптимизации. Справочная библиотека интеллектуальных систем. Спрингер. ISBN 978-3-642-40178-7.

Внешние ссылки

• Журнал комбинаторной оптимизации
• Семинар по комбинаторной оптимизации Aussois
• Платформа комбинаторной оптимизации Java (с открытым исходным кодом)
• Почему сложно планировать людей?
• Классы сложности задач оптимизации / Стефан Кугеле