Branch-and-Bound Methods

This chapter describes the principles of branch and bound in combinatorial optimization and gives details of one of its applications. Branch-and-bound methods belong to the category of exact methods: they provide one or all of the optimal solutions of the considered instance for various optimization problems. Practical use of a branch-and-bound method requires the specification of several ingredients; a general description is given in the chapter, while it describes them for the binary knapsack problem. The chapter concludes by giving some variants of branch-and-bound methods. The binary knapsack problem is a classic example of an NP-hard problem and branch-and-bound methods belong to the usual methods applied to solve this problem.