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

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

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

Приложения

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

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

Методы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

^ Писатель 2003 , с. 1.
^ Сбихи, Абделькадер; Эглезе, Ричард В. (2007). «Комбинаторная оптимизация и зеленая логистика» (PDF) . 4ИЛИ . 5 (2): 99–116. дои : 10.1007/s10288-007-0047-3 . S2CID 207070217 . Архивировано (PDF) из оригинала 26 декабря 2019 г. Проверено 26 декабря 2019 г.
^ Эскандарпур, Маджид; Дежакс, Пьер; Мемчик, Джо; Петон, Оливье (2015). «Проектирование устойчивой сети цепочки поставок: обзор, ориентированный на оптимизацию» (PDF) . Омега . 54 : 11–32. дои : 10.1016/j.omega.2015.01.006 . Архивировано (PDF) из оригинала 26 декабря 2019 г. Проверено 26 декабря 2019 г.
^ Хобе, Алекс; Фоглер, Дэниел; Сейболд, Мартин П.; Эбигбо, Анози; Сеттгаст, Рэндольф Р.; Саар, Мартин О. (2018). «Оценка скорости потока жидкости через сеть трещин с использованием комбинаторной оптимизации» . Достижения в области водных ресурсов . 122 : 85–97. arXiv : 1801.08321 . Бибкод : 2018AdWR..122...85H . дои : 10.1016/j.advwatres.2018.10.002 . S2CID 119476042 . Архивировано из оригинала 21 августа 2020 г. Проверено 16 сентября 2020 г.
^ Кук 2016 .
^ «Приближение-ТСП» (PDF) . Архивировано (PDF) из оригинала 1 марта 2022 г. Проверено 17 февраля 2022 г.
^ Аузиелло, Джорджо; и др. (2003), Сложность и аппроксимация (исправленная редакция), Springer, ISBN 978-3-540-65431-5
^ Jump up to: ^а ^б Хромкович, Юрай (2002), Алгоритмика для сложных задач , Тексты по теоретической информатике (2-е изд.), Springer, ISBN 978-3-540-44134-2
^ Канн, Вигго (1992), Об аппроксимируемости задач NP-полной оптимизации , Королевский технологический институт, Швеция, ISBN 91-7170-082-Х
^ Возьмите один город и заберите все возможные приказы остальных 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 . Бибкод : 2008РвМП...80.1061Д . CiteSeerX 10.1.1.563.9990 . дои : 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 .

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

[1] Писатель 2003 , с. 1.

[2] Сбихи, Абделькадер; Эглезе, Ричард В. (2007). «Комбинаторная оптимизация и зеленая логистика» (PDF) . 4ИЛИ . 5 (2): 99–116. дои : 10.1007/s10288-007-0047-3 . S2CID 207070217 . Архивировано (PDF) из оригинала 26 декабря 2019 г. Проверено 26 декабря 2019 г.

[3] Эскандарпур, Маджид; Дежакс, Пьер; Мемчик, Джо; Петон, Оливье (2015). «Проектирование устойчивой сети цепочки поставок: обзор, ориентированный на оптимизацию» (PDF) . Омега . 54 : 11–32. дои : 10.1016/j.omega.2015.01.006 . Архивировано (PDF) из оригинала 26 декабря 2019 г. Проверено 26 декабря 2019 г.

[4] Хобе, Алекс; Фоглер, Дэниел; Сейболд, Мартин П.; Эбигбо, Анози; Сеттгаст, Рэндольф Р.; Саар, Мартин О. (2018). «Оценка скорости потока жидкости через сеть трещин с использованием комбинаторной оптимизации» . Достижения в области водных ресурсов . 122 : 85–97. arXiv : 1801.08321 . Бибкод : 2018AdWR..122...85H . дои : 10.1016/j.advwatres.2018.10.002 . S2CID 119476042 . Архивировано из оригинала 21 августа 2020 г. Проверено 16 сентября 2020 г.

[5] Кук 2016 .

[6] «Приближение-ТСП» (PDF) . Архивировано (PDF) из оригинала 1 марта 2022 г. Проверено 17 февраля 2022 г.

[Ausiello03-7] Аузиелло, Джорджо; и др. (2003), Сложность и аппроксимация (исправленная редакция), Springer, ISBN 978-3-540-65431-5

[Hromkovic02-8] Jump up to: ^а ^б Хромкович, Юрай (2002), Алгоритмика для сложных задач , Тексты по теоретической информатике (2-е изд.), Springer, ISBN 978-3-540-44134-2

[Kann92-9] Канн, Вигго (1992), Об аппроксимируемости задач NP-полной оптимизации , Королевский технологический институт, Швеция, ISBN 91-7170-082-Х

[10] Возьмите один город и заберите все возможные приказы остальных 14 городов. Затем разделите на два, потому что не имеет значения, в каком направлении во времени они следуют друг за другом: 14!/2 = 43 589 145 600.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]