MPI and OpenMP implementations of branch-and-bound skeletons

Publisher Summary This chapter describes two skeletons to solve optimization problems using the branch-and-bound technique. Sequential and parallel code of the invariant part of the solvers is provided. The implementation of the skeletons is in C++, and is divided into two different parts: one, that implements the resolution pattern provided by the library, and the second part, which the user has to complete with the particular characteristics of the problem to solve. This second part is used by the resolution pattern and acts as a link. Required classes are used to store the basic data of the algorithm. The solvers are implemented by provided classes. There is one skeleton in the class hierarchy, which is implemented using MPI, and another one using OpenMP. Once the user has represented the problem, two parallel solvers are obtained without any additional effort: one, using the message passing paradigm, and other with the shared memory one. An algorithm for the resolution of the classic 0–1 knapsack problem has been implemented using the skeleton proposed. The obtained computational results using an Origin 3000 are discussed in the chapter.