Optimization Techniques for Solving Complex Problems

CHAPTER 21

Exact, Metaheuristic, and Hybrid Approaches to Multidimensional Knapsack Problems

J. E. GALLARDO, C. COTTA, and A. J. FERNÁNDEZ

Universidad de Málaga, Spain

21.1 INTRODUCTION

In this chapter we review our recent work on applying hybrid collaborative techniques that integrate branch and bound (B&B) and memetic algorithms (MAs) in order to design effective heuristics for the multidimensional knapsack problem (MKP). To this end, let us recall that branch and bound (B&B) [102] is an exact algorithm for finding optimal solutions to combinatorial problems that works basically by producing convergent lower and upper bounds for the optimal solution using an implicit enumeration scheme. A different approach to optimization is provided by evolutionary algorithms (EAs) [2–4]. These are powerful heuristics for optimization problems based on principles of natural evolution: namely, adaptation and survival of the fittest. Starting from a population of randomly generated individuals (representing solutions), a process consisting of selection (promising solutions are chosen from the population), reproduction (new solutions are created by combining selected ones), and replacement (some solutions are replaced by new ones) is repeated. A fitness function measuring the quality of the solution is used to guide the process.

A key aspect of EAs is robustness, meaning that they can be deployed ...