Namespaces
Variants
Actions

Difference between revisions of "Branch-and-bound algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
b1108401.png
 +
$#A+1 = 57 n = 0
 +
$#C+1 = 57 : ~/encyclopedia/old_files/data/B110/B.1100840 Branch\AAhand\AAhbound algorithm
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
Consider a (mixed) integer [[Linear programming|linear programming]] problem
 
Consider a (mixed) integer [[Linear programming|linear programming]] problem
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108401.png" /></td> </tr></table>
+
$$
 +
v ( P ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108402.png" /></td> </tr></table>
+
$$
 +
=  
 +
{ \mathop{\rm min} } _ {x \geq  0 } \left \{ {c  ^ {T} x } : {Ax \geq  b, x _ {j} \in \mathbf Z, j \in N  ^  \prime  \subset  \{ 1 \dots n \} } \right \} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108403.png" /> is the set of variables that are required to be integer, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108404.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108405.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108406.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108407.png" />-matrix. For convenience and without loss of generality, assume that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108408.png" /> is bounded. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b1108409.png" /> be the feasible set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084011.png" /> the set of optimal solutions, i.e.,
+
where $  N  ^  \prime  $
 +
is the set of variables that are required to be integer, $  x,c \in \mathbf R  ^ {n} $,  
 +
b \in \mathbf R  ^ {m} $,  
 +
and $  A $
 +
is an $  ( m \times n ) $-
 +
matrix. For convenience and without loss of generality, assume that $  P $
 +
is bounded. Let $  F ( P ) $
 +
be the feasible set of $  P $
 +
and $  F  ^ {*} ( P ) $
 +
the set of optimal solutions, i.e.,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084012.png" /></td> </tr></table>
+
$$
 +
F ( P ) = \left \{ {x \in \mathbf R  ^ {n} } : {Ax \geq  b, x \geq  0, x _ {j} \in \mathbf Z, j \in N  ^  \prime  } \right \} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084013.png" /></td> </tr></table>
+
$$
 +
F  ^ {*} ( P ) = \left \{ {x  ^ {*} \in F ( P ) } : {c  ^ {T} x  ^ {*} = { \mathop{\rm min} } _ {x \in F ( P ) } c  ^ {T} x } \right \} .
 +
$$
  
 
In branch-and-bound methods, the above problem is split up into a number of subproblems by partitioning the feasible set in some way. These subproblems are examined in turn and can be further split up. This is the branching part. Bounds on the optimal values of the subproblems are used to discard certain subproblems as irrelevant, or to perform a further decomposition.
 
In branch-and-bound methods, the above problem is split up into a number of subproblems by partitioning the feasible set in some way. These subproblems are examined in turn and can be further split up. This is the branching part. Bounds on the optimal values of the subproblems are used to discard certain subproblems as irrelevant, or to perform a further decomposition.
  
In somewhat more detail, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084014.png" /> be the current list of subproblems, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084015.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084016.png" /> be the currently best point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084017.png" />, the incumbent, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084018.png" /> the currently best value, sometimes called the cutting value. The process is begun from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084021.png" />.
+
In somewhat more detail, let $  L = \{ P _ {1} \dots P _ {r} \} $
 +
be the current list of subproblems, $  v ( P _ {i} ) = { \mathop{\rm min} } \{ {c  ^ {T} x } : {A _ {i} x \geq  b _ {i} , x \geq  0, x _ {j} \in \mathbf Z, j \in N  ^  \prime  } \} $.  
 +
Let $  x  ^ {*} $
 +
be the currently best point of $  v ( P ) $,  
 +
the incumbent, and $  z  ^ {*} = c  ^ {T} x  ^ {*} $
 +
the currently best value, sometimes called the cutting value. The process is begun from $  z  ^ {*} = \infty $,  
 +
$  x  ^ {*} = \textrm{ unknown  } $,  
 +
$  L = \{ P \} $.
  
Now take a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084022.png" /> and consider its linear programming relaxation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084023.png" />:
+
Now take a $  P _ {i} $
 +
and consider its linear programming relaxation $  {\overline{P}\; } _ {i} $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084024.png" /></td> </tr></table>
+
$$
 +
v ( {\overline{P}\; } _ {i} ) = { \mathop{\rm min} } \left \{ {c  ^ {T} x } : {A _ {i} x \geq  b _ {i} ,x \geq 0 } \right \} ,
 +
$$
  
obtained by discarding the integrality constraint. Solve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084025.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084026.png" />, no point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084027.png" /> does better than any already obtained, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084028.png" /> can be discarded. One says that in this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084029.png" /> has been fathomed.
+
obtained by discarding the integrality constraint. Solve $  {\overline{P}\; } _ {i} $.  
 +
If $  v ( {\overline{P}\; } _ {i} ) \geq  z  ^ {*} $,  
 +
no point of $  F ( P _ {i} ) $
 +
does better than any already obtained, and $  P _ {i} $
 +
can be discarded. One says that in this case $  P _ {i} $
 +
has been fathomed.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084030.png" />, there are two subcases:
+
If $  v ( {\overline{P}\; } _ {i} ) < z  ^ {*} $,  
 +
there are two subcases:
  
a) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084032.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084033.png" /> is optimal in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084035.png" /> has also been fathomed. The new values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084037.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084039.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084040.png" /> is discarded.
+
a) $  {\overline{x}\; } \in F  ^ {*} ( {\overline{P}\; } _ {i} ) $
 +
