Mathematics > Optimization and Control
[Submitted on 27 Mar 2023]
Title:Dynamic unsplittable flows with path-change penalties: new formulations and solution schemes for large instances
View PDFAbstract: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.
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.