An object oriented approach to generic branch and bound

Branch and bound algorithms can be characterized by a small set of basic rules that are applied in a divide-and-conquer-like framework. The framework is about the same in all applications, whereas the specification of the rules is problem dependent. Building a framework is a rather simple task in sequential implementations, but must not be underestimated in the parallel case, especially if an efficient branch and bound algorithm is required. In generic branch and bound models, the basic rules can be clearly identified within the framework, and, hence, it can be developed independently from the application. Furthermore, it gives the user the opportunity to concentrate on the actual problem to be solved, without being distracted by user-irrelevant issues like the properties of the underlying architecture. In this paper, we will discuss an object oriented approach to generic branch and bound. We will show how object orientation can help us to build a flexible branch and bound framework, that is able to perform like any branch and bound algorithm that fits into some powerful taxonomies known from the literature. We will define an interface for the specification of the problem dependent parts, and we will give a first indication of how the user can tune the framework if a non-default behavior is desired.