IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i6p1634-1653.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Jiachen Zhang & Youcef Magnouche & Pierre Bauguion & Sebastien Martin & J. Christopher Beck, 2024. "Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-Cut," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1634-1653, December.
    • Handle: RePEc:inm:orijoc:v:36:y:2024:i:6:p:1634-1653
    DOI: 10.1287/ijoc.2023.0128
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2023.0128
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2023.0128?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:36:y:2024:i:6:p:1634-1653. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.