A Neural Separation Algorithm for the Rounded Capacity Inequalities

References

• Addanki R, Nair V, Alizadeh M (2020) Neural large neighborhood search. Learning Meets Combinatorial Algorithms at NeurIPS2020.Google Scholar
• Ahn S, Seo Y, Shin J (2020) Learning what to defer for maximum independent sets. Daumé H III, Singh A, eds. Proc. of the 37th Internat. Conf. Machine Learn., vol. 119 (PMLR, New York), 134–144.Google Scholar
• Augerat P, Belenguer JM, Benavent E, Corbéran A, Naddef D (1998) Separating capacity constraints in the CVRP using Tabu search. Eur. J. Oper. Res. 106(2–3):546–557.Crossref, Google Scholar
• Augerat P, Naddef D, Belenguer J, Benavent E, Corberan A, Rinaldi G (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical report INPG-RR-949-M, Institut National Polytechnique, Grenoble, France.Google Scholar
• Balcan MF, Dick T, Sandholm T, Vitercik E (2018) Learning to branch. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., vol. 80 (PMLR, New York), 344–353.Google Scholar
• Baltean-Lugojan R, Bonami P, Misener R, Tramontani A (2019) Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. Accessed January 5, 2024, https://optimization-online.org/?p=17362.Google Scholar
• Bello I, Pham H, Le QV, Norouzi M, Bengio S (2016) Neural combinatorial optimization with reinforcement learning. Preprint, submitted November 29, https://arxiv.org/abs/1611.09940.Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• Bogyrbayeva A, Meraliyev M, Mustakhov T, Dauletbayev B (2024) Machine learning to solve vehicle routing problems: A survey. IEEE Trans. Intelligent Transportation Systems, 1–19.Google Scholar
• Chen X, Tian Y (2019) Learning to perform local rewriting for combinatorial optimization. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 6281–6292.Google Scholar
• Chmiela A, Khalil E, Gleixner A, Lodi A, Pokutta S (2021) Learning to schedule heuristics in branch and bound. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 24235–24246.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
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Diarrassouba I (2017) On the complexity of the separation problem for rounded capacity inequalities. Discrete Optim. 25:86–104.Crossref, Google Scholar
• Dunning I, Huchette J, Lubin M (2017) JuMP: A modeling language for mathematical optimization. SIAM Rev. 59(2):295–320.Crossref, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Aragão MPD, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• Gasse M, Chételat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 15580–15592.Google Scholar
• Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE (2017) Neural message passing for quantum chemistry. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., vol. 70 (PMLR, New York), 1263–1272.Google Scholar
• Gupta P, Gasse M, Khalil E, Mudigonda P, Lodi A, Bengio Y (2020) Hybrid models for learning to branch. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Adv. Neural Inform. Processing Systems, vol. 33 (Curran Associates, Inc, Red Hook, NY), 18087–18097.Google Scholar
• Hottung A, Tierney K (2020) Neural large neighborhood search for the capacitated vehicle routing problem. De Giacomo G, Catala A, Dilkina B, Milano M, Barro S, Bugarín A, Lang J, eds. Proc. 24th Eur. Conf. Artificial Intelligence, vol. 325 (IOS Press, Amsterdam), 443–450.Google Scholar
• Khalil E, Dai H, Zhang Y, Dilkina B, Song L (2017a) Learning combinatorial optimization algorithms over graphs. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 30 (Curran Associates, Inc., Red Hook, NY), 6351–6361.Google Scholar
• Khalil EB, Dilkina B, Nemhauser GL, Ahmed S, Shao Y (2017b) Learning to run heuristics in tree search. Sierra C, ed. Proc. Internat. Joint Conf. Artificial Intelligence Organ. (International Joint Conferences on Artificial Intelligence, California), 659–666.Google Scholar
• Khalil E, Le Bodic P, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. AAAI Conf. Artificial Intelligence, vol. 30 (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Kim M, Park J, Park J (2022b) Sym-NCO: Leveraging symmetricity for neural combinatorial optimization. Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, eds. Adv. Neural Inform. Processing Systems, vol. 35 (Curran Associates, Inc., Red Hook, NY), 1936–1949.Google Scholar
• Kim H, Kim M, Kwon C, Park J (2022a) Neural coarsening process for multi-level graph combinatorial optimization. Proc. NeurIPS New Frontiers in Graph Learning Workshop.Google Scholar
• Kool W, van Hoof H, Welling M (2018) Attention, learn to solve routing problems! Levine S, Livescu K, Mohamed S, eds. Proc. Internat. Conf. Learn. Representations (Curran Associates, Inc., Red Hook, NY), 7166–7190.Google Scholar
• Kotary J, Fioretto F, van Hentenryck P, Wilder B (2021) End-to-end constrained optimization learning: A survey. Zhou Z-H, ed. Proc. 30th Internat. Joint Conf. Artificial Intelligence (Curran Associates, Inc., Red Hook, NY), 4475–4482.Google Scholar
• Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. Oper. Res. Spektrum 5(2):77–85.Crossref, Google Scholar
• Laporte G, Nobert Y, Desrochers M (1985) Optimal routing under capacity and distance restrictions. Oper. Res. 33(5):1050–1073.Link, Google Scholar
• Lima I, Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian AWR, et al. (2014) CVRPLIB: Capacitated vehicle routing problem library. Accessed October 6, 2022, http://vrp.galgos.inf.puc-rio.br/index.php/en/.Google Scholar
• Lu H, Zhang X, Yang S (2019) A learning-based iterative method for solving vehicle routing problems. Song D, Cho K, White M, eds. Proc. Internat. Conf. Learn. Representations (Curran Associates, Inc., Red Hook, NY), 1–15.Google Scholar
• Lysgaard J (2003) CVRPSEP: A package of separation routines for the capacitated vehicle routing problem. Accessed September 27, 2022, https://econ.au.dk/research/researcher-websites/jens-lysgaard/cvrpsep.Google Scholar
• Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Morabit M, Desaulniers G, Lodi A (2021) Machine-learning–based column selection for column generation. Transportation Sci. 55(4):815–831.Link, Google Scholar
• Morabit M, Desaulniers G, Lodi A (2022) Machine-learning-based arc selection for constrained shortest path problems in column generation. INFORMS J. Optim. 5(2):191–210.Google Scholar
• Park J, Kwon C, Park J (2023) Learn to solve the min-max multiple traveling salesmen problem with reinforcement learning. Proc. 2023 Internat. Conf. Autonomous Agents and Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, London), 878–886.Google Scholar
• Paulus MB, Zarpellon G, Krause A, Charlin L, Maddison CJ (2022) Learning to cut by looking ahead: Cutting plane selection via imitation learning. Chaudhuri K, Jegelka S, Song L, Szepesvari C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., vol. 162 (PMLR, New York), 17584–17600.Google Scholar
• Pisinger D, Ropke S (2010) Large neighborhood search. Handbook of Metaheuristics (Springer, Berlin), 399–419.Crossref, Google Scholar
• Queiroga E, Sadykov R, Uchoa E, Vidal T (2022) 10,000 optimal CVRP solutions for testing machine learning based heuristics. Proc. AAAI-22 Workshop Machine Learn. for Oper. Res. (AAAI Press, Palo Alto, CA).Google Scholar
• Ralphs TK (1995) Parallel Branch and Cut for Vehicle Routing (Cornell University, Ithaca, NY).Google Scholar
• Ralphs TK, Kopman L, Pulleyblank WR, Trotter LE (2003) On the capacitated vehicle routing problem. Math. Programming 94(2):343–359.Crossref, Google Scholar
• Schuetz MJ, Brubaker JK, Katzgraber HG (2022) Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence 4(4):367–377.Crossref, Google Scholar
• Shaw P (1997) A new local search algorithm providing high quality solutions to vehicle routing problems. APES Group (Department of Computer Science, University of Strathclyde, Glasgow, Scotland, UK), 46.Google Scholar
• Smith KA (1999) Neural networks for combinatorial optimization: A review of more than a decade of research. INFORMS J. Comput. 11(1):15–34.Link, Google Scholar
• Tang Y, Agrawal S, Faenza Y (2020) Reinforcement learning for integer programming: Learning to cut. Daumé H III, Singh A, eds. Proc. Internat. 37th Conf. Machine Learn., vol. 119 (PMLR, New York), 9367–9376.Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications (Society for Industrial and Applied Mathematics, Philadelphia, PA).Crossref, Google Scholar
• Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• Vidal T (2022) Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Comput. Oper. Res. 140:105643.Crossref, Google Scholar
• Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 28 (Curran Associates, Inc, Red Hook, NY).Google Scholar
• Wang M, Zheng D, Ye Z, Gan Q, Li M, Song X, Zhou J, et al. (2019) Deep graph library: A graph-centric, highly-performant package for graph neural networks. Preprint, submitted September 3, https://arxiv.org/abs/1909.01315.Google Scholar
• Wenger K (2003) Generic cut generation methods for routing problems. PhD thesis, Institute of Computer Science, University of Heidelberg, Heidelberg, Germany.Google Scholar
• Wu Y, Song W, Cao Z, Zhang J (2021) Learning large neighborhood search policy for integer programming. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 30075–30087.Google Scholar
• Zhang X, Chen L, Gendreau M, Langevin A (2022) Learning-based branch-and-price algorithms for the vehicle routing problem with time windows and two-dimensional loading constraints. INFORMS J. Comput. 34(3):1419–1436.Link, Google Scholar