Branch-and-Bound

Branch and bound (Engl. Branching and barrier or branching and limit ) is in the area of operations research mathematical method frequently used whose aim is for a given integer optimization problem to find a best solution. Branch-and-bound leads to a decision tree , but is not a special procedure itself, but a treatment method, a meta-procedure. For specific combinatorial optimization problems, accordingly adapted branch-and-bound algorithms result .

The principle

In the optimization problem with, let the admissible range be a discrete set, possibly even finite. Trying through all permitted assignments usually fails due to unacceptably long computing times. Therefore, it is gradually split into several subsets (branch). By means of suitable bounds, many suboptimal occupancies are to be recognized and sorted out early on, so that the solution space to be searched is kept small. In the worst case, all assignments are listed (complete enumeration). ${\displaystyle f(x)\to \min !}$ ${\displaystyle x\in D}$ ${\displaystyle D}$ ${\displaystyle x\in D}$ ${\displaystyle D}$

Branch, the branch

The division step ( branch step) serves to divide the problem at hand into two or more sub-problems, which represent a simplification of the original problem. A tree structure is created by executing the splitting step recursively for the sub-problems obtained. There are different selection methods for choosing the next node to be processed in the distribution tree, which have different objectives. Two commonly used methods are described below:

• Depth-first search : Of the sub-problems that have not yet been dealt with, the one that was inserted last is selected ( Last In - First Out ). With this selection rule, the procedure in the tree works its way down as quickly as possible, so that a permissible solution is generally obtained very quickly, but nothing can be said about its quality.

• Breadth-first search : Of the sub-problems that have not yet been processed, the one that was inserted first into the tree is selected ( First In - First Out ). When using this selection rule, the nodes in the tree are processed for each level before lower-lying nodes are considered. A valid solution is usually received relatively late, but it tends to have a good solution value. This strategy also tends to lead to useful lower bounds early on.

The procedures can be combined. A first solution can be determined, for example, with a depth-first search in order to then have a global upper or lower limit in a subsequent breadth-first search.

Bound, the barrier

The Bound step has the task of " cutting off " certain branches of the tree , i.e. H. Not to be considered in the further calculation in order to limit the computational effort. The algorithm achieves this by calculating and comparing the upper and lower bound:

• Upper bounds ( upper bound ) result from each feasible solution. A heuristic can be used beforehand if necessary.
• To get good lower bounds ( lower bound ) to find, often one is relaxation used. This is a on a set defined, easy function to be calculated with for all . The relaxed problem with is easily solvable and has an optimal solution . Then applies to everyone . At is also the optimal solution to the problem that is not relaxed. ${\displaystyle E\supseteq D}$ ${\displaystyle g}$ ${\displaystyle g(x)\leq f(x)}$ ${\displaystyle x\in D}$ ${\displaystyle g(x)\to \min !}$ ${\displaystyle x\in E}$ ${\displaystyle {\bar {x}}}$ ${\displaystyle f(x)\geq g({\bar {x}})}$ ${\displaystyle x\in D}$ ${\displaystyle {\bar {x}}\in D\land f({\bar {x}})=g({\bar {x}})}$ ${\displaystyle {\bar {x}}}$

These considerations are also applicable to sub-problems, where the set has already been split up. If you already know a feasible solution and if the lower bound for a sub-problem is greater than , then you do not need to investigate that sub-problem further because it does not yield an optimal solution. ${\displaystyle D}$ ${\displaystyle {\hat {x}}\in D}$ ${\displaystyle f({\hat {x}})}$

Dominance

Of dominance occurs when for each assignment of a subset of a non inferior feasible solution can be constructed. If not all optimal solutions are sought, but only one, then the search is superfluous , even if the barriers alone are not sufficient to exclude them from further screening. This sometimes increases the efficiency of the method considerably, for example in the case of the multidimensional cutting problem , although dominance tests are not part of the original branch-and-bound method. ${\displaystyle {\tilde {x}}}$ ${\displaystyle T\subset D}$ ${\displaystyle {\bar {x}}\in D\setminus T}$ ${\displaystyle T}$ ${\displaystyle T}$

Example: if to be solved. A lower bound is obtained immediately by all summands are estimated down, so . Applying branch-and-bound without considerations of dominance proves to be unnecessarily time-consuming. Because is to choose as small as possible, no matter how big it is, that is . For will ; at is and therefore not optimal. The only optimal solution is . ${\displaystyle z=x_{1}-x_{2}-x_{1}/x_{2}\to \min !}$ ${\displaystyle x_{1},x_{2}\in \{2,3,4,5\}}$ ${\displaystyle 2-5-5/2=-5{,}5}$ ${\displaystyle z=x_{1}*(1-1/x_{2})-x_{2}\geq x_{1}/2-x_{2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}=2}$ ${\displaystyle x_{2}=5}$ ${\displaystyle z=-3{,}4}$ ${\displaystyle x_{2}\leq 4}$ ${\displaystyle z>-3}$ ${\displaystyle x_{1}=2,\;x_{2}=5}$

Applied to problems of integer linear optimization

The general integer linear optimization problem has the form

• Maximize ${\displaystyle G=a\cdot x}$
• under the constraint and ${\displaystyle A\cdot x\leq b}$ ${\displaystyle x\in \mathbb {N} _{0}^{n}}$
• With
  • A : m × n matrix
  • x : n-dimensional vector
  • a : n-dimensional vector
  • b : m-dimensional vector
  • a · x : scalar product, linear function with n variables, real value
  • Ax  : m-dimensional vector that arises as a matrix-vector product of the matrix A with the n-dimensional vector x .

