Show simple item record

dc.contributor.authorCaprara, Alberto
dc.contributor.authorFurini, Fabio
dc.contributor.authorMalaguti, Enrico
dc.contributor.authorTraversi, Emiliano
dc.date.accessioned2017-03-16T11:59:45Z
dc.date.available2017-03-16T11:59:45Z
dc.date.issued2016
dc.identifier.issn0020-0190
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16372
dc.language.isoenen
dc.subjectCombinatorial Problemsen
dc.subjectTemporal Knapsack Problemen
dc.subjectDantzig–Wolfe Reformulationen
dc.subjectMixed integer programsen
dc.subject.ddc003en
dc.titleSolving the Temporal Knapsack Problem via Recursive Dantzig–Wolfe Reformulationen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe Temporal Knapsack Problem (TKP) is a generalization of the standard Knapsack Problem where a time horizon is considered, and each item consumes the knapsack capacity during a limited time interval only. In this paper we solve the TKP using what we call a Recursive Dantzig–Wolfe Reformulation (DWR) method. The generic idea of Recursive DWR is to solve a Mixed Integer Program (MIP) by recursively applying DWR, i.e., by using DWR not only for solving the original MIP but also for recursively solving the pricing sub-problems. In a binary case (like the TKP), the Recursive DWR method can be performed in such a way that the only two components needed during the optimization are a Linear Programming solver and an algorithm for solving Knapsack Problems. The Recursive DWR allows us to solve Temporal Knapsack Problem instances through computation of strong dual bounds, which could not be obtained by exploiting the best-known previous approach based on DWR.en
dc.relation.isversionofjnlnameInformation Processing Letters
dc.relation.isversionofjnlvol116en
dc.relation.isversionofjnlissue5en
dc.relation.isversionofjnldate2016-05
dc.relation.isversionofjnlpages379-386en
dc.relation.isversionofdoi10.1016/j.ipl.2016.01.008en
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.updated2017-03-16T11:46:58Z
hal.person.labIds461036
hal.person.labIds989
hal.person.labIds461036
hal.person.labIds994
hal.identifierhal-01491117*


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