Ветвь и переплет - Branch and bound

Ветвь и переплет (BB, B & B, или же BnB) является алгоритм парадигма дизайна за дискретный и комбинаторная оптимизация проблемы, а также математическая оптимизация. Алгоритм ветвей и границ состоит из систематического перечисления возможных решений с помощью поиск в пространстве состояний: набор возможных решений рассматривается как формирующий укоренившееся дерево с полным набором в корень. Алгоритм исследует ветви этого дерева, которые представляют собой подмножества множества решений. Перед тем, как перечислить возможные решения ветви, ветвь проверяется по верхней и нижней оценкам. границы на оптимальном решении и отбрасывается, если оно не может дать лучшего решения, чем лучшее, найденное алгоритмом на данный момент.

Алгоритм зависит от эффективной оценки нижней и верхней границ областей / ветвей пространства поиска. Если границы недоступны, алгоритм переходит к исчерпывающему поиску.

Метод был впервые предложен Ailsa Land и Элисон Дойг при проведении исследований в Лондонская школа экономики при поддержке British Petroleum^[1]^[2] в 1960 году для дискретное программирование, и стал наиболее часто используемым инструментом для решения NP-жесткий проблемы оптимизации.^[3] Название «ветвь и переплет» впервые появилось в творчестве Литтла. и другие. на задача коммивояжера.^[4]^[5]

Обзор

Цель алгоритма ветвей и границ - найти значение $Икс$ который максимизирует или минимизирует значение функции с действительным знаком $ж (Икс)$ , называемой целевой функцией, среди некоторого множества $S$ допустимого, или возможные решения. Набор $S$ называется пространством поиска, или возможный регион. В остальной части этого раздела предполагается, что минимизация $ж (Икс)$ желательно; это предположение приходит не теряя общий смысл, так как можно найти максимальное значение $ж (Икс)$ найдя минимум $грамм (Икс) = - ж (Икс)$ . Алгоритм B&B работает по двум принципам:

Он рекурсивно разбивает пространство поиска на меньшие пространства, а затем минимизирует $ж (Икс)$ на этих меньших пространствах; расщепление называется разветвление.
Одно только ветвление составило бы грубая сила перечисление возможных решений и их тестирование. Чтобы повысить производительность поиска методом перебора, алгоритм B&B отслеживает границы минимум, который он пытается найти, и использует эти границы для "чернослив «пространство поиска, исключающее возможные решения, которые, как можно доказать, не содержат оптимального решения.

Превращение этих принципов в конкретный алгоритм решения конкретной задачи оптимизации требует некоторого структура данных который представляет собой наборы возможных решений. Такое представление называется пример проблемы. Обозначим множество возможных решений экземпляра $я$ к $S я$ . Экземплярное представление должно иметь три операции:

$ответвляться(я)$ производит два или более экземпляра, каждый из которых представляет подмножество $S я$ . (Обычно подмножества непересекающийся чтобы алгоритм не посетил одно и то же решение дважды, но это не обязательно. Однако оптимальное решение среди $S я$ должен содержаться хотя бы в одном из подмножеств.^[6])
$граница(я)$ вычисляет нижнюю границу значения любого возможного решения в пространстве, представленном $я$ , то есть, $граница(я) \leq ж (Икс)$ для всех $Икс$ в $S я$ .
$решение(я)$ определяет, есть ли $я$ представляет собой единственное возможное решение. (Необязательно, если это не так, операция может решить вернуть какое-либо возможное решение из числа $S я$ .^[6]) Если $решение(я)$ возвращает решение тогда $ж (решение(я))$ дает оценку сверху оптимального целевого значения на всем пространстве допустимых решений.

Используя эти операции, алгоритм B&B выполняет рекурсивный поиск сверху вниз по дерево экземпляров, образованных операцией ветвления. При посещении экземпляра $я$ , он проверяет, $граница(я)$ больше найденного на данный момент верхнего предела; если так, $я$ можно безопасно исключить из поиска, и рекурсия остановится. Этот шаг сокращения обычно реализуется путем поддержания глобальной переменной, которая записывает минимальную верхнюю границу, наблюдаемую среди всех исследованных экземпляров.

Общая версия

