Connectedness and Local Search for Bicriteria Knapsack Problems

Authors

Abstract

This article reports an experimental study on a given struc- tural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal so- lutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.

Conference

11th European Conference on Evolutionary Computation in Combinatorial Optimisation 2011

DOI