Филиал и цена - Branch and price

В Прикладная математика, филиал и цена это метод комбинаторная оптимизация для решения целочисленное линейное программирование (ILP) и смешанное целочисленное линейное программирование (MILP) проблемы со многими переменными. Метод представляет собой гибрид ветвь и переплет и генерация столбца методы.

Описание алгоритма

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

Схема отделения и алгоритм цен. Адаптирован из [1]

Алгоритм обычно начинается с переформулировки, например Разложение Данцига – Вульфа, чтобы сформировать то, что известно как Главная проблема. Разложение выполняется для получения формулировки задачи, которая дает лучшие оценки, когда релаксация решена, чем когда релаксация исходной постановки решена. Но разложение обычно содержит много переменных, поэтому модифицированная версия, называемая Ограниченная проблема мастера, который учитывает только подмножество столбцов.[2] Затем, чтобы проверить оптимальность, подзадача называется проблема ценообразования решается найти столбцы, которые могут войти в базис и уменьшить целевую функцию (для задачи минимизации). Это включает в себя поиск столбца с отрицательным сниженная стоимость. Обратите внимание, что сама проблема ценообразования может быть трудной для решения, но, поскольку нет необходимости находить столбец с наиболее отрицательной приведенной стоимостью, можно использовать эвристический и локальный методы поиска.[3] Подзадача должна быть решена только до завершения, чтобы доказать, что оптимальное решение Ограниченной Главной Задачи также является оптимальным решением Главной Задачи. Каждый раз, когда обнаруживается столбец с отрицательной приведенной стоимостью, он добавляется к Задаче Ограниченного Мастера, и релаксация повторно оптимизируется. Если ни один столбец не может войти в базис и решение релаксации не является целым числом, происходит ветвление.[1]

Большинство алгоритмов ветвления и ценообразования являются специфическими для конкретной задачи, поскольку проблема должна быть сформулирована таким образом, чтобы можно было сформулировать эффективные правила ветвления и чтобы проблема ценообразования была относительно легко решаемой.[4]

Если плоскости отсечения используются для сужения релаксации LP в рамках алгоритма ветвей и цены, метод известен как цена и скидка в филиале.[5]

Приложения отрасли и цены

Метод филиала и цены может использоваться для решения задач в различных областях применения, в том числе:

  • Многоцветная раскраска графа.[3] Это обобщение раскраска графика проблема, при которой каждому узлу в графе должно быть назначено заранее заданное количество цветов, а любые узлы, которые имеют одно ребро, не могут иметь общий цвет. Затем цель состоит в том, чтобы найти минимальное количество цветов, необходимое для правильной окраски. Задача множественной раскраски может использоваться для моделирования множества приложений, включая планирование заданий и назначение каналов связи.
  • Проблемы с маршрутизацией автомобиля.[2]
  • Обобщенная проблема присваивания.[6]

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

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

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

  1. ^ а б Акелла, М .; С. Гупта; А. Саркар. «Ветвь и цена: создание столбцов для решения огромных целочисленных программ» (PDF). Архивировано из оригинал (PDF) на 21.08.2010. Получено 2012-12-19.
  2. ^ а б Фейе, Доминик (2010). «Учебник по созданию столбцов и разветвлению и цене для задач маршрутизации транспортных средств». 4ИЛИ. 8 (4): 407–424. Дои:10.1007 / s10288-010-0130-z.
  3. ^ а б Мехрота, Анудж; М.А. Трюк (2007). Подход ветвления и цены для многоцветной раскраски графов. Расширяя горизонты: достижения в области вычислений, оптимизации и технологий принятия решений. Серия интерфейсов для исследования операций / информатики. 37. стр.15–29. CiteSeerX  10.1.1.163.6870. Дои:10.1007/978-0-387-48793-9_2. ISBN  978-0-387-48790-8.
  4. ^ Люббеке, М. "Универсальный филиал по сокращению и цене" (PDF).
  5. ^ Desrosiers, J .; М.Е. Люббеке (2010). «Алгоритмы перехода по цене и отсечке». Энциклопедия исследований операций и управления Wiley.
  6. ^ Савелсберг, М. (1997). «Разветвленный и ценовой алгоритм для обобщенной задачи о назначениях». Исследование операций. 831-841. 45 (6): 831–841. Дои:10.1287 / opre.45.6.831.