Machine Learning–Augmented Optimization of Large Bilevel and Two-Stage Stochastic Programs: Application to Cycling Network Design

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):3–39.Crossref, Google Scholar
• Ban GY, Rudin C (2019) The big data newsvendor: Practical insights from machine learning. Oper. Res. 67(1):90–108.Link, Google Scholar
• Bard JF (2013) Practical Bilevel Optimization, Algorithms and Applications, vol. 30 (Springer Science & Business Media, Boston).Google Scholar
• Bertsimas D, Kallus N (2020) From predictive to prescriptive analytics. Management Sci. 66(3):1025–1044.Link, Google Scholar
• Bertsimas D, Mundru N (2023) Optimization-based scenario reduction for data-driven two-stage stochastic optimization. Oper. Res. 71(4):1343–1361.Link, Google Scholar
• Bickel PJ, Breiman L (1983) Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test. Ann. Probab. 11(1):185–214.Crossref, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming, Springer Series in Operations Research and Financial Engineering (Springer Science & Business Media, New York).Crossref, Google Scholar
• Boutilier JJ, Chan TCY (2020) Ambulance emergency response optimization in developing countries. Oper. Res. 68(5):1315–1334.Link, Google Scholar
• Buehler R, Dill J (2016) Bikeway networks: A review of effects on cycling. Transportation Rev. 36(1):9–27.Crossref, Google Scholar
• Carrión M, Arroyo JM, Conejo AJ (2009) A bilevel stochastic programming approach for retailer futures market trading. IEEE Trans. Power Systems 24(3):1446–1456.Crossref, Google Scholar
• Carvalho M, Dragotto G, Feijoo F, Lodi A, Sankaranarayanan S (2024) When Nash meets Stackelberg. Management Sci. 70(10):7308–7324.Link, Google Scholar
• Chen X, Sim M, Sun P, Zhang J (2008) A linear decision-based approximation approach to stochastic programming. Oper. Res. 56(2):344–357.Link, Google Scholar
• City of Toronto (2020) City of Toronto open data. Accessed September 15, 2020, https://www.toronto.ca/city-government/data-research-maps/open-data/.Google Scholar
• City of Toronto (2021a) 2021 cycling network plan update. Accessed July 8, 2022, https://www.toronto.ca/legdocs/mmis/2021/ie/bgrd/backgroundfile-173663.pdf.Google Scholar
• City of Toronto (2021b) ActiveTO: Lessons learned from 2020 and next steps for 2021. Accessed July 21, 2022, https://www.toronto.ca/legdocs/mmis/2021/ie/bgrd/backgroundfile-164864.pdf.Google Scholar
• City of Toronto (2024a) Cycling impact analysis. Accessed September 4, 2024, https://www.toronto.ca/legdocs/mmis/2024/ie/bgrd/backgroundfile-245676.pdf.Google Scholar
• City of Toronto (2024b) Cycling network plan update (2025-2027). Accessed September 4, 2024, https://www.toronto.ca/legdocs/mmis/2024/ie/bgrd/backgroundfile-245671.pdf.Google Scholar
• Cleveland WS, Devlin SJ (1988) Locally weighted regression: An approach to regression analysis by local fitting. J. Amer. Statist. Assoc. 83(403):596–610.Crossref, Google Scholar
• Cole E, Yang X, Wilber K, Mac Aodha O, Belongie S (2022) When does contrastive visual representation learning work? 2022 IEEE/CVF Conf. Comput. Vision Pattern Recognition (CVPR) (IEEE, Piscataway, NJ), 14755–14764.Google Scholar
• Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann. Oper. Res. 153:235–256.Crossref, Google Scholar
• Crainic TG, Hewitt M, Rei W (2014) Scenario grouping in a progressive hedging-based meta-heuristic for stochastic network design. Comput. Oper. Res. 43:90–99.Crossref, Google Scholar
• Dill J, McNeil N (2016) Revisiting the four types of cyclists: Findings from a national survey. Transportation Res. Record 2587(1):90–99.Crossref, Google Scholar
• Dupačová J, Gröwe-Kuska N, Römisch W (2003) Scenario reduction in stochastic programming. Math. Programming 95(3):493–511.Crossref, Google Scholar
• Elmachtoub AN, Grigas P (2022) Smart “predict, then optimize.” Management Sci. 68(1):9–26.Link, Google Scholar
• Furth PG, Mekuria MC, Nixon H (2016) Network connectivity for low-stress bicycling. Transportation Res. Record 2587(1):41–49.Crossref, Google Scholar
• Gonzalez TF (1985) Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 38:293–306.Crossref, Google Scholar
• Imani AF, Miller EJ, Saxe S (2019) Cycle accessibility and level of traffic stress: A case study of Toronto. J. Transport Geography 80:102496.Crossref, Google Scholar
• Keutchayan J, Ortmann J, Rei W (2023) Problem-driven scenario clustering in stochastic optimization. Comput. Management Sci. 20(1):13.Crossref, Google Scholar
• Khalil E, Dai H, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. von Luxburg U, Guyon I, Bengio S, Wallach H, Fergus R, eds. NIPS’17: Proc. 31st Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 6351–6361.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, Washington, DC).Google Scholar
• Kouw WM, Loog M (2019) A review of domain adaptation without target labels. IEEE Trans. Pattern Anal. Machine Intelligence 43(3):766–785.Crossref, Google Scholar
• Kraus S, Koch N (2021) Provisional COVID-19 infrastructure induces large, rapid increases in cycling. Proc. Natl. Acad. Sci. USA 118(15):e2024399118.Crossref, Google Scholar
• Leal M, Ponce D, Puerto J (2020) Portfolio problems with two levels decision-makers: Optimal portfolio selection with pricing decisions on transaction costs. Eur. J. Oper. Res. 284(2):712–727.Crossref, Google Scholar
• Li X, Sun H, Teo CP (2022) Convex optimization for bundle size pricing problem. Management Sci. 68(2):1095–1106.Link, Google Scholar
• Lim J, Dalmeijer K, Guhathakurta S, Van Hentenryck P (2021) The bicycle network improvement problem: Optimization algorithms and a case study in Atlanta. J. Transportation Engrg. Part A: Systems 148(11):12558–12570.Google Scholar
• Lin B, Chan TCY, Saxe S (2021) The impact of COVID-19 cycling infrastructure on low-stress cycling accessibility: A case study in the City of Toronto. Findings (February 12), https://findingspress.org/article/19069-the-impact-of-covid-19-cycling-infrastructure-on-low-stress-cycling-accessibility-a-case-study-in-the-city-of-toronto.Google Scholar
• Liu S, He L, Shen ZJM (2021) On-time last-mile delivery: Order assignment with travel-time predictors. Management Sci. 67(7):4095–4119.Link, Google Scholar
• Liu S, Shen ZJM, Ji X (2022) Urban bike lane planning with bike trajectories: Models, algorithms, and a real-world case study. Manufacturing Service Oper. Management 24(5):2500–2515.Link, Google Scholar
• Liu H, Szeto W, Long J (2019) Bike network design problem with a path-size logit-based equilibrium constraint: Formulation, global optimization, and matheuristic. Transportation Res. Part E: Logist. Transportation Rev. 127:284–307.Crossref, Google Scholar
• Liu S, Siddiq A, Zhang J (2024) Planning bike lanes with data: Ridership, congestion, and path selection. Management Sci., ePub ahead of print December 27, https://doi.org/10.1287/mnsc.2022.00775. Google Scholar
• Magnanti TL, Mireault P, Wong RT (1986) Tailoring benders decomposition for uncapacitated network design. Gallo G, Sandi C, eds. Netflow at Pisa, Mathematical Programming Studies, vol. 26 (Springer, Berlin, Heidelberg), 112–154.Crossref, Google Scholar
• Mauttone A, Mercadante G, Rabaza M, Toledo F (2017) Bicycle network design: Model and solution algorithm. Transportation Res. Procedia 27:969–976.Crossref, Google Scholar
• Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J (2013) Distributed representations of words and phrases and their compositionality. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. NIPS’13: Proc. 27th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 3111–3119.Google Scholar
• Mišić VV (2020) Optimization of tree ensembles. Oper. Res. 68(5):1605–1624.Link, 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
• Olmos LE, Tadeo MS, Vlachogiannis D, Alhasoun F, Alegre XE, Ochoa C, Targa F, González MC (2020) A data science framework for planning the growth of bicycle infrastructures. Transportation Res. Part C: Emerging Tech. 115:102640.Crossref, Google Scholar
• Parzen E (1962) On estimation of a probability density function and mode. Ann. Math. Statist. 33(3):1065–1076.Crossref, Google Scholar
• Perozzi B, Al-Rfou R, Skiena S (2014) DeepWalk: Online learning of social representations. Proc. 20th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 701–710.Google Scholar
• Radford A, Narasimhan K, Salimans T, Sutskever I (2018) Improving language understanding by generative pre-training. Preprint, submitted June 11, https://openai.com/research/language-unsupervised.Google Scholar
• Römisch W, Schultz R (1991) Stability analysis for stochastic programs. Ann. Oper. Res. 30(1):241–266.Crossref, Google Scholar
• Statistics Canada (2016) Population and dwelling count, 2016 census. Accessed November 15, 2020, https://www12.statcan.gc.ca/census-recensement/2016/dp-pd/hlt-fst/pd-pl/Table.cfm?Lang=Eng&T=1902&PR=35&S=3&O=D&RPP=50.Google Scholar
• Stone CJ (1977) Consistent nonparametric regression. Ann. Statist. 5(4):595–620.Crossref, Google Scholar
• White DJ, Anandalingam G (1993) A penalty function approach for solving bi-level linear programs. J. Global Optim. 3(4):397–419.Crossref, Google Scholar
• Wu Y, Song W, Cao Z, Zhang J (2022) Learning scenario representation for solving two-stage stochastic integer programs. Internat. Conf. Learning Representations (OpenReview.net).Google Scholar
• Zhang W, Wang K, Jacquillat A, Wang S (2023) Optimized scenario reduction: Solving large-scale stochastic programs with quality guarantees. INFORMS J. Comput. 35(4):886–908.Link, Google Scholar
• Zugno M, Morales JM, Pinson P, Madsen H (2013) A bilevel model for electricity retailers’ participation in a demand response market environment. Energy Econom. 36:182–197.Crossref, Google Scholar