Dynamic unsplittable flows with path-change penalties: New formulations and solution schemes for large instances - Fédération de recherche ENAC ISAE-SUPAERO ONERA Accéder directement au contenu
Article Dans Une Revue (Article De Synthèse) Computers and Operations Research Année : 2023

Dynamic unsplittable flows with path-change penalties: New formulations and solution schemes for large instances

Flots insécables dynamiques avec pénalités de changement de chemin : nouvelles formulations et méthodes de solutions pour les instances de grande taille

Résumé

In this work, we consider the dynamic unsplittable flow problem. This variation of the unsplittable flow problem has received little attention so far. The unsplittable flow problem is an NP-hard extension of the multi-commodity flow problem where each commodity sends its flow on only one path. In its dynamic version, this problem features several time steps and a penalty is paid when a commodity changes its path from one time step to the next. We present several mixed-integer linear programming formulations for this problem and compare the strength of their linear relaxation. These formulations are embedded in several solvers which are extensively compared on small to large instances. One of these formulations must be solved through a column generation process whose pricing problem is more difficult than those used in classical flow problems. We present limitations of the pricing schemes proposed in earlier works and describe two new schemes with a better worst-case complexity. Overall, this work lays a strong algorithmic baseline for the resolution of the dynamic unsplittable flow problem, proposes original formulations, and discusses the compared advantages of each, thus hopefully contributing a step towards a better understanding of this problem for both OR researchers and practical applications.
Fichier principal
Vignette du fichier
papier dynamic.pdf (2.13 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04638005 , version 1 (08-07-2024)

Identifiants

Citer

François Lamothe, Emmanuel Rachelson, Alain Haït, Cédric Baudoin, Jean-Baptiste Dupé. Dynamic unsplittable flows with path-change penalties: New formulations and solution schemes for large instances. Computers and Operations Research, 2023, 152, pp.106154. ⟨10.1016/j.cor.2023.106154⟩. ⟨hal-04638005⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More