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

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

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

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

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

Приложения

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

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

Методы

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

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

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

Задачи комбинаторной оптимизации можно рассматривать как поиск лучшего элемента некоторого набора дискретных элементов; поэтому, в принципе, для их решения можно использовать любой поисковый алгоритм или метаэвристику . Возможно, наиболее универсально применимые подходы - это ветвление и граница (точный алгоритм, который может быть остановлен в любой момент времени для использования в качестве эвристики), ветвление и разрезание (использует линейную оптимизацию для генерации границ), динамическое программирование (рекурсивный алгоритм ). построение решения с ограниченным окном поиска) и табу-поиск (жадный алгоритм подкачки). Однако не гарантируется, что общие алгоритмы поиска сначала найдут оптимальное решение, а также не гарантируют, что они будут работать быстро (за полиномиальное время). Поскольку некоторые задачи дискретной оптимизации являются 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}$

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

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

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

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

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

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

• НПО (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 возможных туров, посещающих каждый город ровно один раз.

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

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

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

Заметки

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

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

• Кук, Уильям Дж .; Каннингем, Уильям Х .; 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.

• Шрайвер, Александр (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 (открытый исходный код)
• Почему сложно составлять расписание для людей?
• Классы сложности для задач оптимизации / Стефан Кугеле