• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem

Thumbnail
View/Open
cisuc2011.pdf (305.1Kb)
Date
2013
Dewey
Recherche opérationnelle
Sujet
Bi-objective 0-1 knapsack problems; Multi-objective combinatorial optimization; Bounds sets; Bi-objective simplex algorithm; Dichotomic search
Journal issue
Computational Optimization and Applications
Volume
56
Number
1
Publication date
2013
Article pages
97-111
Publisher
Kluwer Academic Publishers
DOI
http://dx.doi.org/10.1007/s10589-013-9551-x
URI
https://basepub.dauphine.fr/handle/123456789/11180
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Figueira, José
123139 CEG-IST
Paquete, Luis
264911 Department of Informatics Engineering - DEI, University of Coimbra
Simoes, Marco
264911 Department of Informatics Engineering - DEI, University of Coimbra
Vanderpooten, Daniel
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
This paper presents several methodological and algorithmic improvements over a state-of-the-art dynamic programming algorithm for solving the bi-objective {0,1} knapsack problem. The variants proposed make use of new definitions of lower and upper bounds, which allow a large number of states to be discarded. The computation of these bounds are based on the application of dichotomic search, definition of new bound sets, and bi-objective simplex algorithms to solve the relaxed problem. Although these new techniques are not of a common application for dynamic programming, we show that the best variants tested in this work can lead to an average improvement of 10 to 30 % in CPU-time and significant less memory usage than the original approach in a wide benchmark set of instances, even for the most difficult ones in the literature.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.