A hybrid model of evolutionary algorithms and branch-and-bound for combinatorial optimization problems

Branch-and-bound and evolutionary algorithms represent two very different approaches for tackling combinatorial optimization problems. These approaches are not incompatible though. In this paper, we consider a hybrid model that combines these two techniques. To be precise, it is based on the interleaved execution of both approaches, and has a heuristic nature. The multidimensional 0-1 knapsack problem has been chosen as benchmark. As it is shown, the hybrid algorithm can produce better results at the same computational cost, especially for larger problem instances.