Learn to Formulate: A Surrogate Model Framework for Generalized Assignment Problem with Routing Constraints

References

• Anderson R, Huchette J, Ma W, Tjandraatmadja C, Vielma JP (2020) Strong mixed-integer programming formulations for trained neural networks. Math. Programming 183(1–2):3–39.Crossref, Google Scholar
• Bagloee SA, Asadi M, Sarvi M, Patriksson M (2018) A hybrid machine-learning and optimization method to solve bi-level problems. Expert Systems Appl. 95:142–152.Crossref, Google Scholar
• Bartholdi JJ, Hackman ST (2014) Warehouse & distribution science: Release 0.96. The Supply Chain and Logistics Institute. https://www2.isye.gatech.edu/∼jjb/wh/book/editions/wh-sci-0.96.pdf.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
• Bertsimas D, O’Hair A, Relyea S, Silberholz J (2016) An analytics approach to designing combination chemotherapy regimens for cancer. Management Sci. 62(5):1511–1531.Link, Google Scholar
• Biggs M, Hariss R, Perakis G (2017) Optimizing objective functions determined from random forests. Preprint, submitted June 16, http://dx.doi.org/10.2139/ssrn.2986630.Google Scholar
• Boccia M, Masone A, Sterle C, Murino T (2023) The parallel AGV scheduling problem with battery constraints: A new formulation and a matheuristic approach. Eur. J. Oper. Res. 307(2):590–603.Crossref, Google Scholar
• Cacchiani V, Salazar-González JJ (2017) Optimal solutions to a real-world integrated airline scheduling problem. Transportation Sci. 51(1):250–268.Link, Google Scholar
• Chan T, Lin B, Saxe S (2022) Machine learning-augmented optimization of large bilevel and two-stage stochastic programs: Application to cycling network design. Preprint, submitted September 20, https://arxiv.org/abs/2209.09404.Google Scholar
• Dobson G, Nambimadom RS (2001) The batch loading and scheduling problem. Oper. Res. 49(1):52–65.Link, Google Scholar
• Dumouchelle J, Julien E, Kurtz J, Khalil EB (2024) Neur2BiLO: Neural bilevel optimization. Preprint, submitted February 4, https://arxiv.org/abs/2402.02552.Google Scholar
• Fajemisin AO, Maragno D, den Hertog D (2024) Optimization with constraint learning: A framework and survey. Eur. J. Oper. Res. 314(1):1–14.Crossref, Google Scholar
• Fischetti M, Jo J (2018) Deep neural networks and mixed integer linear optimization. Constraints 23(3):296–309.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. 33rd Conf. Neural Inform. Processing Systems, Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 15501–15513.Google Scholar
• Grimstad B, Andersson H (2019) ReLU networks as surrogate models in mixed-integer linear programs. Comput. Chemical Engrg. 131:106580.Crossref, Google Scholar
• Gutiérrez-Sánchez A, Rocha-Medina LB (2022) VRP variants applicable to collecting donations and similar problems: A taxonomic review. Comput. Indust. Engrg. 164:107887.Crossref, Google Scholar
• Gutina D, Bärmann A, Roeder G, Schellenberger M, Liers F (2023) Optimization over decision trees: A case study for the design of stable direct-current electricity networks. Optim. Engrg. 24(4):2651–2691.Crossref, Google Scholar
• Halilbašić L, Thams F, Venzke A, Chatzivasileiadis S, Pinson P (2018) Data-driven security-constrained AC-OPF for operations and markets. 2018 Power Systems Comput. Conf. (PSCC) (IEEE, Piscataway, NJ), 1–7.Google Scholar
• Kaleem W, Lee D, Kwon C, Subramanyam A (2024) Neural embedded mixed-integer optimization for location-routing problems. Preprint, submitted December 7, https://arxiv.org/abs/2412.05665.Google Scholar
• Karimi-Mamaghan M, Mohammadi M, Meyer P, Karimi-Mamaghan AM, Talbi EG (2022) Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art. Eur. J. Oper. Res. 296(2):393–422.Crossref, Google Scholar
• Khalil EB, Le Bodic P, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Schuurmans D, Wellman MP, eds. Proc. Thirtieth AAAI Conf. Artificial Intelligence (AAAI-16) (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Kleijnen JP (2018) Design and Analysis of Simulation Experiments (Springer, New York).Google Scholar
• Kody A, Chevalier S, Chatzivasileiadis S, Molzahn D (2022) Modeling the AC power flow equations with optimally compact neural networks: Application to unit commitment. Electric Power Systems Res. 213:108282.Crossref, Google Scholar
• Matusiak M, De Koster R, Saarinen J (2017) Utilizing individual picker skills to improve order batching in a warehouse. Eur. J. Oper. Res. 263(3):888–899.Crossref, Google Scholar
• Mikić M, Todosijević R, Urošević D (2019) Less is more: General variable neighborhood search for the capacitated modular hub location problem. Comput. Oper. Res. 110:101–115.Crossref, Google Scholar
• Mišić VV (2020) Optimization of tree ensembles. Oper. Res. 68(5):1605–1624.Link, Google Scholar
• Mistry M, Letsios D, Krennrich G, Lee RM, Misener R (2021) Mixed-integer convex nonlinear optimization with gradient-boosted trees embedded. INFORMS J. Comput. 33(3):1103–1119.Link, Google Scholar
• Pardo EG, Gil-Borrás S, Alonso-Ayuso A, Duarte A (2024) Order batching problems: Taxonomy and literature review. Eur. J. Oper. Res. 313(1):1–24.Crossref, Google Scholar
• Patel RM, Dumouchelle J, Khalil E, Bodur M (2022) Neur2SP: Neural two-stage stochastic programming. Adv. Neural Inform. Processing Systems 35:23992–24005.Google Scholar
• Paulus MB, Zarpellon G, Krause A, Charlin L, Maddison C (2022) Learning to cut by looking ahead: Cutting plane selection via imitation learning. Internat. Conf. Machine Learning (PMLR, New York), 17584–17600.Google Scholar
• Pentico DW (2007) Assignment problems: A golden anniversary survey. Eur. J. Oper. Res. 176(2):774–793.Crossref, Google Scholar
• Rigo CA, Seman LO, Morsch Filho E, Camponogara E, Bezerra EA (2023) MPPT aware task scheduling for nanosatellites using MIP-based ReLU proxy models. Expert Systems Appl. 234:121022.Crossref, Google Scholar
• Say B, Wu G, Zhou YQ, Sanner S (2017) Nonlinear hybrid planning with deep net learned transition models and mixed-integer linear programming. Internat. Joint Conf. Artificial Intelligence 2017 (Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto, CA), 750–756.Google Scholar
• Schweidtmann AM, Bongartz D, Mitsos A (2023) Optimization with trained machine learning models embedded. Pardalos PM, Prokopyev OA, eds. Encyclopedia of Optimization (Springer, Cham, Switzerland), 1–8.Crossref, Google Scholar
• Taillard É, Badeau P, Gendreau M, Guertin F, Potvin JY (1997) A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Sci. 31(2):170–186.Link, Google Scholar
• Won J, Olafsson S (2005) Joint order batching and order picking in warehouse operations. Internat. J. Production Res. 43(7):1427–1442.Crossref, Google Scholar
• Wu Y, Song W, Cao Z, Zhang J (2021) Learning large neighborhood search policy for integer programming. Adv. Neural Inform. Processing Systems 34:30075–30087.Google Scholar
• Xue S, Gao C (2026) Learn to formulate: A surrogate model framework for generalized assignment problem with routing constraints. https://doi.org/10.1287/ijoc.2024.0736.cd, https://github.com/INFORMSJoC/2024.0736.Google Scholar
• Yadav N, Tanksale A (2022) An integrated routing and scheduling problem for home healthcare delivery with limited person-to-person contact. Eur. J. Oper. Res. 303(3):1100–1125.Crossref, Google Scholar
• Zhang K, Gao C (2023) Improved formulations of the joint order batching and picker routing problem. Internat. J. Production Res. 61(21):7386–7409.Crossref, Google Scholar
• Zhou J, Shi T, Ren J, He C (2024) Accelerating operation optimization of complex chemical processes: A novel framework integrating artificial neural network and mixed-integer linear programming. Chemical Engrg. J. 481:148421.Crossref, Google Scholar