Solving the Multidimensional Knapsack Problem Using an Evolutionary Algorithm Hybridized with Branch and Bound

J. Gallardo, C. Cotta, A. Fernández

Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach, J. Mira, J.R. Álvarez (eds.), Lecture Notes in Computer Science 3562, pp. 21-30, Springer-Verlag Berlin, 2005

© Springer-Verlag Berlin Heidelberg 2005. All rights reserved.


A hybridization of an evolutionary algorithm (EA) with the branch and bound method (BnB) is presented in this paper. Both techniques cooperate by exchanging information, namely lower bounds in the case of the EA, and partial promising solutions in the case of the BnB. The multidimensional knapsack problem has been chosen as a benchmark. To be precise, the algorithms have been tested on large problems instances from the OR-library. As it will be shown, the hybrid approach can provide high quality results, better than those obtained by the EA and the BnB on their own.

Download BibTEX entry
Download PDF version (154K)
[Back to publications page].