Ниже приведен скелет общего алгоритма ветвей и границ для минимизации произвольной целевой функции. $ж$ .^[3] Чтобы получить из этого реальный алгоритм, требуется ограничивающая функция $граница$ , который вычисляет нижние границы $ж$ на узлах дерева поиска, а также правило ветвления для конкретной задачи. Таким образом, общий алгоритм, представленный здесь, является функция высшего порядка.

Используя эвристический, найти решение $Икс час$ к задаче оптимизации. Сохраните его ценность, $B = ж (Икс час)$ . (Если эвристика недоступна, установите $B$ до бесконечности.) $B$ будет обозначать лучшее решение, найденное на данный момент, и будет использоваться как верхняя граница возможных решений.
Инициализируйте очередь, чтобы сохранить частичное решение без присвоения ни одной из переменных задачи.
Цикл, пока очередь не станет пустой:
1. Возьмите узел $N$ вне очереди.
2. Если $N$ представляет собой единственное возможное решение $Икс$ и $ж (Икс) < B$ , тогда $Икс$ пока что это лучшее решение. Запишите это и установите $B \leftarrow ж (Икс)$ .
3. Еще, ответвляться на N производить новые узлы N_я. Для каждого из них:
  1. Если $граница(N я) > B$ , ничего не делать; поскольку нижняя граница этого узла больше верхней границы задачи, она никогда не приведет к оптимальному решению и может быть отброшена.
  2. В противном случае магазин $N я$ в очереди.

Несколько разных очередь могут использоваться структуры данных. Этот Очередь FIFO -на основе реализации дает поиск в ширину. А куча (Очередь LIFO) даст в глубину алгоритм. А лучший первый алгоритм ветвей и границ может быть получен с помощью приоритетная очередь который сортирует узлы по их нижней границе.^[3] Примеры алгоритмов поиска лучшего первого с этой предпосылкой: Алгоритм Дейкстры и его потомок Поиск. Вариант с приоритетом в глубину рекомендуется, когда нет хорошей эвристики для получения начального решения, поскольку он быстро дает полные решения и, следовательно, верхние границы.^[7]

Псевдокод

А C ++ -подобная реализация псевдокода вышеизложенного:

 1 // C ++ - подобная реализация ветвления и привязки,  2 // предполагая, что целевая функция f должна быть минимизирована 3 Комбинаторное решение branch_and_bound_solve( 4     Комбинаторная проблема проблема,  5     ЦельФункция objective_function / * f * /, 6     BoundingFunction lower_bound_function /*граница*/)  7 { 8     // Шаг 1 выше 9     двойной проблема_upper_bound = стандартное::numeric_limits<двойной>::бесконечность; // = B10     Комбинаторное решение heuristic_solution = heuristic_solve(проблема); // x_h11     проблема_upper_bound = objective_function(heuristic_solution); // B = f (x_h)12     Комбинаторное решение current_optimum = heuristic_solution;13     // Шаг 2 выше14     очередь<КандидатРешениеДерево> кандидат в очередь;15     // инициализация очереди для конкретной проблемы16     кандидат в очередь = populate_candidates(проблема);17     пока (!кандидат в очередь.пустой()) { // Шаг 3 выше18         // Шаг 3.119         КандидатРешениеДерево узел = кандидат в очередь.поп();20         // "узел" представляет N выше21         если (узел.представляет_single_candidate()) { // Шаг 3.222             если (objective_function(узел.кандидат()) < проблема_upper_bound) {23                 current_optimum = узел.кандидат();24                 проблема_upper_bound = objective_function(current_optimum);25             }26             // иначе узел - единственный кандидат, который не является оптимальным27         }28         еще { // Шаг 3.3: узел представляет ветвь возможных решений29             // "child_branch" представляет N_i выше30             за (авто&& child_branch : узел.кандидат_узлы) {31                 если (lower_bound_function(child_branch) <= проблема_upper_bound) {32                     кандидат в очередь.ставить в очередь(child_branch); // Шаг 3.3.233                 }34                 // иначе, bound (N_i)> B, поэтому мы обрезаем ветку; шаг 3.3.135             }36         }37     }38     возвращаться current_optimum;39 }

В приведенном выше псевдокоде функции heuristic_solve и populate_candidates вызываемые как подпрограммы должны быть предоставлены в зависимости от проблемы. Функции $ж$ (objective_function) и $граница$ (lower_bound_function) рассматриваются как функциональные объекты как написано, и может соответствовать лямбда-выражения, указатели на функции или же функторы на языке программирования C ++, среди других типов вызываемые объекты.

