Введение
Оптимизация путем исключения неоптимальных решений подзадач.
Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub problems and using a bounding function to eliminate sub problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch and bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm. The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search. The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum in 1960 for discrete programming, and has become the most commonly used tool for solving NP hard optimization problems.
Метод ветвей и границ (BB, B&B или BnB) – это метод решения задач оптимизации путем разбиения их на более мелкие подзадачи и использования оценочной функции для исключения подзадач, которые не могут содержать оптимальное решение. Это парадигма разработки алгоритмов для задач дискретной и комбинаторной оптимизации, а также математической оптимизации. Алгоритм ветвей и границ состоит из систематического перебора возможных решений посредством поиска в пространстве состояний: множество возможных решений представляется в виде корневого дерева, где корень содержит полное множество решений. Алгоритм исследует ветви этого дерева, представляющие подмножества множества решений. Прежде чем перебирать возможные решения ветви, она проверяется на соответствие верхним и нижним оценочным границам оптимального решения и отбрасывается, если не может привести к лучшему решению, чем наилучшее, найденное алгоритмом на данный момент. Эффективность алгоритма зависит от точной оценки верхних и нижних границ регионов/ветвей пространства поиска. Если границы недоступны, алгоритм вырождается в полный перебор. Метод был впервые предложен Айлсой Лэнд и Элисон Доиг в ходе исследований, проводившихся в Лондонской школе экономики при спонсорской поддержке British Petroleum в 1960 году для задач дискретного программирования, и стал наиболее распространенным инструментом для решения NP-трудных задач оптимизации.
Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub problems and using a bounding function to eliminate sub problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch and bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm. The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search. The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum in 1960 for discrete programming, and has become the most commonly used tool for solving NP hard optimization problems.
Обзор
Целью алгоритма ветвей и границ является поиск значения x, которое максимизирует или минимизирует значение вещественной функции f(x), называемой целевой функцией, среди некоторого множества S допустимых или кандидатных решений. Множество S называется пространством поиска или областью допустимых решений. В остальной части раздела предполагается, что требуется минимизация f(x); это предположение не ограничивает общность, поскольку максимальное значение f(x) можно найти, найдя минимум. Алгоритм ветвей и границ работает на основе двух принципов: он рекурсивно разбивает пространство поиска на меньшие пространства, а затем минимизирует f(x) на этих меньших пространствах; это разбиение называется ветвлением. Само по себе ветвление привело бы к полному перебору кандидатных решений и их проверке. Чтобы повысить эффективность по сравнению с полным перебором, алгоритм ветвей и границ отслеживает границы для искомого минимума и использует эти границы для "отсечения" пространства поиска, исключая кандидатные решения, для которых он может доказать, что они не содержат оптимального решения. Преобразование этих принципов в конкретный алгоритм для конкретной задачи оптимизации требует некоторой структуры данных, представляющей наборы кандидатных решений. Такое представление называется экземпляром задачи. Обозначим множество кандидатных решений экземпляра I как SI. Представление экземпляра должно включать три операции:
It recursively splits the search space into smaller spaces, then minimizing f(x) on these smaller spaces; the splitting is called branching. Branching alone would amount to brute force enumeration of candidate solutions and testing them all. To improve on the performance of brute force search, a B&B algorithm keeps track of bounds on the minimum that it is trying to find, and uses these bounds to "prune" the search space, eliminating candidate solutions that it can prove will not contain an optimal solution. Turning these principles into a concrete algorithm for a specific optimization problem requires some kind of data structure that represents sets of candidate solutions. Such a representation is called an instance of the problem. Denote the set of candidate solutions of an instance I by SI. The instance representation has to come with three operations:
branch(I) produces two or more instances that each represent a subset of SI. (Typically, the subsets are disjoint to prevent the algorithm from visiting the same candidate solution twice, but this is not required. However, an optimal solution among SI must be contained in at least one of the subsets.) bound(I) computes a lower bound on the value of any candidate solution in the space represented by I, that is, bound(I) ≤ f(x) for all x in SI. solution(I) determines whether I represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among SI.) If solution(I) returns a solution then f(solution(I)) provides an upper bound for the optimal objective value over the whole space of feasible solutions. Using these operations, a B&B algorithm performs a top down recursive search through the tree of instances formed by the branch operation. Upon visiting an instance I, it checks whether bound(I) is equal or greater than the current upper bound; if so, I may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a global variable that records the minimum upper bound seen among all instances examined so far.
branch(I) создает два или более экземпляров, каждый из которых представляет подмножество SI. (Обычно подмножества не пересекаются, чтобы алгоритм не посещал одно и то же кандидатное решение дважды, но это не обязательно. Однако оптимальное решение среди SI должно содержаться хотя бы в одном из подмножеств.) bound(I) вычисляет нижнюю границу значения любого кандидатного решения в пространстве, представленном I, то есть bound(I) ≤ f(x) для всех x в SI. solution(I) определяет, представляет ли I единственное кандидатное решение. (Необязательно, если это не так, операция может выбрать для возврата некоторое допустимое решение из SI.) Если solution(I) возвращает решение, то f(solution(I)) предоставляет верхнюю границу для оптимального целевого значения по всему пространству допустимых решений. Используя эти операции, алгоритм ветвей и границ выполняет рекурсивный поиск сверху вниз по дереву экземпляров, сформированному операцией ветвления. При посещении экземпляра I он проверяет, равна ли bound(I) текущей верхней границе или превышает ее; если да, то I можно безопасно исключить из поиска, и рекурсия останавливается. Этот шаг отсечения обычно реализуется путем поддержания глобальной переменной, которая хранит минимальную верхнюю границу, обнаруженную среди всех рассмотренных экземпляров.
It recursively splits the search space into smaller spaces, then minimizing f(x) on these smaller spaces; the splitting is called branching. Branching alone would amount to brute force enumeration of candidate solutions and testing them all. To improve on the performance of brute force search, a B&B algorithm keeps track of bounds on the minimum that it is trying to find, and uses these bounds to "prune" the search space, eliminating candidate solutions that it can prove will not contain an optimal solution. Turning these principles into a concrete algorithm for a specific optimization problem requires some kind of data structure that represents sets of candidate solutions. Such a representation is called an instance of the problem. Denote the set of candidate solutions of an instance I by SI. The instance representation has to come with three operations:
branch(I) produces two or more instances that each represent a subset of SI. (Typically, the subsets are disjoint to prevent the algorithm from visiting the same candidate solution twice, but this is not required. However, an optimal solution among SI must be contained in at least one of the subsets.) bound(I) computes a lower bound on the value of any candidate solution in the space represented by I, that is, bound(I) ≤ f(x) for all x in SI. solution(I) determines whether I represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among SI.) If solution(I) returns a solution then f(solution(I)) provides an upper bound for the optimal objective value over the whole space of feasible solutions. Using these operations, a B&B algorithm performs a top down recursive search through the tree of instances formed by the branch operation. Upon visiting an instance I, it checks whether bound(I) is equal or greater than the current upper bound; if so, I may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a global variable that records the minimum upper bound seen among all instances examined so far.
Улучшения
Когда **x** является вектором, алгоритмы ветвей и границ можно комбинировать с интервальным анализом и методами контракторов для получения гарантированных оценок глобального минимума.
Связь с другими алгоритмами
Нау и др. представляют обобщение метода ветвей и границ, которое также охватывает алгоритмы поиска A*, B* и альфа-бета отсечения.