On Beam Search for Multicriteria Combinatorial Optimization Problems

摘要

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 ε-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.