Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-Cut
Pages 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.
History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis.
Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada; Huawei Technologies.
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (Supplementary Material) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0128). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.
References
[1]
Ajili F, Rodošek R, Eremin A (2005) A branch-price-and-propagate approach for optimizing IGP weight setting subject to unique shortest paths. Liebrock LM, ed. Proc. 2005 ACM Sympos. Appl. Comput. (Association for Computing Machinery, New York), 366–370.
[2]
Alvelos FP, de Carvalho JV (2007) An extended model and a column generation algorithm for the planar multicommodity flow problem. Networks 50(1):3–16.
[3]
Alves C, de Carvalho JV (2008) A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem. Comput. Oper. Res. 35(4):1315–1328.
[4]
Angilella V, Krasniqi F, Medagliani P, Martin S, Leguay J, Shoushou R, Xuan L (2022) High capacity and resilient large-scale deterministic IP networks. J. Network System Management 30(4):1–28.
[5]
Archetti C, Bouchard M, Desaulniers G (2011) Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Sci. 45(3):285–298.
[6]
Assad AA (1978) Multicommodity network flows—A survey. Networks 8(1):37–91.
[7]
Balas E (1975) Facets of the knapsack polytope. Math. Programming 8(1):146–164.
[8]
Barnhart C, Hane CA, Vance PH (2000) Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 48(2):318–326.
[9]
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.
[10]
Beck JC, Refalo P (2003) A hybrid approach to scheduling with earliness and tardiness costs. Ann. Oper. Res. 118:49–71.
[11]
Bhatia R, Hao F, Kodialam M, Lakshman T (2015) Optimized network traffic engineering using segment routing. 2015 IEEE Conf. Comput. Comm. (IEEE, Piscataway, NJ), 657–665.
[12]
Caimi G, Chudak F, Fuchsberger M, Laumanns M, Zenklusen R (2011) A new resource-constrained multicommodity flow model for conflict-free train routing and scheduling. Transportation Sci. 45(2):212–227.
[13]
Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.
[14]
Cronholm W, Ajili F (2004) Strong cost-based filtering for Lagrange decomposition applied to network design. Wallace M, ed. Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin, Heidelberg), 726–730.
[15]
D’Ambrosio C, Lodi A, Wiese S, Bragalli C (2015) Mathematical programming techniques in water network optimization. Eur. J. Oper. Res. 243(3):774–788.
[16]
Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.
[17]
Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper. Res. 58(1):179–192.
[18]
Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269–271.
[19]
Dooms G, Deville Y, Dupont P (2005) CP (graph): Introducing a graph computation domain in constraint programming. Beek P, ed. Principles Practice Constraint Programming 11th Internat. Conf. Proc., vol. 11 (Springer, Berlin, Heidelberg), 211–225.
[20]
Finn N (2018) Introduction to time-sensitive networking. IEEE Comm. Standards Magazine 2(2):22–28.
[21]
Focacci F, Lodi A, Milano M (2002) Embedding relaxations in global constraints for solving TSP and TSPTW. Ann. Math. Artificial Intelligence 34(4):291–311.
[22]
Fortz B, Gouveia L, Joyce-Moniz M (2017) Models for the piecewise linear unsplittable multicommodity flow problems. Eur. J. Oper. Res. 261(1):30–42.
[23]
Foteinos V, Tsagkaris K, Peloso P, Ciavaglia L, Demestichas P (2014) Operator-friendly traffic engineering in IP/MPLS core networks. IEEE eTrans. Network Service Management 11(3):333–349.
[24]
Frei C, Faltings B (1999) Resource allocation in networks using abstraction and constraint satisfaction techniques. Jaffar J, ed. Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin, Heidelberg), 204–218.
[25]
Gélinas S, Desrochers M, Desrosiers J, Solomon MM (1995) A new branching strategy for time constrained routing problems with application to backhauling. Ann. Oper. Res. 61:91–109.
[26]
Handler GY, Zang I (1980) A dual algorithm for the constrained shortest path problem. Networks 10(4):293–309.
[27]
Hartert R, Schaus P, Vissicchio S, Bonaventure O (2015) Solving segment routing problems with hybrid constraint programming techniques. Pesant G, ed. Internat. Conf. Principles Practice Constraint Programming (Springer, Cham), 592–608.
[28]
Hashemi Doulabi SH, Rousseau LM, Pesant G (2016) A constraint-programming-based branch-and-price-and-cut approach for operating room planning and scheduling. INFORMS J. Comput. 28(3):432–448.
[29]
Hooker JN, Ottosson G (2003) Logic-based benders decomposition. Math. Programming 96(1):33–60.
[30]
IBM (2023) IBM ILOG CPLEX Optimizer. Accessed January 1, 2024, https://www.ibm.com/de-de/analytics/cplex-optimizer.
[31]
Junker U, Karisch SE, Kohl N, Vaaben B, Fahle T, Sellmann M (1999) A framework for constraint programming based column generation. Jaffar J, ed. Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin, Heidelberg), 261–274.
[32]
Kadioğlu S (2019) Core group placement: Allocation and provisioning of heterogeneous resources. EURO J. Comput. Optim. 7(3):243–264.
[33]
Karp RM (1975) On the computational complexity of combinatorial problems. Networks 5(1):45–68.
[34]
Kinable J, van Hoeve WJ, Smith SF (2020) Snow plow route optimization: A constraint programming approach. IISE Trans. 53(6):685–703.
[35]
Laborie P (2009) IBM ILOG CP optimizer for detailed scheduling illustrated on three problems. Hoeve W-J, Hooker JN, eds. Integration AI OR Techniques Constraint Programming Combin. Optim. Problems: Sixth Internat. Conf. Proc. (Springer, Berlin, Heidelberg), 148–162.
[36]
Laborie P, Rogerie J (2016) Temporal linear relaxation in IBM ILOG CP Optimizer. J. Scheduling 19(4):391–400.
[37]
Laborie P, Rogerie J, Shaw P, Vilím P (2018) IBM ILOG CP optimizer for scheduling: 20+ years of scheduling with constraints at IBM/ILOG. Constraints 23:210–250.
[38]
Lam E, Hentenryck PV (2016) A branch-and-price-and-check model for the vehicle routing problem with location congestion. Constraints 21:394–412.
[39]
Lam E, Desaulniers G, Stuckey PJ (2022) Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations. Comput. Oper. Res. 145:105870.
[40]
Le Pape C, Perron L, Régin JC, Shaw P (2002) Robust and parallel solving of a network design problem. Hentenryck P, ed. Principles Practice Constraint Programming Eighth Internat. Conf. Proc. (Springer, Berlin, Heidelberg), 633–648.
[41]
Lozano L, Medaglia AL (2013) On an exact method for the constrained shortest path problem. Comput. Oper. Res. 40(1):378–384.
[42]
Milano M, Wallace M (2010) Integrating operations research in constraint programming. Ann. Oper. Res. 175(1):37–76.
[43]
Minoux M (2001) Discrete cost multicommodity network optimization problems and exact solution methods. Ann. Oper. Res. 106(1–4):19–46.
[44]
Ouaja W, Richards B (2005) Hybrid Lagrangian relaxation for bandwidth-constrained routing: Knapsack decomposition. Liebrock LM, ed. Proc. 2005 ACM Sympos. Appl. Comput. (Association for Computing Machinery, New York), 383–387.
[45]
Petterson M, Szymankek R, Kuchcinski K (2007) A CP-LP hybrid method for unique shortest path routing optimization. Internat. Network Optim. Conf.
[46]
Régin JC (1996) Generalized arc consistency for global cardinality constraint. Proc. 13th National Conf. Artificial Intelligence, vol. 1 (AAAI Press, Menlo Park), 209–215.
[47]
Risso C, Nesmachnow S, Robledo F (2018) Metaheuristic approaches for IP/MPLS network design. Internat. Trans. Oper. Res. 25(2):599–625.
[48]
Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Sci. 40(4):455–472.
[49]
Ros L, Creemers T, Tourouta E, Riera J (2001) A global constraint model for integrated routing and scheduling on a transmission network. Internat. Conf. Inform. Networks Systems Tech., 40–47
[50]
Rossi F, Van Beek P, Walsh T (2006) Handbook of Constraint Programming (Elsevier, Boston).
[51]
Rousseau LM, Gendreau M, Pesant G, Focacci F (2004) Solving VRPTWs with constraint programming based column generation. Ann. Oper. Res. 130:199–216.
[52]
Sakkout HE, Wallace M (2000) Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints 5(4):359–388.
[53]
Salimifard K, Bigharaz S (2022) The multicommodity network flow problem: State of the art classification, applications, and solution methods. Oper. Res. 22(1):1–47.
[54]
Sebbah S, Bagley C, Colena M, Kadioglu S (2016) Availability optimization in cloud-based in-memory data grids. Principles Practice Constraint Programming 22nd Internat. Conf. Proc. (Springer, Berlin, Heidelberg), 666–679.
[55]
Shi H, Blaauwbroek N, Nguyen PH, Kamphuis RI (2016) Energy management in multi-commodity smart energy systems with a greedy approach. Appl. Energy 167:385–396.
[56]
Tang F, Mao B, Kawamoto Y, Kato N (2021) Survey on machine learning for intelligent end-to-end communication toward 6G: From network access, routing to traffic control and streaming adaption. IEEE Comm. Surveys Tutorials 23(3):1578–1598.
[57]
Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015) Line: Large-scale information network embedding. Proc. 24th Internat. Conf. World Wide Web, 1067–1077.
[58]
Vlk M, Hanzálek Z, Tang S (2021) Constraint programming approaches to joint routing and scheduling in time-sensitive networks. Comput. Indust. Engrg. 157:107317.
[59]
Wei L, Luo Z, Baldacci R, Lim A (2020) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J. Comput. 32(2):428–443.
[60]
Wolsey LA, Nemhauser GL (1999) Integer and Combinatorial Optimization, vol. 55 (John Wiley & Sons, Hoboken).
[61]
Xia Q, Simonis H (2005) Primary/secondary path generation problem: Reformulation, solutions and comparisons. Internat. Conf. Networking (Springer, Berlin, Heidelberg), 611–619.
[62]
Yen JY (1971) Finding the k shortest loopless paths in a network. Management Sci. 17(11):712–716.
[63]
Zhang J, Magnouche Y, Bauguion P, Martin S, Beck JC (2023a) Appendix to computing bi-path multi-commodity flows with constraint programming-based branch-and-price-and-cut. Accessed January 5, 2024, https://tidel.mie.utoronto.ca/pubs/Computing_Bi-Path_MCP_with_CP-based_B&P&C(Appendix).pdf.
[64]
Zhang J, Youcef M, Bauguion P, Martin S, Beck JC (2023b) Computing bipath multicommodity flows with constraint programming–based branch and price and-cut. https://doi.org/10.1287/ijoc.2023.0128.cd, https://github.com/INFORMSJoC/2023.0128.
Index Terms
- Computing Bipath Multicommodity Flows with Constraint Programming–Based Branch-and-Price-and-Cut
Index terms have been assigned to the content through auto-classification.
Recommendations
Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems
We present a column-generation model and branch-and-price-and-cut algorithm for origin-destination integer multicommodity flow problems. The origin-destination integer multicommodity flow problem is a constrained version of the linear multicommodity ...
A Constraint-Programming-Based Branch-and-Price-and-Cut Approach for Operating Room Planning and Scheduling
This paper presents an efficient algorithm for an integrated operating room planning and scheduling problem. It combines the assignment of surgeries to operating rooms and scheduling over a short-term planning horizon. This integration results in more ...
Branch-and-price-and-cut algorithms for solving the reliable h-paths problem
We examine a routing problem in which network arcs fail according to independent failure probabilities. The reliable h -path routing problem seeks to find a minimum-cost set of h 2 arc-independent paths from a common origin to a common destination, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024, INFORMS.
Publisher
INFORMS
Linthicum, MD, United States
Publication History
Published: 29 March 2024
Accepted: 29 January 2024
Received: 21 April 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in