next up previous contents index
Next: The Optimization of the Up: The Subproblem Previous: The Other Nodes of

Branch-and-Bound

A linear-programming based branch-and-bound algorithm in its simpliest form is obtained if linear programming relaxations in each subproblem are solved that are neither enhanced by the generation of cutting planes nor by the dynamic generation of variables. Such an algorithm requires only two problem specific functions: one to check if a given LP-solution is a feasible solution of the optimization problem, and one for the generation of the sons.

The first function is problem specific, because, if constraints of the integer programming formulation are violated, the condition that all discrete variables have integer values is not sufficient. Therefore, for safety this function is declared pure virtual.

The second required problem specific function is usually only a one-liner, which returns the problem specific subproblem generated by a branching rule.

Hence, the implementation of a pure branch-and-bound algorithm does not require very much effort.



Stefan Thienel
Fri Sep 19 11:32:54 MET DST 1997