Title :

On local search for bi-objective knapsack problems

Author(s) :

Liefooghe, Arnaud [Auteur correspondant]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Paquete, Luis [Auteur]
Evolutionary and Complex Systems Group [ECOS Group]
Figueira, José [Auteur]
Operations research for Complex HybrId Decision Sytems [ORCHIDS]
Center for Management Studies, Instituto Superior Técnico [Porto Salvo] [CEG - IST]

Journal title :

Evolutionary Computation

Pages :

179-196

Publisher :

Massachusetts Institute of Technology Press (MIT Press)

Publication date :

2013

ISSN :

1063-6560

English keyword(s) :

Multi-objective combinatorial optimization
population-based local search
structural analysis
connectedness
knapsack problems

HAL domain(s) :

Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL