View source for Branch-and-bound algorithm

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>

<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>

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.,

<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>

<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>

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" />.

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" />:

<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>

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.

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084030.png" />, 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.

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.

The algorithm ends when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b110/b110840/b11084046.png" />.

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:

<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>

<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>

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" />.

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 [[#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]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.H. Land,   A.G. Doig,   "An automatic method for solving discrete programming problems"  ''Econometrica'' , '''28'''  (1960)  pp. 497–520</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.J. Dakin,   "A tree-search algorithm for mixed integer programming problems"  ''Comp. J.'' , '''8'''  (1965)  pp. 250–255</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  C.H. Papadimitriou,   K. Steiglitz,   "Combinatorial optimization" , Prentice-Hall  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  S. Walukiewicz,   "Integer programming" , Kluwer Acad. Publ.  (1991)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  S. Zionts,   "Linear and integer programming" , Prentice-Hall  (1974)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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</TD></TR></table>