Bob++: a Framework for Exact Combinatorial Optimization Methods on Parallel Machines

Abstract — The aim of this article is to propose the object-oriented design of the Bob++ framework. Bob++ is a framework for implementing solvers for combinatorial optimization problems on parallel and se-quential machines. Several similar frameworks have been proposed in the last decade but each of them only focuses in one method, said Branch-and-Bound, Divide-and-Conquer, etc.. and proposes also one paralleliza-tion, which is very difficult to extend. We propose a software design where: first, several exact combinatorial optimization methods are made available to the user to solve a problem, and second, an interface to facilitate the implementation of a parallelization is also provided. Parallelizations may use POSIX threads as well as MPI, or more specialized libraries such as Athapascan/Kaapi. Keywords—Combinatorial Optimization, Search algo