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

Ветви и границы ( 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) \leq f (x)$ для всех $x$ в $S I$ .
$Solution(I)$ определяет, представляет ли $я$ единственное решение-кандидат. (Необязательно, если это не так, операция может выбрать возврат некоторого допустимого решения из числа $S I$ . ^{[ 6 ]}) Если $решение(I)$ возвращает решение, то $f (решение(I))$ обеспечивает верхнюю границу оптимального целевого значения во всем пространстве возможных решений.

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

Общая версия

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

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

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

Псевдокод

C ++ Реализация приведенного выше псевдокода в стиле :

// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
    CombinatorialProblem problem, 
    ObjectiveFunction objective_function /*f*/,
    BoundingFunction lower_bound_function /*bound*/) 
{
    // Step 1 above.
    double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
    CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
    problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
    CombinatorialSolution current_optimum = heuristic_solution;
    // Step 2 above
    queue<CandidateSolutionTree> candidate_queue;
    // problem-specific queue initialization
    candidate_queue = populate_candidates(problem);
    while (!candidate_queue.empty()) { // Step 3 above
        // Step 3.1
        CandidateSolutionTree node = candidate_queue.pop();
        // "node" represents N above
        if (node.represents_single_candidate()) { // Step 3.2
            if (objective_function(node.candidate()) < problem_upper_bound) {
                current_optimum = node.candidate();
                problem_upper_bound = objective_function(current_optimum);
            }
            // else, node is a single candidate which is not optimum
        }
        else { // Step 3.3: node represents a branch of candidate solutions
            // "child_branch" represents N_i above
            for (auto&& child_branch : node.candidate_nodes) {
                if (lower_bound_function(child_branch) <= problem_upper_bound) {
                    candidate_queue.enqueue(child_branch); // Step 3.3.2
                }
                // otherwise, bound(N_i) > B so we prune the branch; step 3.3.1
            }
        }
    }
    return current_optimum;
}

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

Улучшения

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

^ А. Х. Лэнд и А. Г. Дойг (1960). «Автоматический метод решения задач дискретного программирования». Эконометрика . 28 (3): 497–520. дои : 10.2307/1910129 . JSTOR 1910129 .
^ «Кадровые новости» . www.lse.ac.uk. Архивировано из оригинала 24 февраля 2021 г. Проверено 8 октября 2018 г.
^ Перейти обратно: ^а ^б ^с Клаузен, Йенс (1999). Алгоритмы ветвей и границ — принципы и примеры (PDF) (технический отчет). Копенгагенский университет . Архивировано из оригинала (PDF) 23 сентября 2015 г. Проверено 13 августа 2014 г.
^ Перейти обратно: ^а ^б Литтл, Джон округ Колумбия; Мурти, Катта Г.; Суини, Дура В.; Карел, Кэролайн (1963). «Алгоритм решения задачи коммивояжера» (PDF) . Исследование операций . 11 (6): 972–989. дои : 10.1287/опре.11.6.972 . hdl : 1721.1/46828 .
^ Балас, Эгон; Тот, Паоло (1983). Методы ветвей и границ для задачи коммивояжера (PDF) (Отчет). Университета Карнеги-Меллона Высшая школа промышленного управления . Архивировано (PDF) из оригинала 20 октября 2012 г.
^ Перейти обратно: ^а ^б Бадер, Дэвид А.; Харт, Уильям Э.; Филлипс, Синтия А. (2004). «Разработка параллельного алгоритма для ветвей и границ» (PDF) . В Гринберге, HJ (ред.). Учебные пособия по новым методологиям и приложениям в исследовании операций . Клювер Академик Пресс. Архивировано из оригинала (PDF) 13 августа 2017 г. Проверено 16 сентября 2015 г.
^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Спрингер. п. 249.
^ Мур, RE (1966). Интервальный анализ . Энглвуд Клифф, Нью-Джерси: Прентис-Холл. ISBN 0-13-476853-1 .
^ Жолен, Л.; Киффер, М.; Дидрит, О.; Уолтер, Э. (2001). Прикладной интервальный анализ . Берлин: Шпрингер. ISBN 1-85233-219-0 .
^ Хансен, скорая помощь (1992). Глобальная оптимизация с использованием интервального анализа . Нью-Йорк: Марсель Деккер.
^ Конвей, Ричард Уолтер ; Максвелл, Уильям Л .; Миллер, Луи В. (2003). Теория планирования . Публикации Courier Dover. стр. 56–61 .
^ Фукунага, Кейносукэ; Нарендра, Патренахалли М. (1975). «Алгоритм ветвей и границ для вычисления $k$ -ближайших соседей». Транзакции IEEE на компьютерах (7): 750–753. дои : 10.1109/tc.1975.224297 . S2CID 5941649 .
^ Нарендра, Патренахалли М.; Фукунага, К. (1977). «Алгоритм ветвей и границ для выбора подмножества функций» (PDF) . Транзакции IEEE на компьютерах . С-26 (9): 917–922. дои : 10.1109/TC.1977.1674939 . S2CID 26204315 .
^ Хазиме, Хусейн; Мазумдер, Рахул; Сааб, Али (2020). «Разреженная регрессия в масштабе: метод ветвей и границ, основанный на оптимизации первого порядка». arXiv : 2004.06152 [ stat.CO ].
^ Новозин, Себастьян; Ламперт, Кристоф Х. (2011). «Структурированное обучение и прогнозирование в компьютерном зрении». Основы и тенденции в компьютерной графике и зрении . 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651 . дои : 10.1561/0600000033 . ISBN 978-1-60198-457-9 .
^ Нау, Дана С.; Кумар, Випин; Канал, Лавин (1984). «Общая ветвь и граница и ее связь с A∗ и AO∗» (PDF) . Искусственный интеллект . 23 (1): 29–58. дои : 10.1016/0004-3702(84)90004-3 .

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

LiPS – Бесплатная, простая в использовании программа с графическим интерфейсом, предназначенная для решения задач линейного, целочисленного и целевого программирования.
Cbc – (Монета или ветвь и разрез) – это решатель смешанного целочисленного программирования с открытым исходным кодом, написанный на C++.

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

[2] «Кадровые новости» . www.lse.ac.uk. Архивировано из оригинала 24 февраля 2021 г. Проверено 8 октября 2018 г.

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

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

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

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

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

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

[9] Жолен, Л.; Киффер, М.; Дидрит, О.; Уолтер, Э. (2001). Прикладной интервальный анализ . Берлин: Шпрингер. ISBN 1-85233-219-0 .

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

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

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

[13] Нарендра, Патренахалли М.; Фукунага, К. (1977). «Алгоритм ветвей и границ для выбора подмножества функций» (PDF) . Транзакции IEEE на компьютерах . С-26 (9): 917–922. дои : 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 . дои : 10.1561/0600000033 . ISBN 978-1-60198-457-9 .

[16] Нау, Дана С.; Кумар, Випин; Канал, Лавин (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 ]