Show simple item record

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorCLAUTIAUX, François
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorDETIENNE, Boris
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorGUILLOT, Gaël
dc.date.accessioned2024-04-04T02:46:15Z
dc.date.available2024-04-04T02:46:15Z
dc.date.issued2021-09-01
dc.identifier.issn0377-2217
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191534
dc.description.abstractEnIn this paper, we address the temporal knapsack problem (TKP). In this generalization of the classical knapsack problem, selected items enter and leave the knapsack at fixed dates. We solve the TKP with a dynamic program of exponential size, which is solved using a method called Successive Sublimation Dynamic Programming (SSDP). This method starts by relaxing a set of constraints from the initial problem, and iteratively reintroduces them when needed. We show that a direct application of SSDP to the temporal knapsack problem does not lead to an effective method, and that several improvements are needed to compete with the best results from the literature.
dc.language.isoen
dc.publisherElsevier
dc.subject.enTemporal knapsack
dc.subject.enExact algorithm
dc.subject.enLagrangian Relaxation
dc.subject.enSuccessive Sublimation Dynamic Programming method
dc.title.enAn iterative dynamic programming approach for the temporal knapsack problem
dc.typeArticle de revue
dc.identifier.doi10.1016/j.ejor.2020.12.036
dc.subject.halMathématiques [math]/Optimisation et contrôle [math.OC]
bordeaux.journalEuropean Journal of Operational Research
bordeaux.volume293
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue2
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-02044832
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02044832v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Operational%20Research&rft.date=2021-09-01&rft.volume=293&rft.issue=2&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=CLAUTIAUX,%20Fran%C3%A7ois&DETIENNE,%20Boris&GUILLOT,%20Ga%C3%ABl&rft.genre=article


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