and $  {\overline{x}\; } \in F ( P ) $.  
 +
Then $  {\overline{x}\; } $
 +
is optimal in $  F ( P _ {i} ) $
 +
and $  P _ {i} $
 +
has also been fathomed. The new values of $  x  ^ {*} $
 +
and $  z  ^ {*} $
 +
are $  {\overline{x}\; } $
 +
and $  c  ^ {T} {\overline{x}\; } $,  
 +
and $  P _ {i} $
 +
is discarded.
  
b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084042.png" /> (i.e., an integrality constraint is violated). Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084043.png" /> is split up into certain subproblems, which are added to the list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084045.png" /> is removed and the incumbent and cutting value remain the same.
+
b) $  {\overline{x}\; } \in F  ^ {*} ( {\overline{P}\; } _ {i} ) $
 +
and $  {\overline{x}\; } \notin F ( P ) $(
 +
i.e., an integrality constraint is violated). Then $  P _ {i} $
 +
is split up into certain subproblems, which are added to the list $  L $,  
 +
$  P _ {i} $
 +
is removed and the incumbent and cutting value remain the same.
  
The algorithm ends when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084046.png" />.
+
The algorithm ends when $  L = \emptyset $.
  
This description does not yet say anything about how to split up a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084047.png" />. One method often used is to pick a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084048.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084049.png" /> is not integral and to split up <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084050.png" /> into the two subproblems defined by the respective constraints:
+
This description does not yet say anything about how to split up a $  P _ {i} $.  
 +
One method often used is to pick a $  j \in N  ^  \prime  $
 +
for which $  {\overline{x}\; } _ {j} $
 +
is not integral and to split up $  P _ {i} $
 +
into the two subproblems defined by the respective constraints:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084051.png" /></td> </tr></table>
+
$$
 +
x _ {j} \geq  [ x _ {j} ] + 1,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084052.png" /></td> </tr></table>
+
$$
 +
x _ {j} \leq  [ x _ {j} ] ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084053.png" /> denotes the entier (or [[Integral part|integral part]]) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084054.png" />, the largest integer less than or equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084055.png" />.
+
where $  [ x _ {j} ] $
 +
denotes the entier (or [[Integral part|integral part]]) of $  x _ {j} $,  
 +
the largest integer less than or equal to $  x _ {j} $.
  
In the above, the linear programming relaxation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084056.png" /> has been used to obtain bounds on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084057.png" />. This can be replaced with other ideas, e.g., [[Lagrangean relaxation|Lagrangean relaxation]].
+
In the above, the linear programming relaxation $  {\overline{P}\; } _ {i} $
 +
has been used to obtain bounds on $  v ( P _ {i} ) $.  
 +
