Bob++: Framework for Solving Optimization Problems with Branch-and-Bound methods

Abstract

This paper describes the design of Bob++, a framework for implementing sequential and/or parallel search algorithms. To our knowledge, the Bob++ is among the rare frameworks that allow implementation of various search methods (B&B, D&C (divide-and-conquer), DP (dynamic programming), A*) for general COPs and run the application on any architecture (sequential/SMP machines, clusters/grids) with minimum modification in the source code. The Bob++ is based on the notion of global priority queue that encapsulates sequential data structures and load balancing strategies. This makes transparent the parallelizations of the search algorithms. To parallelize Bob++ library, we integrated it on Athapascan parallel programming interface which is a C++ library developed by the INRIA Apache project