Afficher la notice abrégée

Arc flow formulations based on dynamic programming: Theoretical foundations and applications

hal.structure.identifierInstitute of Computing [Campinas] [IC]
dc.contributor.authorDE LIMA, Vinícius
hal.structure.identifierUniversidade do Minho = University of Minho [Braga]
dc.contributor.authorALVES, Cláudio
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorCLAUTIAUX, François
hal.structure.identifierUniversità degli Studi di Modena e Reggio Emilia = University of Modena and Reggio Emilia [UNIMORE]
dc.contributor.authorIORI, Manuel
hal.structure.identifierUniversidade do Minho = University of Minho [Braga]
dc.contributor.authorVALÉRIO DE CARVALHO, José
dc.date.accessioned2024-04-04T02:43:25Z
dc.date.available2024-04-04T02:43:25Z
dc.date.issued2022-01
dc.identifier.issn0377-2217
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191334
dc.description.abstractEnNetwork flow formulations are among the most successful tools to solve optimization problems. One of such formulations is the arc flow, where variables represent flows on individual arcs of the network. For NP-hard problems, polynomial-sized arc flow models typically provide weak linear relaxations and may have too much symmetry to be efficient in practice. Instead, arc flow models with a pseudo-polynomial size usually provide strong relaxations and are efficient in practice. The interest in pseudo-polynomial arc flow formulations has grown considerably in the last twenty years, in which they have been used to solve many open instances of hard problems. A remarkable advantage of arc flow models is the possibility to solve practical-sized instances directly by a Mixed Integer Linear Programming solver, avoiding the implementation of complex methods based on column generation. In this survey, we present theoretical foundations of pseudo-polynomial arc flow formulations, by showing a relation between their network and Dynamic Programming (DP). This relation allows a better understanding of the strength of these formulations, through a link with models obtained by Dantzig-Wolfe decomposition. The relation with DP also allows a new perspective to relate state-space relaxation methods for DP with arc flow models. We also present a dual point of view to contrast the linear relaxation of arc flow models with that of models based on paths and cycles. To conclude, we review the main solution methods and applications of arc flow models based on DP in several domains such as cutting, packing, scheduling, and routing.
dc.language.isoen
dc.publisherElsevier
dc.subject.enCombinatorial Optimization
dc.subject.enArc Flow
dc.subject.enDynamic Programming
dc.subject.enAcyclic Network
dc.subject.enPseudo-Polynomial
dc.title.enArc flow formulations based on dynamic programming: Theoretical foundations and applications
dc.typeArticle de revue
dc.identifier.doi10.1016/j.ejor.2021.04.024
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalEuropean Journal of Operational Research
bordeaux.page3-21
bordeaux.volume296
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue1
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-03478786
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03478786v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Operational%20Research&rft.date=2022-01&rft.volume=296&rft.issue=1&rft.spage=3-21&rft.epage=3-21&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=DE%20LIMA,%20Vin%C3%ADcius&ALVES,%20Cl%C3%A1udio&CLAUTIAUX,%20Fran%C3%A7ois&IORI,%20Manuel&VAL%C3%89RIO%20DE%20CARVALHO,%20Jos%C3%A9&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée