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

References

• 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.Google Scholar
• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Link, Google Scholar
• Assad AA (1978) Multicommodity network flows—A survey. Networks 8(1):37–91.Crossref, Google Scholar
• Balas E (1975) Facets of the knapsack polytope. Math. Programming 8(1):146–164.Crossref, Google Scholar
• 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.Link, Google Scholar
• 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.Link, Google Scholar
• Beck JC, Refalo P (2003) A hybrid approach to scheduling with earliness and tardiness costs. Ann. Oper. Res. 118:49–71.Crossref, Google Scholar
• 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.Google Scholar
• 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.Link, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• 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.Google Scholar
• 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.Crossref, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.Link, Google Scholar
• Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper. Res. 58(1):179–192.Link, Google Scholar
• Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269–271.Crossref, Google Scholar
• 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.Google Scholar
• Finn N (2018) Introduction to time-sensitive networking. IEEE Comm. Standards Magazine 2(2):22–28.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Google Scholar
• 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.Crossref, Google Scholar
• Handler GY, Zang I (1980) A dual algorithm for the constrained shortest path problem. Networks 10(4):293–309.Crossref, Google Scholar
• 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.Google Scholar
• 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.Link, Google Scholar
• Hooker JN, Ottosson G (2003) Logic-based benders decomposition. Math. Programming 96(1):33–60.Crossref, Google Scholar
• IBM (2023) IBM ILOG CPLEX Optimizer. Accessed January 1, 2024, https://www.ibm.com/de-de/analytics/cplex-optimizer.Google Scholar
• 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.Google Scholar
• Kadioğlu S (2019) Core group placement: Allocation and provisioning of heterogeneous resources. EURO J. Comput. Optim. 7(3):243–264.Crossref, Google Scholar
• Karp RM (1975) On the computational complexity of combinatorial problems. Networks 5(1):45–68.Crossref, Google Scholar
• Kinable J, van Hoeve WJ, Smith SF (2020) Snow plow route optimization: A constraint programming approach. IISE Trans. 53(6):685–703.Crossref, Google Scholar
• 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.Google Scholar
• Laborie P, Rogerie J (2016) Temporal linear relaxation in IBM ILOG CP Optimizer. J. Scheduling 19(4):391–400.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Lam E, Hentenryck PV (2016) A branch-and-price-and-check model for the vehicle routing problem with location congestion. Constraints 21:394–412.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Google Scholar
• Lozano L, Medaglia AL (2013) On an exact method for the constrained shortest path problem. Comput. Oper. Res. 40(1):378–384.Crossref, Google Scholar
• Milano M, Wallace M (2010) Integrating operations research in constraint programming. Ann. Oper. Res. 175(1):37–76.Crossref, Google Scholar
• Minoux M (2001) Discrete cost multicommodity network optimization problems and exact solution methods. Ann. Oper. Res. 106(1–4):19–46.Crossref, Google Scholar
• 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.Google Scholar
• Petterson M, Szymankek R, Kuchcinski K (2007) A CP-LP hybrid method for unique shortest path routing optimization. Internat. Network Optim. Conf.Google Scholar
• 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.Google Scholar
• Risso C, Nesmachnow S, Robledo F (2018) Metaheuristic approaches for IP/MPLS network design. Internat. Trans. Oper. Res. 25(2):599–625.Crossref, Google Scholar
• 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.Link, Google Scholar
• 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–47Google Scholar
• Rossi F, Van Beek P, Walsh T (2006) Handbook of Constraint Programming (Elsevier, Boston).Google Scholar
• Rousseau LM, Gendreau M, Pesant G, Focacci F (2004) Solving VRPTWs with constraint programming based column generation. Ann. Oper. Res. 130:199–216.Crossref, Google Scholar
• Sakkout HE, Wallace M (2000) Probe backtrack search for minimal perturbation in dynamic scheduling. Constraints 5(4):359–388.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Google Scholar
• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Google Scholar
• 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.Crossref, Google Scholar
• 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.Link, Google Scholar
• Wolsey LA, Nemhauser GL (1999) Integer and Combinatorial Optimization, vol. 55 (John Wiley & Sons, Hoboken).Google Scholar
• Xia Q, Simonis H (2005) Primary/secondary path generation problem: Reformulation, solutions and comparisons. Internat. Conf. Networking (Springer, Berlin, Heidelberg), 611–619.Google Scholar
• Yen JY (1971) Finding the k shortest loopless paths in a network. Management Sci. 17(11):712–716.Link, Google Scholar
• 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.Google Scholar
• 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://dx.doi.org/10.1287/ijoc.2023.0128.cd, https://github.com/INFORMSJoC/2023.0128.Google Scholar