This can be replaced with other ideas, e.g., [[Lagrangean relaxation|Lagrangean relaxation]].
  
 
In [[#References|[a5]]], there is a useful flow chart of branch and bound. The branch-and-bound idea was introduced in [[#References|[a1]]] and improved in [[#References|[a2]]]. Some standard references are [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]].
 
In [[#References|[a5]]], there is a useful flow chart of branch and bound. The branch-and-bound idea was introduced in [[#References|[a1]]] and improved in [[#References|[a2]]]. Some standard references are [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]].

Latest revision as of 06:29, 30 May 2020


Consider a (mixed) integer linear programming problem

$$ v ( P ) = $$

$$ = { \mathop{\rm min} } _ {x \geq 0 } \left \{ {c ^ {T} x } : {Ax \geq b, x _ {j} \in \mathbf Z, j \in N ^ \prime \subset \{ 1 \dots n \} } \right \} , $$

where $ N ^ \prime $ is the set of variables that are required to be integer, $ x,c \in \mathbf R ^ {n} $, $ b \in \mathbf R ^ {m} $, and $ A $ is an $ ( m \times n ) $- matrix. For convenience and without loss of generality, assume that $ P $ is bounded. Let $ F ( P ) $ be the feasible set of $ P $ and $ F ^ {*} ( P ) $ the set of optimal solutions, i.e.,

$$ F ( P ) = \left \{ {x \in \mathbf R ^ {n} } : {Ax \geq b, x \geq 0, x _ {j} \in \mathbf Z, j \in N ^ \prime } \right \} , $$

$$ F ^ {*} ( P ) = \left \{ {x ^ {*} \in F ( P ) } : {c ^ {T} x ^ {*} = { \mathop{\rm min} } _ {x \in F ( P ) } c ^ {T} x } \right \} . $$

In branch-and-bound methods, the above problem is split up into a number of subproblems by partitioning the feasible set in some way. These subproblems are examined in turn and can be further split up. This is the branching part. Bounds on the optimal values of the subproblems are used to discard certain subproblems as irrelevant, or to perform a further decomposition.

In somewhat more detail, let $ L = \{ P _ {1} \dots P _ {r} \} $ be the current list of subproblems, $ v ( P _ {i} ) = { \mathop{\rm min} } \{ {c ^ {T} x } : {A _ {i} x \geq b _ {i} , x \geq 0, x _ {j} \in \mathbf Z, j \in N ^ \prime } \} $. Let $ x ^ {*} $ be the currently best point of $ v ( P ) $, the incumbent, and $ z ^ {*} = c ^ {T} x ^ {*} $ the currently best value, sometimes called the cutting value. The process is begun from $ z ^ {*} = \infty $, $ x ^ {*} = \textrm{ unknown } $, $ L = \{ P \} $.

Now take a $ P _ {i} $ and consider its linear programming relaxation $ {\overline{P}\; } _ {i} $:

$$ v ( {\overline{P}\; } _ {i} ) = { \mathop{\rm min} } \left \{ {c ^ {T} x } : {A _ {i} x \geq b _ {i} ,x \geq 0 } \right \} , $$

obtained by discarding the integrality constraint. Solve $ {\overline{P}\; } _ {i} $. If $ v ( {\overline{P}\; } _ {i} ) \geq z ^ {*} $, no point of $ F ( P _ {i} ) $ does better than any already obtained, and $ P _ {i} $ can be discarded. One says that in this case $ P _ {i} $ has been fathomed.

If $ v ( {\overline{P}\; } _ {i} ) < z ^ {*} $, there are two subcases:

a) $ {\overline{x}\; } \in F ^ {*} ( {\overline{P}\; } _ {i} ) $ and $ {\overline{x}\; } \in F ( P ) $. Then $ {\overline{x}\; } $ is optimal in $ F ( P _ {i} ) $ and $ P _ {i} $ has also been fathomed. The new values of $ x ^ {*} $ and $ z ^ {*} $ are $ {\overline{x}\; } $ and $ c ^ {T} {\overline{x}\; } $, and $ P _ {i} $ is discarded.

b) $ {\overline{x}\; } \in F ^ {*} ( {\overline{P}\; } _ {i} ) $ and $ {\overline{x}\; } \notin F ( P ) $( i.e., an integrality constraint is violated). Then $ P _ {i} $ is split up into certain subproblems, which are added to the list $ L $, $ P _ {i} $ is removed and the incumbent and cutting value remain the same.

The algorithm ends when $ L = \emptyset $.

This description does not yet say anything about how to split up a $ P _ {i} $. One method often used is to pick a $ j \in N ^ \prime $ for which $ {\overline{x}\; } _ {j} $ is not integral and to split up $ P _ {i} $ into the two subproblems defined by the respective constraints:

$$ x _ {j} \geq [ x _ {j} ] + 1, $$

$$ x _ {j} \leq [ x _ {j} ] , $$

where $ [ x _ {j} ] $ denotes the entier (or integral part) of $ x _ {j} $, the largest integer less than or equal to $ x _ {j} $.

In the above, the linear programming relaxation $ {\overline{P}\; } _ {i} $ has been used to obtain bounds on $ v ( P _ {i} ) $. This can be replaced with other ideas, e.g., Lagrangean relaxation.

In [a5], there is a useful flow chart of branch and bound. The branch-and-bound idea was introduced in [a1] and improved in [a2]. Some standard references are [a3], [a4], [a5], [a6].

References

[a1] A.H. Land, A.G. Doig, "An automatic method for solving discrete programming problems" Econometrica , 28 (1960) pp. 497–520
[a2] R.J. Dakin, "A tree-search algorithm for mixed integer programming problems" Comp. J. , 8 (1965) pp. 250–255
[a3] C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization" , Prentice-Hall (1982)
[a4] S. Walukiewicz, "Integer programming" , Kluwer Acad. Publ. (1991)
[a5] S. Zionts, "Linear and integer programming" , Prentice-Hall (1974)
[a6] G.L. Nemhauser, L.A. Wolsey, "Integer programming" G.L. Nemhauser (ed.) A.H.G. Rinnooy Kan (ed.) M.J. Todd (ed.) , Optimization , North-Holland (1989) pp. 447–528
How to Cite This Entry:
Branch-and-bound algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Branch-and-bound_algorithm&oldid=17467
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article