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

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

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

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

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

Приложения

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

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

Методы

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

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

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

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

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

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

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

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

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

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

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

• NPO(I) : Равно FPTAS . Содержит задачу о рюкзаке .
• NPO(II) : Равно PTAS . Содержит задачу планирования Makespan .
• NPO(III) : Класс задач NPO, имеющих полиномиальные алгоритмы, которые вычисляют решения со стоимостью, не превышающей c раз оптимальную стоимость (для задач минимизации), или со стоимостью, по крайней мере, равной оптимальной стоимости (для задач максимизации). В книге Громковича [ ^{which ? ]} из этого класса исключены все задачи 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 ^[10] возможных туров, которые посещают каждый город ровно один раз.

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

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

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

Примечания

1. Schrijver 2003, стр. 1.
2. Sbihi, Abdelkader; Eglese, Richard W. (2007). «Комбинаторная оптимизация и зеленая логистика» (PDF) . 4OR . 5 (2): 99–116. doi :10.1007/s10288-007-0047-3. S2CID  207070217. Архивировано (PDF) из оригинала 26.12.2019 . Получено 26.12.2019 .
3. Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier (2015). «Устойчивое проектирование сетей цепочек поставок: обзор, ориентированный на оптимизацию» (PDF) . Omega . 54 : 11–32. doi :10.1016/j.omega.2015.01.006. Архивировано (PDF) из оригинала 26.12.2019 . Получено 26.12.2019 .
4. Hobé, Alex; Vogler, Daniel; Seybold, Martin P.; Ebigbo, Anozie; Settgast, Randolph R.; Saar, Martin O. (2018). «Оценка расходов жидкости через сети трещин с использованием комбинаторной оптимизации». Advances in Water Resources . 122 : 85–97. arXiv : 1801.08321 . Bibcode : 2018AdWR..122...85H. doi : 10.1016/j.advwatres.2018.10.002. S2CID  119476042. Архивировано из оригинала 21.08.2020 . Получено 16.09.2020 .
5. Кук 2016.
6. "Approximation-TSP" (PDF) . Архивировано (PDF) из оригинала 2022-03-01 . Получено 2022-02-17 .
7. Аусиелло, Джорджио и др. (2003), Сложность и аппроксимация (исправленное издание), Springer, ISBN 978-3-540-65431-5
8. Hromkovic, Juraj (2002), Алгоритмика для сложных проблем , Тексты по теоретической информатике (2-е изд.), Springer, ISBN 978-3-540-44134-2
9. Канн, Вигго (1992), Об аппроксимируемости NP-полных задач оптимизации , Королевский технологический институт, Швеция, ISBN 91-7170-082-X
10. Возьмем один город и возьмем все возможные заказы остальных 14 городов. Затем разделим на два, поскольку неважно, в каком направлении во времени они следуют друг за другом: 14!/2 = 43 589 145 600.

Ссылки

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

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

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

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

• Das, Arnab; Chakrabarti, Bikas K , ред. (2005). Квантовый отжиг и связанные с ним методы оптимизации . Конспект лекций по физике. Том 679. Springer. Bibcode :2005qnro.book.....D. ISBN 978-3-540-27987-7.

• Das, Arnab; Chakrabarti, Bikas K (2008). "Colloquium: Quantum annealing and analog quantum computing". 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.

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

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

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

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

• Schrijver, Alexander (2005). «Об истории комбинаторной оптимизации (до 1960 г.)» (PDF) . В Aardal, K. ; Nemhauser, GL; Weismantel, R. (ред.). Handbook of Discrete Optimization . Elsevier. стр. 1–68.

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

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

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

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

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

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