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

Минимального остовного дерева взвешенного плоского графа . Нахождение минимального остовного дерева - распространенная проблема комбинаторной оптимизации.

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

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

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

Приложения [ править ]

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

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

Методы [ править ]

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

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

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

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

Формальное определение [ править ]

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

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

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

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

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

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

Задача оптимизации NP [ править ]

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

размер любого допустимого решения полиномиально ограничен размером данного экземпляра , ${\ Displaystyle у \ в е (х)}$ ${\ displaystyle x}$
языки и могут быть распознаны за полиномиальное время , и ${\ Displaystyle \ {\, х \, \ середина \, х \ в I \, \}}$ ${\ Displaystyle \ {\, (х, у) \, \ середина \, у \ в е (х) \, \}}$
${\ displaystyle m}$ является полиномиальное время вычислимой .

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

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

НПО (I) : равно FPTAS . Содержит задачу о ранце .
НПО (II) : равно ПТАС . Содержит проблему планирования 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 и Max Clique .

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

Конкретные проблемы [ править ]

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

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

См. Также [ править ]

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

Заметки [ править ]

Перейти ↑ Schrijver 2003 , p. 1.
^ Дискретная оптимизация . Эльзевир . Проверено 8 июня 2009 .
^ Сбихи, Абделькадер; Эглезе, Ричард В. (2007). «Комбинаторная оптимизация и зеленая логистика» (PDF) . 4ИЛИ . 5 (2): 99–116. DOI : 10.1007 / s10288-007-0047-3 . S2CID 207070217 .
^ Эскандарпур, Маджид; Деякс, Пьер; Мимчик, Джо; Петон, Оливье (2015). «Дизайн устойчивой сети поставок: обзор, ориентированный на оптимизацию» (PDF) . Омега . 54 : 11–32. DOI : 10.1016 / j.omega.2015.01.006 .
^ Хобе, Алекс; Фоглер, Даниэль; Сейболд, Мартин П .; Эбигбо, Анози; Settgast, Randolph R .; Саар, Мартин О. (2018). «Оценка расходов жидкости через сети трещин с использованием комбинаторной оптимизации» . Достижения в области водных ресурсов . arXiv : 1801.08321 . DOI : 10.1016 / j.advwatres.2018.10.002 .
^ Кук 2016 .
^ Аузиелло, Джорджио; и другие. (2003), Сложность и приближение (исправленное издание), Springer, ISBN 978-3-540-65431-5
^ a b Хромкович, Юрай (2002), Алгоритмика для сложных задач , Тексты в теоретической информатике (2-е изд.), Springer, ISBN 978-3-540-44134-2
^ Канн, Вигго (1992), О приближаемости NP-полных задач оптимизации , Королевский технологический институт, Швеция, ISBN 91-7170-082-X
^ Возьмите один город и возьмите все возможные приказы из других 14 городов. Затем разделите на два, потому что не имеет значения, в каком направлении во времени они идут друг за другом: 14! / 2 = 43,589,145,600.

Ссылки [ править ]

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

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

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

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

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

Дас, Арнаб; Чакрабарти, Бикас К. (2008). «Коллоквиум: квантовый отжиг и аналоговые квантовые вычисления». Ред. Мод. 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 .

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

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

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

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

Шрайвер, Александр (2005). «К истории комбинаторной оптимизации (до 1960 г.)» (PDF) . В Aardal, K .; Nemhauser, GL; Weismantel, R. (ред.). Справочник по дискретной оптимизации . Эльзевир. С. 1–68.

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

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

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

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

Внешние ссылки [ править ]

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

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

[1] Перейти ↑ Schrijver 2003 , p. 1.

[2] Дискретная оптимизация . Эльзевир . Проверено 8 июня 2009 .

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

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

[5] Хобе, Алекс; Фоглер, Даниэль; Сейболд, Мартин П .; Эбигбо, Анози; Settgast, Randolph R .; Саар, Мартин О. (2018). «Оценка расходов жидкости через сети трещин с использованием комбинаторной оптимизации» . Достижения в области водных ресурсов . arXiv : 1801.08321 . DOI : 10.1016 / j.advwatres.2018.10.002 .

[6] Кук 2016 .

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

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

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

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

[1]