Solving knapsack problems using Divide and Conquer and Branch and Bound methods

This paper presents the MaLLBa library. This library provides skeletons to solve combinatorial optimization problems using exact, heuristic and hybrid techniques. The user must choose a paradigm and for it must establish the problem and solution types and the specific characteristics of the technique using the C++ language. This information is combined with the skeletons provided by the library to obtain two programs: one sequential and the other parallel. To exploit parallelism on Linux workstations, MaLLBa uses the Message Passing paradigm. This work is centered to present the Divide and Conquer and Branch and Bound skeletons. Concretely both of them will be applied to solve the Integer Knapsack Problem. Finally, the obtained computational results will be presented.