On Beam Search for Multicriteria Combinatorial Optimization Problems

Authors

Abstract

In this article, the beam search approach is extended to multicriteria
combinatorial optimization, with particular emphasis on its
application to bicriteria {0,1} knapsack problems. The beam search
uses several definitions of upper bounds of knapsack solutions as well
as a new selection procedure based on \epsilon-indicator that allows
to discard uninteresting solutions. An in-depth experimental analysis
on a wide benchmark set of instances suggests that this approach can
achieve very good solution quality in a small fraction of time needed
to solve the problem to optimality by state-of-the-art algorithms.

Keywords

Multiobjective optimization, metaheuristics, knapsack problems

Subject

Multiobjective optimization, metaheuristics, knapsack problems

Conference

9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012), LNCS 7298, 307-321, Springer, August 2012