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

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

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

Этот метод был впервые предложен Эйлсой Лэнд и Элисон Дойг во время проведения исследования в Лондонской школе экономики, спонсируемого British Petroleum, в 1960 году по дискретному программированию . и стал наиболее часто используемым инструментом для решения NP-сложных задач оптимизации. Название «ветвь и границ» впервые появилось в работе Литтла и др. по задаче коммивояжера .

Обзор

Цель алгоритма ветвей и границ — найти значение 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 должно содержаться хотя бы в одном из подмножеств. )
• bound( I ) вычисляет нижнюю границу значения любого решения-кандидата в пространстве, представленном I , то естьbound ( I ) ≤ f ( x ) для всех x в S _I .
• Solution( I ) определяет, представляет ли я единственное решение-кандидат. (Необязательно, если это не так, операция может выбрать возврат некоторого допустимого решения из числа S _I . ) Если решение( I ) возвращает решение, то f (решение( I )) обеспечивает верхнюю границу оптимального целевого значения во всем пространстве возможных решений.

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

Общая версия

Ниже приведен скелет общего алгоритма ветвей и границ для минимизации произвольной целевой функции f . Чтобы получить из этого реальный алгоритм, требуется ограничивающая функция , которая вычисляет нижние границы 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) даст алгоритм глубины . Алгоритм ветвей и границ с лучшим приоритетом можно получить, используя очередь приоритетов , которая сортирует узлы по их нижней границе. Примерами алгоритмов поиска по принципу «наилучший результат» с этой предпосылкой являются алгоритм Дейкстры и его потомок A* search . Вариант с глубиной рекомендуется, когда нет хорошей эвристики для получения начального решения, поскольку он быстро дает полные решения и, следовательно, верхние границы.

Псевдокод

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}$Алгоритмы ветвей и границ можно комбинировать с интервальным анализом. и методы подрядчиков для обеспечения гарантированного соответствия глобальному минимуму.

Приложения

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

• Целочисленное программирование
• Нелинейное программирование
• Задача коммивояжера (TSP)
• Квадратичная задача о назначениях (QAP)
• Задача максимальной выполнимости (MAX-SAT)
• Поиск ближайшего соседа ( Кейносукэ Фукунага )
• Планирование цеха потока
• Проблема с обрезкой материала
• Вычислительная филогенетика
• Установить инверсию
• Оценка параметров
• 0/1 проблема с рюкзаком
• Установить проблему с обложкой
• Выбор функций в машинном обучении
• Структурированное прогнозирование в компьютерном зрении
• Проблема с маршрутизацией дуги , включая проблему с китайским почтальоном
• Планирование талантов , проблема с организацией съемок сцен

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

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

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

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

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

Максимизировать $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$.

См. также

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

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

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