Ветви и границы

Оптимизация путем исключения неоптимальных решений подзадач

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

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

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

Обзор

Целью алгоритма ветвей и границ является поиск значения x , которое максимизирует или минимизирует значение действительной функции f ( x ) , называемой целевой функцией, среди некоторого множества S допустимых или потенциальных решений . Множество S называется пространством поиска или допустимой областью . Остальная часть этого раздела предполагает, что минимизация f ( x ) желательна; это предположение не теряет общности , поскольку можно найти максимальное значение f ( x ) путем нахождения минимума g ( x ) = − f ( x ) . Алгоритм B&B работает в соответствии с двумя принципами:

• Он рекурсивно разбивает пространство поиска на меньшие пространства, а затем минимизирует f ( x ) на этих меньших пространствах; разбиение называется ветвлением .
• Ветвление само по себе будет равносильно перебору возможных решений методом грубой силы и проверке их всех. Для повышения производительности поиска методом грубой силы алгоритм B&B отслеживает границы минимума, который он пытается найти, и использует эти границы для « обрезки » пространства поиска, исключая возможные решения, которые, как он может доказать, не будут содержать оптимального решения.

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

• branch( I ) создает два или более экземпляров, каждый из которых представляет подмножество S _I . (Обычно подмножества не пересекаются , чтобы предотвратить посещение алгоритмом одного и того же возможного решения дважды, но это не обязательно. Однако оптимальное решение среди S _I должно содержаться по крайней мере в одном из подмножеств. ^[6] )
• bound( I ) вычисляет нижнюю границу значения любого возможного решения в пространстве, представленном I , то есть bound( I ) ≤ f ( x ) для всех x в S _I .
• solution( I ) определяет, представляет ли I единственное возможное решение. (Если это не так, операция может выбрать возврат некоторого допустимого решения из числа S _I . ^[6] ) Если solution( I ) возвращает решение, то f (solution( I )) обеспечивает верхнюю границу для оптимального целевого значения во всем пространстве допустимых решений.

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

Обычная версия

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

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

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

Псевдокод

Реализация вышеизложенного на псевдокоде, похожем на C++ , выглядит следующим образом:

// C++-подобная реализация ветвей и границ,// предполагая, что целевая функция f должна быть минимизированаКомбинаторное решение branch_and_bound_solve (  Комбинаторная задача ,   ObjectiveFunction объективная_функция /*f*/ ,   Ограничивающая функция нижняя_граничная_функция /*ограниченная*/ )   { // Шаг 1 выше. double problem_upper_bound = std :: numeric_limits < double >:: infinity ; // = B     Комбинаторное решение эвристическое_решение = эвристическое_решение ( задача ); // x_h     problem_upper_bound = objective_function ( heuristic_solution ); // B = f(x_h)    Комбинаторное решение current_optimum = эвристическое_решение ;    // Шаг 2 выше очередь < CandidateSolutionTree > candidate_queue ;  // инициализация очереди, специфичная для проблемы candidate_queue = populate_candidates ( проблема );   while ( ! candidate_queue . empty ()) { // Шаг 3 выше    // Шаг 3.1 узел CandidateSolutionTree = candidate_queue . pop ();    // "узел" представляет N выше если ( узел . представляет_единственный_кандидат ()) { // Шаг 3.2    если ( целевая_функция ( узел.кандидат ( ) ) < верхняя_граница_проблемы ) {     current_optimum = узел . candidate ();   верхняя_граница_проблемы = целевая_функция ( текущий_оптимум );   } // в противном случае узел является единственным кандидатом, который не является оптимальным } else { // Шаг 3.3: узел представляет ветвь возможных решений   // "child_branch" представляет N_i выше для ( auto && child_branch : node . candidate_nodes ) {      если ( нижняя_граница_функция ( дочерняя_ветвь ) <= проблема_верхняя_граница ) {     candidate_queue.enqueue ( child_branch ) ; // Шаг 3.3.2  } // в противном случае bound(N_i) > B, поэтому мы обрезаем ветвь; шаг 3.3.1 } } } вернуть текущий_оптимум ; }

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

Улучшения

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

Приложения

Этот подход используется для ряда NP-трудных задач:

• Целочисленное программирование
• Нелинейное программирование
• Задача коммивояжера (TSP) ^{[4] [11]}
• Квадратичная задача о назначениях (QAP)
• Задача максимальной выполнимости (MAX-SAT)
• Поиск ближайшего соседа ^[12] ( Кейносукэ Фукунага )
• Планирование работы поточного цеха
• Проблема сокращения запасов
• Вычислительная филогенетика
• Установить инверсию
• Оценка параметров
• 0/1 задача о рюкзаке
• Установить проблему покрытия
• Выбор признаков в машинном обучении ^{[13] [14]}
• Структурированное прогнозирование в компьютерном зрении ^{[15] : 267–276}
• Задача о маршрутизации дуг , включая задачу «Китайский почтальон»
• Планирование талантов , проблемы организации съемок сцен

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

Связь с другими алгоритмами

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

Пример оптимизации

Для решения этой проблемы можно использовать метод ветвей и границ.

Максимизируйте с этими ограничениями ${\displaystyle Z=5x_{1}+6x_{2}}$

${\displaystyle x_{1}+x_{2}\leq 50}$

${\displaystyle 4x_{1}+7x_{2}\leq 280}$

${\displaystyle x_{1},x_{2}\geq 0}$

${\displaystyle x_{1}}$и являются целыми числами. ${\displaystyle x_{2}}$

