Branch-and-bound algorithm

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