Улучшения

Когда ${ displaystyle mathbf {x}}$ вектор ${ Displaystyle mathbb {R} ^ {п}}$ , алгоритмы ветвлений и границ можно комбинировать с интервальный анализ^[8] и подрядчик методы, чтобы обеспечить гарантированные вложения глобального минимума.^[9]^[10]

Приложения

Этот подход используется для ряда NP-жесткий проблемы

Ветвь и переплет также могут быть основой различных эвристика. Например, можно захотеть прекратить ветвление, когда разрыв между верхней и нижней границами станет меньше определенного порога. Это используется, когда решение «достаточно хорошо для практических целей» и может значительно сократить требуемые вычисления. Этот тип решения особенно применим, когда используемая функция стоимости шумный или это результат статистические оценки и поэтому точно не известно, а известно только, что они лежат в диапазоне значений с конкретным вероятность.^{[нужна цитата ]}

Отношение к другим алгоритмам

Нау и другие. представляют собой обобщение ветвей и границ, которое также включает А *, B * и альфа-бета алгоритмы поиска из искусственный интеллект.^[16]

внешняя ссылка

LiPS - Бесплатная простая в использовании программа с графическим интерфейсом, предназначенная для решения задач линейного, целочисленного и целевого программирования.
Cbc - (Coin-or branch and cut) - решатель смешанного целочисленного программирования с открытым исходным кодом, написанный на C ++.

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

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

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

^ А. Х. Лэнд и А. Г. Дойг (1960). «Автоматический метод решения задач дискретного программирования». Econometrica. 28 (3). С. 497–520. Дои:10.2307/1910129.
^ "Новости персонала". www.lse.ac.uk. Получено 2018-10-08.
^ ^а ^б ^c Клаузен, Йенс (1999). Алгоритмы ветвей и границ - принципы и примеры (PDF) (Технический отчет). Копенгагенский университет. Архивировано из оригинал (PDF) на 2015-09-23. Получено 2014-08-13.
^ ^а ^б Литтл, Джон Д. К.; Murty, Katta G .; Суини, Дура У .; Карел, Кэролайн (1963). «Алгоритм задачи коммивояжера» (PDF). Исследование операций. 11 (6): 972–989. Дои:10.1287 / opre.11.6.972.
^ Балас, Эгон; Тот, Паоло (1983). Методы ветвей и границ для задачи коммивояжера (PDF) (Отчет). Университет Карнеги Меллон Высшая школа промышленного администрирования. Архивировано из оригинал (PDF) 20 октября 2012 г.
^ ^а ^б Бадер, Дэвид А .; Харт, Уильям Э .; Филлипс, Синтия А. (2004). «Разработка параллельного алгоритма для ветвей и границ» (PDF). В Гринберге, Х. Дж. (Ред.). Учебники по новым методологиям и приложениям в исследовании операций. Kluwer Academic Press. Архивировано из оригинал (PDF) на 2017-08-13. Получено 2015-09-16.
^ Мельхорн, Курт; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF). Springer. п. 249.
^ Мур, Р. Э. (1966). Интервальный анализ. Энглвуд Клифф, Нью-Джерси: Прентис-Холл. ISBN 0-13-476853-1.
^ Jaulin, L .; Kieffer, M .; Didrit, O .; Уолтер, Э. (2001). Прикладной интервальный анализ. Берлин: Springer. ISBN 1-85233-219-0.
^ Хансен, Э. Р. (1992). Глобальная оптимизация с использованием интервального анализа. Нью-Йорк: Марсель Деккер.
^ Конвей, Ричард Уолтер; Максвелл, Уильям Л .; Миллер, Луи В. (2003). Теория планирования. Courier Dover Publications. стр.56–61.
^ Фукунага, Кейносуке; Нарендра, Патренахалли М. (1975). "Алгоритм ветвей и границ для вычисления $k$ -ближайшие соседи ». Транзакции IEEE на компьютерах: 750–753. Дои:10.1109 / т-с.1975.224297.
^ Narendra, Patrenahalli M .; Фукунага, К. (1977). «Алгоритм ветвей и границ для выбора подмножества признаков» (PDF). Транзакции IEEE на компьютерах. С-26 (9): 917–922. Дои:10.1109 / TC.1977.1674939.
^ Хазиме, Хусейн; Мазумдер, Рахул; Сааб, Али (2020). «Разреженная регрессия в масштабе: ветвление и граница, основанная на оптимизации первого порядка». arXiv:2004.06152.
^ Новозин, Себастьян; Ламперт, Кристоф Х. (2011). «Структурированное обучение и прогнозирование в компьютерном зрении». Основы и тенденции компьютерной графики и зрения. 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651. Дои:10.1561/0600000033. ISBN 978-1-60198-457-9.
^ Nau, Dana S .; Кумар, Випин; Канал, Лавин (1984). «Общая ветвь и граница и ее связь с A ∗ и AO ∗» (PDF). Искусственный интеллект. 23 (1): 29–58. Дои:10.1016/0004-3702(84)90004-3.

