В прикладной математике , филиал и цена является метод комбинаторной оптимизации для решения целочисленного линейного программирования (ЦЛП) и смешанного целочисленного линейного программирования (MILP) проблемы со многими переменными. Этот метод представляет собой гибрид методов создания ветвей и границ и столбцов .
Описание алгоритма
Ветвь и цена - это метод ветвей и границ, в котором в каждом узле дерева поиска столбцы могут быть добавлены в релаксацию линейного программирования (релаксация LP). В начале алгоритма наборы столбцов исключаются из LP-релаксации, чтобы уменьшить требования к вычислениям и памяти, а затем столбцы добавляются обратно в LP-релаксацию по мере необходимости. Подход основан на наблюдении, что для больших задач большинство столбцов будут небазовыми, а соответствующая им переменная будет равна нулю в любом оптимальном решении. Таким образом, подавляющее большинство столбцов не имеют отношения к решению проблемы.
Алгоритм обычно начинается с использования переформулировки, такой как разложение Данцига – Вульфа , чтобы сформировать так называемую главную проблему . Разложение выполняется для получения формулировки задачи, которая дает лучшие оценки, когда релаксация решена, чем когда релаксация исходной формулировки решена. Но декомпозиция обычно содержит много переменных, поэтому решена модифицированная версия, называемая основной задачей с ограничениями , которая рассматривает только подмножество столбцов. [2] Затем для проверки оптимальности решается подзадача, называемая проблемой ценообразования, чтобы найти столбцы, которые могут войти в базис и уменьшить целевую функцию (для задачи минимизации). Это включает в себя поиск столбца с отрицательной приведенной стоимостью . Обратите внимание, что сама проблема ценообразования может быть трудной для решения, но поскольку нет необходимости находить столбец с наиболее отрицательной приведенной стоимостью, можно использовать эвристический и локальный методы поиска. [3] Подзадача должна быть решена только до завершения, чтобы доказать, что оптимальное решение Ограниченной Главной Задачи также является оптимальным решением Главной Задачи. Каждый раз, когда обнаруживается столбец с отрицательной приведенной стоимостью, он добавляется к Задаче Ограниченного Мастера, и релаксация оптимизируется повторно. Если никакие столбцы не могут войти в базис и решение релаксации не является целочисленным, происходит ветвление. [1]
Большинство алгоритмов ветвлений и цен являются специфическими для конкретных задач, поскольку проблема должна быть сформулирована таким образом, чтобы можно было сформулировать эффективные правила ветвления и чтобы проблема ценообразования была относительно легко решена. [4]
Если плоскости отсечения используются для ужесточения релаксации LP в алгоритме ветвления и цены, этот метод известен как цена ветвления и сокращение . [5]
Приложения отрасли и цены
Метод филиала и цены может использоваться для решения проблем в различных областях применения, в том числе:
- Многоцветная раскраска графа. [3] Это обобщение проблемы раскраски графа, в которой каждому узлу в графе должно быть назначено заранее заданное количество цветов, и любые узлы, которые имеют одно ребро, не могут иметь общий цвет. Затем цель состоит в том, чтобы найти минимальное количество цветов, необходимое для правильной окраски. Задачу множественной раскраски можно использовать для моделирования множества приложений, включая планирование заданий и назначение телекоммуникационных каналов.
- Проблемы с маршрутизацией автомобиля . [2]
- Обобщенная задача о назначении . [6]
Смотрите также
Внешние ссылки
- Слайды лекций по отрасли и ценам
- Код прототипа для универсального алгоритма ветвления и цены
- BranchAndCut.org часто задаваемые вопросы
- SCIP - фреймворк с открытым исходным кодом для решающей программы по сокращению ветвей и цене и смешанного целочисленного программирования.
- ABACUS - A Branch-And-CUt System - программное обеспечение с открытым исходным кодом
Рекомендации
- ^ a b Акелла, М .; С. Гупта; А. Саркар. «Ветвь и цена: создание столбцов для решения огромных целочисленных программ» (PDF) . Архивировано из оригинального (PDF) 21 августа 2010 года . Проверено 19 декабря 2012 .
- ^ а б Фейе, Доминик (2010). «Учебное пособие по генерации столбцов и ветвям и ценам для задач маршрутизации транспортных средств». 4ИЛИ . 8 (4): 407–424. DOI : 10.1007 / s10288-010-0130-Z .
- ^ а б Мехрота, Анудж; МА Уловка (2007). Подход по разветвлению и цене для многоцветной раскраски графов . Расширяя горизонты: достижения в области вычислений, оптимизации и технологий принятия решений . Серия интерфейсов для исследования операций / информатики. 37 . С. 15–29 . CiteSeerX 10.1.1.163.6870 . DOI : 10.1007 / 978-0-387-48793-9_2 . ISBN 978-0-387-48790-8.
- ^ Гамрат, Г. "Универсальные отделения по сокращению и цене" (PDF) .
- ^ Desrosiers, J .; ME Lubbecke (2010). «Алгоритмы перехода по цене и отсечению». Энциклопедия Wiley исследований операций и управления .
- ^ Савелсберг, М. (1997). «Разветвленный и ценовой алгоритм для обобщенной задачи о назначениях». Исследование операций . 831-841. 45 (6): 831–841. DOI : 10.1287 / opre.45.6.831 .
- Барнхарт, Синтия; Джонсон, Эллис Л .; Немхаузер, Джордж Л .; Савелсберг, Мартин В. П.; Вэнс, Памела H. (1998), "ветви и цена: поколение колонки для решения больших целочисленных программ", исследование операций , 46 (3): 316-329, CiteSeerX 10.1.1.197.7390 , DOI : 10,1287 / opre. 46.3.316 , JSTOR 222825