On Local Search for Bi-objective Knapsack Problems

Authors

Arnaud Liefooghe
Luis Paquete
José Figueira

Abstract

In this article, a local search approach is proposed for three variants of the bi-objective binary knapsack problem, with the aim of maximizing the total profit and minimizing the total weight. First, an experimental study on a given structural property of connectedness of the efficient set is conducted. Based on this property, a local search algorithm is proposed and its performance is compared against exact algorithms in terms of running time and quality metrics. The experimental results indicate that this simple local search algorithmis able to find a representative set of optimal solutions in most of the cases, and in much less time than exact algorithms.

Journal

Evolutionary Computation, Vol. 21, #1, pp. 179-196, MIT Press, January 2013

Cited by

Year 2014 : 1 citations

I Yevseyeva, AP Guerreiro, MTM Emmerich, C. Fonseca, A Portfolio Optimization Approach to Selection in Multiobjective Evolutionary Algorithms, Parallel Problem Solving from Nature – PPSN XIII, Lecture Notes in Computer Science Volume 8672, 2014, pp 672-681