[land_doig-1] А. Х. Лэнд и А. Г. Дойг (1960). «Автоматический метод решения задач дискретного программирования». Econometrica. 28 (3). С. 497–520. Дои:10.2307/1910129.

[2] "Новости персонала". www.lse.ac.uk. Получено 2018-10-08.

[clausen99-3] а ^б ^c Клаузен, Йенс (1999). Алгоритмы ветвей и границ - принципы и примеры (PDF) (Технический отчет). Копенгагенский университет. Архивировано из оригинал (PDF) на 2015-09-23. Получено 2014-08-13.

[little-4] а ^б Литтл, Джон Д. К.; Murty, Katta G .; Суини, Дура У .; Карел, Кэролайн (1963). «Алгоритм задачи коммивояжера» (PDF). Исследование операций. 11 (6): 972–989. Дои:10.1287 / opre.11.6.972.

[5] Балас, Эгон; Тот, Паоло (1983). Методы ветвей и границ для задачи коммивояжера (PDF) (Отчет). Университет Карнеги Меллон Высшая школа промышленного администрирования. Архивировано из оригинал (PDF) 20 октября 2012 г.

[bader-6] а ^б Бадер, Дэвид А .; Харт, Уильям Э .; Филлипс, Синтия А. (2004). «Разработка параллельного алгоритма для ветвей и границ» (PDF). В Гринберге, Х. Дж. (Ред.). Учебники по новым методологиям и приложениям в исследовании операций. Kluwer Academic Press. Архивировано из оригинал (PDF) на 2017-08-13. Получено 2015-09-16.

[7] Мельхорн, Курт; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF). Springer. п. 249.

[8] Мур, Р. Э. (1966). Интервальный анализ. Энглвуд Клифф, Нью-Джерси: Прентис-Холл. ISBN 0-13-476853-1.

[9] Jaulin, L .; Kieffer, M .; Didrit, O .; Уолтер, Э. (2001). Прикладной интервальный анализ. Берлин: Springer. ISBN 1-85233-219-0.

[10] Хансен, Э. Р. (1992). Глобальная оптимизация с использованием интервального анализа. Нью-Йорк: Марсель Деккер.

[11] Конвей, Ричард Уолтер; Максвелл, Уильям Л .; Миллер, Луи В. (2003). Теория планирования. Courier Dover Publications. стр.56–61.

[12] Фукунага, Кейносуке; Нарендра, Патренахалли М. (1975). "Алгоритм ветвей и границ для вычисления $k$ -ближайшие соседи ». Транзакции IEEE на компьютерах: 750–753. Дои:10.1109 / т-с.1975.224297.

[13] Narendra, Patrenahalli M .; Фукунага, К. (1977). «Алгоритм ветвей и границ для выбора подмножества признаков» (PDF). Транзакции IEEE на компьютерах. С-26 (9): 917–922. Дои:10.1109 / TC.1977.1674939.

[14] Хазиме, Хусейн; Мазумдер, Рахул; Сааб, Али (2020). «Разреженная регрессия в масштабе: ветвление и граница, основанная на оптимизации первого порядка». arXiv:2004.06152.

[15] Новозин, Себастьян; Ламперт, Кристоф Х. (2011). «Структурированное обучение и прогнозирование в компьютерном зрении». Основы и тенденции компьютерной графики и зрения. 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651. Дои:10.1561/0600000033. ISBN 978-1-60198-457-9.

[16] Nau, Dana S .; Кумар, Випин; Канал, Лавин (1984). «Общая ветвь и граница и ее связь с A ∗ и AO ∗» (PDF). Искусственный интеллект. 23 (1): 29–58. Дои:10.1016/0004-3702(84)90004-3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]