Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-Cut

Jiachen Zhang (), Youcef Magnouche (), Pierre Bauguion (), Sebastien Martin () and J. Christopher Beck ()
Additional contact information
Jiachen Zhang: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada
Youcef Magnouche: Huawei Technologies, Paris Research Center, 92100 Boulogne-Billancourt, France
Pierre Bauguion: Huawei Technologies, Paris Research Center, 92100 Boulogne-Billancourt, France
Sebastien Martin: Huawei Technologies, Paris Research Center, 92100 Boulogne-Billancourt, France
J. Christopher Beck: Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1634-1653

Abstract: We propose a constraint programming (CP)–based branch-and-price-and-cut framework to exactly solve bipath multicommodity flow (MCF): an MCF problem with two paths for each demand. The goal is to route demands in a capacitated network under the minimum cost. The two paths must have disjoint arcs, and the delays accumulated along the two paths must be within a small deviation of each other. CP is used at multiple points in this framework: for solving pricing problems, for cut generation, and for primal and branching node heuristics. These modules use a CP solver designed for network routing problems and can be adapted to other combinatorial optimization problems. We also develop a novel, complete, two-level branching scheme. On a set of diverse bipath MCF instances, experimental results show that our algorithm significantly outperforms monolithic CP and mixed integer linear programming models and demonstrate the efficiency and flexibility brought by the tailored integration of linear programming and CP methodologies.

Keywords: constraint programming; branch-and-price-and-cut; multicommodity flow; network routing (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0128 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1634-1653

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().