Show simple item record

dc.contributor.authorFurini, Fabio
dc.contributor.authorMonaci, Michele
dc.contributor.authorTraversi, Emiliano
dc.date.accessioned2019-04-12T14:21:51Z
dc.date.available2019-04-12T14:21:51Z
dc.date.issued2018
dc.identifier.issn03050548
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18642
dc.language.isoenen
dc.subjectKnapsack problemsen
dc.subjectColumn generationen
dc.subjectRelaxationsen
dc.subjectBranch-and-bound algorithmsen
dc.subjectComputational experimentsen
dc.subject.ddc005en
dc.titleExact approaches for the knapsack problem with setupsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We theoretically compare the strength of the relaxations and derive specific results for a relevant case arising in benchmark instances from the literature. Finally, we embed the algorithms above into a unified implicit enumeration scheme which is run in parallel with an improved Dynamic Programming algorithm to effectively solve the problem to proven optimality. An extensive computational analysis shows that our new exact algorithm is capable of efficiently solving all the instances of the literature and turns out to be the best algorithm for instances with a low number of classes.en
dc.relation.isversionofjnlnameComputers & Operations Research
dc.relation.isversionofjnlvol90en
dc.relation.isversionofjnldate2018-02
dc.relation.isversionofjnlpages208-220en
dc.relation.isversionofdoi10.1016/j.cor.2017.09.019en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-27T12:17:50Z
hal.person.labIds989
hal.person.labIds461036
hal.person.labIds994
hal.identifierhal-02098420*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record