Show simple item record

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

hal.structure.identifierCEG-IST
dc.contributor.authorFigueira, José*
hal.structure.identifierDepartment of Informatics Engineering - DEI, University of Coimbra
dc.contributor.authorPaquete, Luis*
hal.structure.identifierDepartment of Informatics Engineering - DEI, University of Coimbra
dc.contributor.authorSimoes, Marco*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorVanderpooten, Daniel*
dc.date.accessioned2013-04-03T12:50:27Z
dc.date.available2013-04-03T12:50:27Z
dc.date.issued2013
dc.identifier.issn0926-6003
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11180
dc.language.isoenen
dc.subjectBi-objective 0-1 knapsack problems
dc.subjectMulti-objective combinatorial optimization
dc.subjectBounds sets
dc.subjectBi-objective simplex algorithm
dc.subjectDichotomic search
dc.subject.ddc003en
dc.titleAlgorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis 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.
dc.relation.isversionofjnlnameComputational Optimization and Applications
dc.relation.isversionofjnlvol56
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages97-111
dc.relation.isversionofdoi10.1007/s10589-013-9551-x
dc.relation.isversionofjnlpublisherKluwer Academic Publishers
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-10-06T09:39:38Z
hal.faultCode{"duplicate-entry":{"hal-01505666":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
cisuc2011.pdf
Size:
305.1Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record