Филиал и цена
В прикладной математике ветвь и цена — это метод комбинаторной оптимизации для решения задач целочисленного линейного программирования (ILP) и смешанного целочисленного линейного программирования (MILP) со многими переменными. Этот метод представляет собой гибрид методов ветвей и границ и генерации столбцов .
Описание алгоритма
[ редактировать ]Ветви и цена — это метод ветвей и границ, в котором в каждом узле дерева поиска столбцы могут быть добавлены для релаксации линейного программирования (релаксация LP). В начале алгоритма наборы столбцов исключаются из релаксации LP, чтобы уменьшить требования к вычислениям и памяти, а затем при необходимости столбцы добавляются обратно в релаксацию LP. Этот подход основан на наблюдении, что для больших задач большинство столбцов будут небазисными и их соответствующая переменная будет равна нулю в любом оптимальном решении. Таким образом, подавляющее большинство столбцов не имеют отношения к решению проблемы.
Алгоритм обычно начинается с использования переформулировки, такой как разложение Данцига – Вольфа , для формирования так называемой главной проблемы . Разложение выполняется для получения формулировки задачи, которая дает лучшие границы при решении релаксации, чем при решении релаксации исходной формулировки. Но декомпозиция обычно содержит много переменных, поэтому решается модифицированная версия, называемая ограниченной главной проблемой , которая рассматривает только подмножество столбцов. [2] Затем для проверки на оптимальность решается подзадача, называемая проблемой ценообразования , чтобы найти столбцы, которые могут войти в базис и уменьшить целевую функцию (для задачи минимизации). Это предполагает поиск столбца с отрицательной приведенной стоимостью . Обратите внимание, что саму проблему ценообразования может быть трудно решить, но поскольку нет необходимости находить столбец с наиболее отрицательной приведенной стоимостью, можно использовать эвристические и локальные методы поиска. [3] Подзадачу необходимо решить до конца только для того, чтобы доказать, что оптимальное решение Ограниченной главной задачи также является оптимальным решением Главной задачи. Каждый раз, когда обнаруживается столбец с отрицательной приведенной стоимостью, он добавляется к Ограниченной главной задаче, и релаксация повторно оптимизируется. Если ни один столбец не может войти в базис и решение релаксации не является целым, то происходит ветвление. [1]
Большинство алгоритмов ветвления и ценообразования специфичны для конкретной задачи, поскольку проблема должна быть сформулирована таким образом, чтобы можно было сформулировать эффективные правила ветвления и чтобы проблему ценообразования было относительно легко решить. [4]
Если секущие плоскости используются для ужесточения релаксации LP в алгоритме ветвления и цены, этот метод известен как цена ветвления и разрез . [5]
Приложения отрасли и цены
[ редактировать ]Метод ветвей и цен можно использовать для решения задач в различных прикладных областях, в том числе:
- Раскраска графа. [3] Это обобщение проблемы раскраски графа , в которой каждому узлу графа должно быть присвоено заданное количество цветов, и любые узлы, имеющие общее ребро, не могут иметь общий цвет. Цель состоит в том, чтобы найти минимальное количество цветов, необходимое для правильной раскраски. Задача многоцветности может использоваться для моделирования различных приложений, включая планирование заданий и назначение каналов связи.
- Проблемы с маршрутизацией транспортных средств . [2]
- Обобщенная задача о назначениях . [6]
См. также
[ редактировать ]Внешние ссылки
[ редактировать ]- Слайды лекций по отрасли и ценам
- Код прототипа для общего алгоритма ветвей и цен
- Часто задаваемые вопросы о BranchAndCut.org
- SCIP - платформа с открытым исходным кодом для расчета ветвей и цены и решатель смешанного целочисленного программирования.
- ABACUS – Система филиалов и разрезов – программное обеспечение с открытым исходным кодом
Ссылки
[ редактировать ]- ^ Jump up to: а б Акелла, М.; С. Гупта; А. Саркар. «Отрасль и цена: генерация столбцов для решения огромных целочисленных программ» (PDF) . Архивировано из оригинала (PDF) 21 августа 2010 г. Проверено 19 декабря 2012 г.
- ^ Jump up to: а б Фейе, Доминик (2010). «Учебное пособие по созданию столбцов и ветвям и ценам для решения задач маршрутизации транспортных средств». 4ИЛИ . 8 (4): 407–424. дои : 10.1007/s10288-010-0130-z .
- ^ Jump up to: а б Мехрота, Анудж; М. А. Трюк (2007). «Подход «ветвь и цена» для мультираскраски графов» . Расширение горизонтов: достижения в области вычислений, оптимизации и технологий принятия решений . Серия интерфейсов исследования операций/информатики. Том. 37. С. 15–29 . CiteSeerX 10.1.1.163.6870 . дои : 10.1007/978-0-387-48793-9_2 . ISBN 978-0-387-48790-8 .
- ^ Гамрат, Г. «Общие цены на ветки и цены» (PDF) .
- ^ Дерозье, Ж.; М. Е. Люббеке (2010). «Алгоритмы ветвления цены и сокращения». Энциклопедия исследований операций и науки управления Wiley .
- ^ Савелсберг, М. (1997). «Алгоритм ветвей и цены для обобщенной задачи назначения». Исследование операций . 831-841. 45 (6): 831–841. дои : 10.1287/опре.45.6.831 .
- Барнхарт, Синтия; Джонсон, Эллис Л.; Немхаузер, Джордж Л .; Савелсберг, Мартин В.П.; Вэнс, Памела Х. (1998), «Отрасль и цена: генерация столбцов для решения огромных целочисленных программ», Operations Research , 46 (3): 316–329, CiteSeerX 10.1.1.197.7390 , doi : 10.1287/упр. 46.3.316 , JSTOR 222825
 | ||||