hal.structure.identifier | Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE] | |
dc.contributor.author | Furini, Fabio | |
hal.structure.identifier | ESSEC Business School | |
dc.contributor.author | Ljubić, Ivana | |
hal.structure.identifier | Department of Statistics and Operations Research | |
dc.contributor.author | Sinnl, Markus | |
dc.date.accessioned | 2019-04-12T13:55:34Z | |
dc.date.available | 2019-04-12T13:55:34Z | |
dc.date.issued | 2017 | |
dc.identifier.issn | 0377-2217 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/18639 | |
dc.language.iso | en | en |
dc.subject | Combinatorial optimization | en |
dc.subject | Maximal knapsack packing | en |
dc.subject | Minimal knapsack cover | en |
dc.subject | Dynamic programming | en |
dc.subject | Integer programming | en |
dc.subject.ddc | 003 | en |
dc.title | An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem | en |
dc.type | Article accepté pour publication ou publié | |
dc.description.abstracten | Given 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.isversionofjnlname | European Journal of Operational Research | |
dc.relation.isversionofjnlvol | 262 | en |
dc.relation.isversionofjnlissue | 2 | en |
dc.relation.isversionofjnldate | 2017-10 | |
dc.relation.isversionofjnlpages | 438-448 | en |
dc.relation.isversionofdoi | 10.1016/j.ejor.2017.03.061 | en |
dc.relation.isversionofjnlpublisher | Elsevier | en |
dc.subject.ddclabel | Recherche opérationnelle | en |
dc.relation.forthcoming | non | en |
dc.relation.forthcomingprint | non | en |
dc.description.ssrncandidate | non | en |
dc.description.halcandidate | oui | en |
dc.description.readership | recherche | en |
dc.description.audience | International | en |
dc.relation.Isversionofjnlpeerreviewed | oui | en |
dc.relation.Isversionofjnlpeerreviewed | oui | en |
dc.date.updated | 2019-03-27T11:53:09Z | |
hal.faultCode | {"duplicate-entry":{"hal-01666303":{"doi":"1.0"}}} | |
hal.author.function | aut | |
hal.author.function | aut | |
hal.author.function | aut | |