Machine-Learning–Based Column Selection for Column Generation

References

• Alvarez A, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1):185–195.Link, Google Scholar
• Amor HMB, Desrosiers J, Frangioni A (2009) On the choice of explicit stabilizing terms in column generation. Discrete Appl. Math. 157(6):1167–1184.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Ball M, Bodin L, Dial R (1983) A matching based heuristic for scheduling mass transit crews and vehicles. Transportation Sci. 17(1):4–31.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1996) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Battaglia PJ, Hamrick B, Bapst V, Sanchez-Gonzalez A, Zambaldi V, Malinowski M, Tacchetti A, et al. (2018) Relational inductive biases, deep learning, and graph networks. Preprint, submitted June 4, https://arxiv.org/abs/1806.01261.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
• Contardo C, Desaulniers G, Lessard F (2015) Reaching the elementary lower bound in the vehicle routing problem with time windows. Networks 65(1):88–99.Crossref, 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
• de Groot SW, Huisman D (2008) Vehicle and crew scheduling: Solving large real-world instances with an integrated approach. Hickman M, Mirchandani P, Voß S, eds. Computer-Aided Systems in Public Transport (Springer, Berlin), 43–56.Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2002) Accelerating strategies for column generation methods in vehicle routing and crew scheduling problems. Ribeiro CC, Hansen P, eds. Essays and Surveys in Metaheuristics (Kluwer, Norwell, MA), 309–324.Crossref, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2005) Column Generation (Springer, New York).Crossref, Google Scholar
• Desaulniers G, Madsen OBG, Ropke S (2014) The vehicle routing problem with time windows. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods and Applications, 2nd ed. (Society for Industrial and Applied Mathematics, Philadelphia), 119–159.Crossref, Google Scholar
• Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40(2):342–354.Link, Google Scholar
• du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1):229–237.Crossref, Google Scholar
• Elhallaoui I, Desaulniers G, Metrane A, Soumis F (2008) Bi-dynamic constraint aggregation and subproblem reduction. Comput. Oper. Res. 35(5):1713–1724.Crossref, Google Scholar
• Elhallaoui I, Metrane A, Desaulniers G, Soumis F (2011) An improved primal simplex algorithm for degenerate linear programs. INFORMS J. Comput. 23(4):569–577.Link, Google Scholar
• Elhallaoui I, Metrane A, Soumis F, Desaulniers G (2010) Multi-phase dynamic constraint aggregation for set partitioning type problems. Math. Programming 123(2):345–370.Crossref, Google Scholar
• Elhallaoui I, Villeneuve D, Soumis F, Desaulniers G (2005) Dynamic aggregation of set-partitioning constraints in column generation. Oper. Res. 53(4):632–645.Link, Google Scholar
• Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44(3):216–229.Crossref, Google Scholar
• Freling R, Huisman D, Wagelmans APM (2003) Models and algorithms for integration of vehicle and crew scheduling. J. Scheduling 6(1):63–85.Crossref, Google Scholar
• Freling R, Wagelmans APM, Paixão JMP (1999) An overview of models and techniques for integrating vehicle and crew scheduling. Wilson NHM, ed. Computer-Aided Transit Scheduling (Springer, Berlin), 441–460.Crossref, Google Scholar
• Gilmore P, Gomory RE (1961) A linear programming approach to the cutting stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Gondzio J, González-Brevis P, Munari P (2016) Large-scale optimization with the primal-dual column generation method. Math. Programming Comput. 8(1):47–82.Crossref, Google Scholar
• Goodfellow I, Bengio Y, Courville A (2016) Deep Learning (MIT Press, Cambridge, MA).Google Scholar
• Gori M, Monfardini G, Scarselli F (2005) A new model for learning in graph domains. Proc. 2005 IEEE Internat. Joint Conf. Neural Networks, vol. 2 (IEEE, Piscataway, NJ), 729–734.Google Scholar
• Haase K, Desaulniers G, Desrosiers J (2001) Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Sci. 35(3):286–303.Link, Google Scholar
• Homberger J, Gehring H (2005) A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. 162(1):220–238.Crossref, Google Scholar
• Huisman D, Freling R, Wagelmans APM (2005) Multiple-depot integrated vehicle and crew scheduling. Transportation Sci. 39(4):491–502.Link, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer US, Boston), 33–65.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Khalil EB, Bodic PL, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. Thirtieth AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Kohl N, Desrosiers J, Madsen OBG, Solomon MM, Soumis F (1999) 2-Path cuts for the vehicle routing problem with time windows. Transportation Sci. 33(1):101–116.Link, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Lodi A, Zarpellon G (2017) On learning and branching: A survey. TOP 25(2):207–236.Crossref, Google Scholar
• Mesquita M, Paias A (2008) Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem. Comput. Oper. Res. 35(5):1562–1575.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper. Res. Lett. 35(5):660–668.Crossref, Google Scholar
• Scarselli F, Gori M, Tsoi AC, Hagenbuchner M, Monfardini G (2009) The graph neural network model. IEEE Trans. Neural Networks 20(1):61–80.Crossref, Google Scholar
• Tahir A, Desaulniers G, El Hallaoui I (2019) Integral column generation for the set partitioning problem. Eur. J. Transportation Logist. 8(5):713–744.Crossref, Google Scholar
• Václavík R, Novák A, Šåcha P, Hanzálek Z (2018) Accelerating the branch-and-price algorithm using machine learning. Eur. J. Oper. Res. 271(3):1055–1069.Crossref, Google Scholar
• Vanderbeck F (2005) Implementing mixed integer column generation. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Boston), 331–358.Crossref, Google Scholar
• Wu Z, Pan S, Chen F, Long G, Zhang C, Yu PS (2019) A comprehensive survey on graph neural networks. Preprint, submitted January 3, https://arxiv.org/abs/1901.00596.Google Scholar
• Zaghrouti A, El Hallaoui I, Soumis F (2018) Improved integral simplex using decomposition for the set partitioning problem. Eur. J. Comput. Optim. 6(2):185–206.Crossref, Google Scholar
• Zaghrouti A, Soumis F, El Hallaoui I (2014) Integral simplex using decomposition for the set partitioning problem. Oper. Res. 62(2):435–449.Link, Google Scholar