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

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

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

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

Обзор

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

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

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

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

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

Общая версия

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

Псевдокод

A 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) и $bound$ ( lower_bound_function) рассматриваются как записанные объекты функций и могут соответствовать лямбда-выражениям , указателям на функции или функторам на языке программирования C ++, среди других типов вызываемых объектов .

Улучшения

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

Приложения

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

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

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

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

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

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

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

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

Languages

In other projects