By neglecting the integer conditions one obtains the continuous relaxation , which can be solved with the simplex method . Because of the required integers, the initial problem does not belong to the linear optimization problems.

Solution

The problem can be solved with the help of the branch-and-bound method. First, the best objective function value so far is set and the integer condition is omitted: ${\displaystyle {\hat {G}}:=-\infty }$

• Maximize ${\displaystyle G=a\cdot x}$
• under the constraints and . ${\displaystyle A\cdot x\leq b}$ ${\displaystyle x\geq 0}$

We call the resulting problem P ₀ . This now linear optimization problem is solved with the simplex method. In general, the solution obtained will not be an integer; H. are not consistently integers. Without loss of generality, this would also apply. ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle x_{1}}$

Now one tries to find solutions with integers . Let the largest integer be less than . Then formulated to two new linear optimization problems and such that the solution is found before each excluded: ${\displaystyle x_{1}}$ ${\displaystyle s_{1}}$ ${\displaystyle x_{1}}$ ${\displaystyle P_{11}}$ ${\displaystyle P_{12}}$

• ${\displaystyle P_{11}}$ - Maximize ${\displaystyle G=a\cdot x}$
• under the constraints

  ${\displaystyle A\cdot x\leq b}$

  ${\displaystyle x\geq 0}$

  ${\displaystyle x_{1}\leq s_{1}}$

• ${\displaystyle P_{12}}$ - Maximize ${\displaystyle G=a\cdot x}$
• under the constraints

  ${\displaystyle A\cdot x\leq b}$

  ${\displaystyle x\geq 0}$

  ${\displaystyle x_{1}\geq s_{1}+1}$

Such a division into sub-problems is called a branch .

Both sub-problems are solved with the dual simplex method. The following cases can occur:

1. The allowable area becomes empty.
2. One finds an integer optimal solution for the sub-problem.
3. ${\displaystyle x_{1}}$becomes an integer, but not another one, regardless of whether that was an integer before or not. ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$

In case (1) the sub-problem is solved. In the other cases, this also applies if is and only one optimal solution is or is and all optimal solutions are sought. Otherwise, in case (2) the solution found is saved as the best so far and replaced by , while in case (3) the sub-problem has to be split up further. ${\displaystyle G\leq {\hat {G}}}$ ${\displaystyle G<{\hat {G}}}$ ${\displaystyle {\hat {G}}}$ ${\displaystyle G}$

In this way, the entire solution space is searched and an optimal solution is found, if there is one and the process was not terminated prematurely. It is quite possible that, despite an exhaustive search, you will not find a solution. Then the initial problem has no feasible solutions.

example

The process is demonstrated on the basis of a specific task.

The starting problem is:

• Maximize ${\displaystyle G=x_{1}+x_{2}}$
• with the constraints

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

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

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

We leave out the integer condition and find the optimal solution with the simplex method

• ${\displaystyle G={\frac {7}{3}}}$
• ${\displaystyle x_{1}={\frac {5}{3}}}$
• ${\displaystyle x_{2}={\frac {2}{3}}}$

We continue with the goal of finding an integer solution . For this purpose, we create 2 further optimization tasks, one with the additional secondary condition , the other with . ${\displaystyle x_{1}}$ ${\displaystyle x_{1}\leq 1}$ ${\displaystyle x_{1}\geq 2}$

• ${\displaystyle P_{11}}$ - Maximize ${\displaystyle G=x_{1}+x_{2}}$
• with the constraints

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

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

  ${\displaystyle x_{1}\leq 1}$

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

• ${\displaystyle P_{12}}$ - Maximize ${\displaystyle G=x_{1}+x_{2}}$
• with the constraints

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

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

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

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

The problem has the solution ${\displaystyle P_{11}}$

• ${\displaystyle G=2}$
• ${\displaystyle x_{1}=1}$
• ${\displaystyle x_{2}=1}$

Since and are integers, this is a feasible solution to the initial problem. But we don't yet know whether there is a better solution. ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

To do this, we solve the problem and get: ${\displaystyle P_{12}}$

• ${\displaystyle G=2}$
• ${\displaystyle x_{1}=2}$
• ${\displaystyle x_{2}=0}$

This is also a feasible solution because of the integers. Since both for and for the objective function take on the value , the problem has two optimal solutions. ${\displaystyle P_{11}}$ ${\displaystyle P_{12}}$ ${\displaystyle G=2}$

Evaluation of the procedure

With the branch-and-bound method, several - in unfavorable cases very many - optimization problems must be saved, managed and solved with the help of the simplex method . Particularly in the case of major problems that can have several hundred thousand variables and constraints, this leads to high computing and memory costs. Instead, one avoids the disadvantage of Gomory's cutting plane method, in which numerical problems make it difficult to find a solution due to the lack of accuracy of the number representation in the computer . In practice, both methods are often combined to branch-and-cut when solving integer optimization problems . Cutting planes are separated in the root node and sometimes also in other nodes of the branch-and-bound tree in order to intensify the linear relaxation.

history

The idea of ​​branch-and-bound was first formulated in 1960 by AH Land and AG Doig in the field of operations research. RJ Dakin gave an algorithm that was easy to implement in 1965.

literature

• RJ Dakin: A tree-search algorithm for mixed integer programming problems . In: The Computer Journal , Volume 8, 1965, pp. 250-255 comjnl.oxfordjournals.org

Individual evidence

1. ^ AH Land and AG Doig. An automatic method of solving discrete programming problems . In: Econometrica , Vol. 28 (1960), No. 3, 497-520, doi: 10.2307 / 1910129 .