Первый шаг — ослабить целочисленное ограничение. У нас есть две крайние точки для первого уравнения, которые образуют линию: и . Мы можем образовать вторую линию с векторными точками и . ${\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}0\\50\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}0\\40\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}70\\0\end{bmatrix}}}$

две линии.

Третья точка — . Это область выпуклой оболочки , поэтому решение лежит в одной из вершин области. Мы можем найти пересечение, используя сокращение строк, которое равно , или со значением 276,667. Мы проверяем другие конечные точки, проводя линию по области, и обнаруживаем, что это максимум по действительным числам. ${\displaystyle {\begin{bmatrix}0\\0\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}70/3\\80/3\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}23.333\\26.667\end{bmatrix}}}$

Мы выбираем переменную с максимальной дробной частью, в этом случае она становится параметром для метода ветвей и границ. Мы переходим к и получаем 276 @ . Мы достигли целочисленного решения, поэтому переходим к другой ветви . Мы получаем 275,75 @ . У нас есть десятичное решение, поэтому переходим к и находим 274,571 @ . Мы пробуем другую ветвь , но допустимых решений нет. Следовательно, максимум равен 276 с и . ${\displaystyle x_{2}}$ ${\displaystyle x_{2}\leq 26}$ ${\displaystyle \langle 24,26\rangle }$ ${\displaystyle x_{2}\geq 27}$ ${\displaystyle \langle 22.75,27\rangle }$ ${\displaystyle x_{1}}$ ${\displaystyle x_{1}\leq 22}$ ${\displaystyle \langle 22,27.4286\rangle }$ ${\displaystyle x_{1}\geq 23}$ ${\displaystyle x_{1}\longmapsto 24}$ ${\displaystyle x_{2}\longmapsto 26}$

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

• Откат назад
• Метод ветвей и отсечений — гибрид метода ветвей и границ и метода секущей плоскости , который широко используется для решения целочисленных линейных задач .
• Эволюционный алгоритм
• Альфа-бета обрезка

Ссылки

1. AH Land и AG Doig (1960). «Автоматический метод решения задач дискретного программирования». Econometrica . 28 (3): 497–520. doi :10.2307/1910129. JSTOR  1910129.
2. "Staff News". www.lse.ac.uk . Архивировано из оригинала 2021-02-24 . Получено 2018-10-08 .
3. Clausen, Jens (1999). Алгоритмы ветвей и границ — принципы и примеры (PDF) (технический отчет). Копенгагенский университет . Архивировано из оригинала (PDF) 2015-09-23 . Получено 2014-08-13 .
4. Little, John DC; Murty, Katta G.; Sweeney, Dura W.; Karel, Caroline (1963). "Алгоритм для задачи коммивояжера" (PDF) . Operations Research . 11 (6): 972–989. doi :10.1287/opre.11.6.972. hdl : 1721.1/46828 .
5. Балас, Эгон; Тот, Паоло (1983). Методы ветвей и границ для задачи коммивояжера (PDF) (Отчет). Высшая школа промышленного администрирования Университета Карнеги-Меллона . Архивировано (PDF) из оригинала 20 октября 2012 г.
6. Bader, David A.; Hart, William E.; Phillips, Cynthia A. (2004). "Parallel Algorithm Design for Branch and Bound" (PDF) . В Greenberg, HJ (ред.). Tutorials on Emerging Methodologies and Applications in Operations Research . Kluwer Academic Press. Архивировано из оригинала (PDF) 2017-08-13 . Получено 2015-09-16 .
7. Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Springer. стр. 249.
8. Мур, Р. Э. (1966). Интервальный анализ . Энглвуд Клифф, Нью-Джерси: Prentice-Hall. ISBN 0-13-476853-1.
9. Жолен, Л.; Киффер, М.; Дидрит, О.; Уолтер, Э. (2001). Прикладной интервальный анализ . Берлин: Шпрингер. ISBN 1-85233-219-0.
10. Хансен, ER (1992). Глобальная оптимизация с использованием интервального анализа . Нью-Йорк: Марсель Деккер.
11. Конвей, Ричард Уолтер ; Максвелл, Уильям Л .; Миллер, Луис У. (2003). Теория планирования . Courier Dover Publications. С. 56–61.
12. Фукунага, Кейносукэ; Нарендра, Патренахалли М. (1975). «Алгоритм ветвей и границ для вычисления k -ближайших соседей». IEEE Transactions on Computers (7): 750–753. doi :10.1109/tc.1975.224297. S2CID  5941649.
13. Нарендра, Патренахалли М.; Фукунага, К. (1977). «Алгоритм ветвей и границ для выбора подмножества признаков» (PDF) . IEEE Transactions on Computers . C-26 (9): 917–922. doi :10.1109/TC.1977.1674939. S2CID  26204315.
14. Хазимех, Хуссейн; Мазумдер, Рахул; Сааб, Али (2020). «Разреженная регрессия в масштабе: метод ветвей и границ, укорененный в оптимизации первого порядка». arXiv : 2004.06152 [stat.CO].
15. Новозин, Себастьян; Ламперт, Кристоф Х. (2011). «Структурированное обучение и прогнозирование в компьютерном зрении». Основы и тенденции в компьютерной графике и зрении . 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651 . doi :10.1561/0600000033. ISBN  978-1-60198-457-9.
16. Нау, Дана С.; Кумар, Випин; Канал, Лавин (1984). «Общий метод ветвей и границ и его связь с A∗ и AO∗» (PDF) . Искусственный интеллект . 23 (1): 29–58. doi :10.1016/0004-3702(84)90004-3.

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

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