Show simple item record

An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorFurini, Fabio
hal.structure.identifier
dc.contributor.authorLjubić, Ivana
hal.structure.identifierDepartment of Statistics and Operations Research
dc.contributor.authorSinnl, Markus
dc.date.accessioned2019-04-12T13:55:34Z
dc.date.available2019-04-12T13:55:34Z
dc.date.issued2017
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18639
dc.language.isoenen
dc.subjectCombinatorial optimizationen
dc.subjectMaximal knapsack packingen
dc.subjectMinimal knapsack coveren
dc.subjectDynamic programmingen
dc.subjectInteger programmingen
dc.subject.ddc003en
dc.titleAn effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven a set of items with profits and weights and a knapsack capacity, we study the problem of finding a maximal knapsack packing that minimizes the profit of the selected items. We propose an effective dynamic programming (DP) algorithm which has a pseudo-polynomial time complexity. We demonstrate the equivalence between this problem and the problem of finding a minimal knapsack cover that maximizes the profit of the selected items. In an extensive computational study on a large and diverse set of benchmark instances, we demonstrate that the new DP algorithm outperforms a state-of-the-art commercial mixed-integer programming (MIP) solver applied to the two best performing MIP models from the literature.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol262en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2017-10
dc.relation.isversionofjnlpages438-448en
dc.relation.isversionofdoi10.1016/j.ejor.2017.03.061en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-27T11:53:09Z
hal.faultCode{"duplicate-entry":{"hal-01666303":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record