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

редактировать

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

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

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

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

Содержание

1 Приложения
2 Методы
3 Формальное определение
4 Проблема оптимизации NP
5 Конкретные проблемы
6 См. Также
7 Примечания
8 Ссылки
9 Внешние ссылки

Приложения

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

Логистика
Оптимизация цепочки поставок
Создание лучшей авиалинии из спиц и направлений
Выбор такси в парке для получения платы за проезд
Определение оптимального способа доставки пакетов
Определение оптимального распределения рабочих мест между людьми
Проектирование сетей распределения воды
Проблемы науки о Земле (например, резервуар дебиты)

Методы

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

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

точно решаемые за полиномиальное время частные случаи рассматриваемой проблемы (например, см. исправлено -параметрические алгоритмы )
, которые хорошо работают на "случайных" экземплярах (например, для TSP )
алгоритмы аппроксимации, которые выполняются за полиномиальное время и находят решение, которое "близко" к оптимальному
решение реальных примеров, которые возникают на практике и не обязательно демонстрируют наихудшее поведение, присущее NP-полным задачам (например, экземпляры TSP с десятками тысяч узлов).

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

Формальное определение

Формально комбинаторная оптимизация задача $A {\ displaystyle A}$ $A$ - это четверка $(I, f, m, g) {\ displaystyle (I, f, m, g)}$ $(I, f, m, g)$ , где

$I {\ displaystyle I}$ $I$ - набор экземпляров;
задан экземпляр $x ∈ I { \ displaystyle x \ in I}$ $x \ in I$ , $f (x) {\ displaystyle f (x)}$ $f (x)$ - конечный набор возможных решений;
с учетом экземпляра $x { \ displaystyle x}$ $x$ и возможное решение $y {\ displaystyle y}$ $y$ of $x {\ displaystyle x}$ $x$ , $m (x, y) {\ displaystyle m (x, y)}$ $m (x, y)$ обозначает показатель из $y {\ displaystyle y}$ $y$ , который обычно положительный real.
$g {\ displaystyle g}$ $г$ - целевая функция, равная либо $min {\ displaystyle \ min}$ $\ min$ , либо $max { \ Displaystyle \ max}$ $\ max$ .

Затем цель состоит в том, чтобы найти для некоторого экземпляра $x {\ displaystyle x}$ $x$ оптимальное решение, то есть возможное решение $y {\ displaystyle y}$ $y$ с

m (x, y) = g {m (x, y ′) ∣ y ′ ∈ f (x)}. {\ displaystyle m (x, y) = g \ {m (x, y ') \ mid y' \ in f (x) \}.}

m(x,y)=g\{m(x,y')\mid y'\in f(x)\}.

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

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

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

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

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

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

NPO делится на следующие подклассы в зависимости от их аппроксимируемости:

NPO (I): равно FPTAS. Содержит задачу о ранце.
NPO (II): равно PTAS. Содержит задачу планирования Makespan.
NPO (III):: Класс проблем NPO, которые имеют алгоритмы с полиномиальным временем, которые вычисляют решения со стоимостью, не превышающей c оптимальных затрат (для задачи минимизации) или стоимость не менее $1 / c {\ displaystyle 1 / 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 и Max Clique.

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

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

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

См. Также

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

Примечания

Ссылки

Бисли, JE «Целочисленное программирование» (лекции). CS1 maint: ref = harv (ссылка )

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

Кук, Уильям (2016). «Оптимальные туры TSP». Университеты Ватерлоо. CS1 maint: ref = harv (ссылка ) (Информация о крупнейших на сегодняшний день случаях TSP)

Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпинский, Марек ; Woeginger, Gerhard (ред.). «Сборник проблем оптимизации NP». CS1 maint: ref = harv (ссылка ) (Это постоянно обновляемый каталог результатов аппроксимации для задач оптимизации NP.)

Дас, Арнаб; Чакрабарти, Бикас К., ред. (2005). Квантовый отжиг и связанные с ним методы оптимизации. Конспект лекций по физике. 679 . Springer. Bibcode : 2005qnro.book..... D. CS1 maint: ref = harv (ссылка )

Das, Arnab; Chakrabarti, Bikas K ( 2008). "Коллоквиум: квантовый отжиг и аналоговые квантовые вычисления". Rev. Mod. Phys. 80 (3): 1061. arXiv : 0801.2193. Bibcode : 2008RvMP... 80.1061D. CiteSeerX 10.1.1.563.9990. doi : 10.1103 / RevModPhys.80.1061. S2CID 14255125. CS1 maint: ref = harv (ссылка )

Лоулер, Юджин (2001). Комбинаторная оптимизация: сети и матроиды. Dover. ISBN 0-486-41453-1. Cite имеет пустой неизвестный параметр: | 1 =( ) CS1 maint: ref = harv (ссылка )

Ли, Джон (2004). Первый курс комбинаторной оптимизации. Cambridge University Press. ISBN 0-521-01012-8. CS1 maint: ref = harv (ссылка )

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

Шрайвер, Александр (2003). Комбинаторная оптимизация : Многогранники и эффективность. Алгоритмы и комбинаторика. 24 . Springer. ISBN 9783540443896. CS1 maint: ref = harv (ссылка )

Шрайвер, Александр (2005). «Из истории комбинаторной оптимизации (до 1960)» (PDF). В Аардал, К. ; Немхаузер, Г.Л.; Вайсмантель, R. (ред.). Handbook of Discrete Optimization. Elsevier. Pp. 1–68. CS1 maint: ref = harv (ссылка )

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

; Гош, Диптеш (2010). Сети в действии; Текст и компьютерные упражнения по оптимизации сети. Springer. ISBN 978-1-4419-5512-8. CS1 maint: ref = harv (ссылка )

Джерард Сирксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика. CRC Press. ISBN 978-1-498-71016-9.

Pintea, C-M. (2014). Достижения в области биологических вычислений для задачи комбинаторной оптимизации. Справочная библиотека интеллектуальных систем. Springer. ISBN 978-3-642-40178-7. CS1 maint: ref = harv (ссылка )

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

На Викискладе есть медиафайлы to Комбинаторная оптимизация.