Branch-and-Bound Methods

Eva K. Lee

ABSTRACT

In this article the classical branch-and-bound approach for solving integer programming problems is described. Various branching variable selection and node selection schemes are discussed; and the techniques of problem preprocessing and reformulation, heuristics, and continuous reduced-cost fixing are outlined. These latter techniques have been shown to be very effective when embedded within a branch-and-bound algorithm. The use of an interior-point method as a subproblem solver is also described. Finally, Lagrangian relaxation is analyzed as an alternative relaxation for use within the branch-and-bound tree search environment.