On local search for bi-objective knapsack problems - Laboratoire d'Informatique Fondamentale de Lille
Journal Articles Evolutionary Computation Year : 2013

On local search for bi-objective knapsack problems

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 algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact algorithms.
Fichier principal
Vignette du fichier
liefooghe_ecj2013.pdf (248.31 Ko) Télécharger le fichier
Origin Publisher files allowed on an open archive

Dates and versions

hal-00676625 , version 1 (02-03-2023)

Identifiers

Cite

Arnaud Liefooghe, Luis Paquete, José Rui Figueira. On local search for bi-objective knapsack problems. Evolutionary Computation, 2013, 21 (1), pp.179-196. ⟨10.1162/EVCO_a_00074⟩. ⟨hal-00676625⟩
266 View
64 Download

Altmetric

Share

More