AI for Discrete Optimization (IMEN891N, Fall 2025)

(♦: In-class presentation by students)

Part I: Basic AI techniques

Week 1: Introduction

• Motivation and trends: [Stanford MS&E236] Lecture “Introduction” (link), Survey (Bengio et al. 2021)
  • 2021 AAAI Tutorial: Recent Advances in Integrating Machine Learning and Combinatorial Optimization (link)
  • 2024 AI4OPT Seminar: Using Machine Learning for Combinatorial Optimization (ML4CO) (link)
  • 2021 FODSI Workshop: Learning in Graph Neural Networks for Algorithms (link)

Week 1–3: Deep reinforcement learning

• Graph Neural Networks (GNN): [Stanford MS&E236] Lecture “GNNs” (link)
  • Tutorials (Cappart et al. 2023, Angioni et al. 2025)
  • [Stanford CS224W] Lecture 6–8 (link)
• Reinforcement Learning (RL): [Stanford MS&E236] Lecture “Reinforcement learning (Q-learning)” (link)
  • Textbook (Sutton & Barto 2020) Chapter 3–6
  • [Stanford CS234] Lecture 2–6 (link)
• ♦ End-to-end heuristics:
      Routing (Dai et al. 2018, Kool et al. 2018, Deudon et al. 2018)
      Scheduling (Kwon et al. 2020, Park et al. 2021, Kwon et al. 2021)
  • 2023 DIMACS Workshop: Search Heuristics for Solving Routing Problems with Deep Reinforcement Learning (link)
  • 2023 DIMACS Workshop: (Bad) Reinforcement Learning Approaches to Vehicle Routing Problems (link)

Week 4: Simulation-based learning

• Bandit models: Textbook (Sutton & Barto 2020) Chapter 2, Tutorial (Agrawal 2019)
  • Monographs (Lattimore & Szepesvári 2020, Slivkins 2019)
  • 2019 INFORMS TutORial: Recent Advances in Multiarmed Bandits (link)
• Bayesian optimization (Frazier 2018, Theodoridis 2015)
  • 2018 INFORMS TutORial: Bayesian Optimization (link)

Part I — Reading list

• Bengio, Y., Lodi, A., & Prouvost, A. (2021). Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2), 405–421.

• Cappart, Q., Chételat, D., Khalil, E. B., Lodi, A., Morris, C., & Veličković, P. (2023). Combinatorial Optimization and Reasoning with Graph Neural Networks. Journal of Machine Learning Research, 24(130), 1–61.

• Angioni, D., Archetti, C., & Speranza, M. G. (2025). Neural combinatorial optimization: A tutorial. Computers & Operations Research, 182, 107102. (link)

• Sutton, R. S., & Barto, A. G. (2020). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.

• Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., & Song, L. (2018). Learning Combinatorial Optimization Algorithms over Graphs.

• Kool, W., van Hoof, H., & Welling, M. (2018). Attention, Learn to Solve Routing Problems! In ICLR.

• Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., & Rousseau, L.-M. (2018). Learning Heuristics for the TSP by Policy Gradient. In CPAIOR (LNCS), 170–181. (link)

• Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., & Min, S. (2020). POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. In NeurIPS, 33, 21188–21198.

• Park, J., Chun, J., Kim, S. H., Kim, Y., & Park, J. (2021). Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59(11), 3360–3377. (link)

• Kwon, Y.-D., Choo, J., Yoon, I., Park, M., Park, D., & Gwon, Y. (2021). Matrix encoding networks for neural combinatorial optimization. In NeurIPS, 34, 5138–5149.

• Agrawal, S. (2019). Recent Advances in Multiarmed Bandits for Sequential Decision Making. In INFORMS TutORials in Operations Research, 167–188. (link)

• Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. (link)

• Slivkins, A. (2019). Introduction to Multi-Armed Bandits. Foundations and Trends® in Machine Learning, 12(1–2), 1–286. (link)

• Frazier, P. I. (2018). Bayesian Optimization. In INFORMS TutORials in Operations Research, 255–278. (link)

• Theodoridis, S. (2015). Machine Learning: A Bayesian and Optimization Perspective. Academic Press.

Part II: Data-driven algorithm design

Week 5–7: Branch & cut in a MIP solver

• Theory class (Achterberg 2009)
  • CO@Work 2024 Lecture: Section “The Fundamentals of MIP” (link)
• ♦ Learn-to-branch (Khalil et al. 2016, Lodi & Zarpellon 2017, Balcan et al. 2018), Learn-to-cut (Deza & Khalil 2023, Scavuzzo et al. 2024)
  • 2023 Gurobi Days Digital: On The Interplay Between Learning And Optimization And Its Effect On MIP Solving (by Andrea Lodi @ Cornell Tech) (link)
  • 2023 IPAM Workshop: Machine Learning for MIP Solving (by Bistra Dilkina @ University of Southern California) (link)
• Proposal of the final project

Week 7-8: Large Neighborhood Search (LNS) heuristics

• Theory class (Pisinger & Ropke 2019, Windras Mara et al. 2022, Voigt 2025)
• ♦ Learning applications: MIP (Song et al. 2020, Wu et al. 2021, Hendel 2022), Routing (Hottung & Tierney 2020, Ma et al. 2022, Qin et al. 2022), Scheduling (Zhang et al. 2023, Li et al. 2025)
  • 2022 CPAIOR Keynote: Deep Learning and Neural Network Accelerators for Combinatorial Optimization (by Vinod Nair @ Google) (link)
  • LNS (link) and Adaptive LNS for MIP (by Krunal Patel @ Polytechnique Montréal) (link)

Week 8-10: Branch & price algorithms

• Theory class (Desrosiers et al. 2025, Uchoa et al. 2024)
  • CO@Work 2024 Lecture: “Branch-and-Price Crash Course” (link)
  • CO@Work 2020 Lecture: “Column Generation, Dantzig-Wolfe, Branch-Price-and-Cut” (link)
• ♦ Learning for column generation: Scheduling (Koutecká et al. 2025, Václavík et al. 2018), Routing (Morabit et al. 2021), Graph problems (Shen et al. 2022, Sun et al. 2023)
  • 2025 Scheduling Seminar: Machine Learning Inside Decomposition of Scheduling Problems (by Přemysl Šůcha @ CTU in Prague) (link)

Week 11-12: Algorithms without a solver

• Data-driven algorithm design: [Stanford MS&E236] Lecture “Algorithms with predictions” (link), Survey (Balcan 2021, Gupta & Roughgarden 2020, Mitzenmacher & Vassilvitskii 2022)
  • 2022 Simons Institute Boot Camp: Machine Learning for Algorithm Design (by Ellen Vitercik @ Stanford University) (link)
• ♦ Automated algorithm configuration: Survey (Schede et al. 2022), irace package (López-Ibáñez et al. 2016)
  • 2023 AutoML Conference Tutorial: A Survey for Automated Algorithm Configuration (Viktor Bengs @ LMU Munich et al.) (link)
• ♦ (Optional) Neural algorithmic reasoning: [Stanford MS&E236] Lecture “Neural algorithmic reasoning” (link), Seminal works (Veličković & Blundell 2021, Cappart et al. 2023)
  • 2022 Learning on Graphs Conference Tutorial: Neural Algorithmic Reasoning (by Petar Veličković @ DeepMind et al.) (link)

Part II — Reading list

• Achterberg, Tobias (2009). SCIP: Solving Constraint Integer Programs. Mathematical Programming Computation, 1(1), 1–41. (link)
• Khalil, Elias, Bodic, Pierre Le, Song, Le, Nemhauser, George, Dilkina, Bistra (2016). Learning to Branch in Mixed Integer Programming. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). (link)
• Lodi, Andrea, Zarpellon, Giulia (2017). On learning and branching: a survey. TOP, 25(2), 207–236. (link)
• Balcan, Maria-Florina, Dick, Travis, Sandholm, Tuomas, Vitercik, Ellen (2018). Learning to Branch. Proceedings of the 35th International Conference on Machine Learning, 344–353. (link)
• Deza, Arnaud, Khalil, Elias B. (2023). Machine Learning for Cutting Planes in Integer Programming: A Survey. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 6592–6600. (link)
• Scavuzzo, Lara, Aardal, Karen, Lodi, Andrea, Yorke-Smith, Neil (2024). Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming. Mathematical Programming. (link)
• Pisinger, David, Ropke, Stefan (2019). Large Neighborhood Search. Handbook of Metaheuristics, 99–127. (link)
• Windras Mara, Setyo Tri, Norcahyo, Rachmadi, Jodiawan, Panca, Lusiantoro, Luluk, Rifai, Achmad Pratama (2022). A Survey of Adaptive Large Neighborhood Search Algorithms and Applications. Computers & Operations Research, 146, 105903. (link)
• Voigt, Stefan (2025). A Review and Ranking of Operators in Adaptive Large Neighborhood Search for Vehicle Routing Problems. European Journal of Operational Research, 322(2), 357–375. (link)
• Song, Jialin, Lanka, Ravi, Yue, Yisong, Dilkina, Bistra (2020). A General Large Neighborhood Search Framework for Solving Integer Linear Programs. Advances in Neural Information Processing Systems, 33, 20012–20023.
• Wu, Yaoxin, Song, Wen, Cao, Zhiguang, Zhang, Jie (2021). Learning Large Neighborhood Search Policy for Integer Programming. Advances in Neural Information Processing Systems, 34, 30075–30087.
• Hendel, Gregor (2022). Adaptive Large Neighborhood Search for Mixed Integer Programming. Mathematical Programming Computation, 14(2), 185–221. (link)
• Hottung, André, Tierney, Kevin (2020). Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem. ECAI 2020, 443–450. (link)
• Ma, Yining, Li, Jingwen, Cao, Zhiguang, Song, Wen, Guo, Hongliang, Gong, Yuejiao, Chee, Yeow Meng (2022). Efficient Neural Neighborhood Search for Pickup and Delivery Problems. Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 4776–4784. (link)
• Qin, Zhiwei (Tony), Zhu, Hongtu, Ye, Jieping (2022). Reinforcement Learning for Ridesharing: An Extended Survey. Transportation Research Part C: Emerging Technologies, 144, 103852. (link)
• Zhang, Cong, Cao, Zhiguang, Song, Wen, Wu, Yaoxin, Zhang, Jie (2023). Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling. The Twelfth International Conference on Learning Representations.
• Li, Sirui, Ouyang, Wenbin, Ma, Yining, Wu, Cathy (2025). Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling. The Thirteenth International Conference on Learning Representations.
• Desrosiers, Jacques, Lübbecke, Marco, Desaulniers, Guy, Gauthier, Jean Bertrand (2025). Branch-and-Price. Springer.
• Uchoa, Eduardo, Pessoa, Artur, Moreno, Lorenza (2024). Optimizing with Column Generation: Advanced Branch-Cut-and-Price Algorithms (Part I).
• Koutecká, Pavlína, Šůcha, Přemysl, Hůla, Jan, Maenhout, Broos (2025). A Machine Learning Approach to Rank Pricing Problems in Branch-and-Price. European Journal of Operational Research, 320(2), 328–342. (link)
• Václavík, Roman, Novák, Antonín, Šůcha, Přemysl, Hanzálek, Zdeněk (2018). Accelerating the Branch-and-Price Algorithm Using Machine Learning. European Journal of Operational Research, 271(3), 1055–1069. (link)
• Morabit, Mouad, Desaulniers, Guy, Lodi, Andrea (2021). Machine-Learning–Based Column Selection for Column Generation. Transportation Science, 55(4), 815–831. (link)
• Shen, Yunzhuang, Sun, Yuan, Li, Xiaodong, Eberhard, Andrew, Ernst, Andreas (2022). Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 9926–9934. (link)
• Sun, Yuan, Ernst, Andreas T., Li, Xiaodong, Weiner, Jake (2023). Learning to Generate Columns with Application to Vertex Coloring. The Eleventh International Conference on Learning Representations.
• Maria-Florina Balcan (2021). Data-Driven Algorithm Design. In Tim Roughgarden (ed.), Beyond the Worst-Case Analysis of Algorithms, 626–645. Cambridge University Press, Cambridge. (link)
• Rishi Gupta, & Tim Roughgarden (2020). Data-driven algorithm design. Commun. ACM, 63(6), 87–94. (link)
• Michael Mitzenmacher, & Sergei Vassilvitskii (2022). Algorithms with predictions. Commun. ACM, 65(7), 33–35. (link)
• Elias Schede, Jasmin Brandt, Alexander Tornede, Marcel Wever, Viktor Bengs, Eyke Hüllermeier, & Kevin Tierney (2022). A Survey of Methods for Automated Algorithm Configuration. Journal of Artificial Intelligence Research, 75, 425–487. (link)
• Manuel López‑Ibáñez, Jérémie Dubois‑Lacoste, Leslie Pérez Cáceres, Mauro Birattari, & Thomas Stützle (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3, 43–58. (link)
• Petar Veličković, & Charles Blundell (2021). Neural algorithmic reasoning. Patterns, 2(7), 100273. (link)
• Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, & Petar Veličković (2023). Combinatorial Optimization and Reasoning with Graph Neural Networks. Journal of Machine Learning Research, 24(130), 1–61.

Part III: Data-driven optimization

Week 12-13: Optimization under uncertainty

• Theory in robust optimization (Bertsimas et al. 2011, Gorissen et al. 2015, Bertsimas & den Hertog 2022)
  • 2005 Robust and Adaptive Optimization: A Tractable Approach to Optimization Under Uncertainty (by Dimitris Bertsimas @ MIT) (link)
  • 2019 DTU Seminar: Adaptive Robust Optimization and its Applications to Power Systems (by Antonio J. Conejo @ Ohio State University) (link)
• ♦ Data-driven robust optimization (Bertsimas et al. 2018, Goerigk & Kurtz 2023, Ning & You 2018)
  • 2017 AIChE Webinar: Machine Learning and Robust Optimization (by Fengqi You @ Cornell University) (link)
  • 2024 Robust Optimization Webinar: Learning for Decision-Making under Uncertainty (by Bartolomeo Stellato @ Princeton University) (link)

Week 14: Decision-focused learning

• ♦ Decision-focused learning (Wilder et al. 2019, Mandi et al. 2024)
  • 2024 CPAIOR Keynote: Decision-Focused Learning: Foundations, State of Art, Benchmarking & Opportunities (by Tias Guns @ KU Leuven) (link)
• ♦ Predict-then-optimize (Elmachtoub & Grigas 2022, Mandi et al. 2020, Tang & Khalil 2024)
  • 2022 CPAIOR Master Class: Learning, Optimization, and Generalization in the Predict-then-Optimize Setting (by Tias Guns @ KU Leuven) (link)
  • 2023 ACP Summer School: Predict-then-Optimize (by Elias B. Khalil @ University of Toronto) (link)

Part III — Reading list

• Bertsimas, Dimitris, Brown, David B., Caramanis, Constantine (2011). Theory and Applications of Robust Optimization. SIAM Review, 53(3), 464–501. (link)
• Gorissen, Bram L., Yanıkoğlu, İhsan, den Hertog, Dick (2015). A Practical Guide to Robust Optimization. Omega, 53, 124–137. (link)
• Bertsimas, Dimitris, den Hertog, D. (2022). Robust and Adaptive Optimization. Dynamic Ideas LLC.
• Bertsimas, Dimitris, Gupta, Vishal, Kallus, Nathan (2018). Data-Driven Robust Optimization. Mathematical Programming, 167(2), 235–292. (link)
• Goerigk, Marc, Kurtz, Jannis (2023). Data-Driven Robust Optimization Using Deep Neural Networks. Computers & Operations Research, 151, 106087. (link)
• Ning, Chao, You, Fengqi (2018). Data-Driven Stochastic Robust Optimization: General Computational Framework and Algorithm Leveraging Machine Learning for Optimization under Uncertainty in the Big Data Era. Computers & Chemical Engineering, 111, 115–133. (link)
• Wilder, Bryan, Dilkina, Bistra, Tambe, Milind (2019). Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1658–1665. (link)
• Mandi, Jayanta, Kotary, James, Berden, Senne, Mulamba, Maxime, Bucarey, Victor, Guns, Tias, Fioretto, Ferdinando (2024). Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities. Journal of Artificial Intelligence Research, 80, 1623–1701. (link)
• Elmachtoub, Adam N., Grigas, Paul (2022). Smart “Predict, Then Optimize”. Management Science, 68(1), 9–26. (link)
• Mandi, Jayanta, Demirović, Emir, Stuckey, Peter J., Guns, Tias (2020). Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 34, 1603–1610. (link)
• Tang, Bo, Khalil, Elias B. (2024). PyEPO: A PyTorch-based End-to-End Predict-Then-Optimize Library for Linear and Integer Programming. Mathematical Programming Computation, 16(3), 297–335. (link)

Part IV: Finale

Week 15: Recent topics

• Optimization over a trained neural network (Anderson et al. 2020, Bunel et al. 2020)
  • 2021 IPAM Workshop: Neural network verification as piecewise linear optimization (by Joseph Huchette @ Rice University) (link)
• ♦ Generative AI: Large language models (Wasserkrug et al. 2025, Ahmaditeshnizi et al. 2024, Huang et al. 2025), Foundation models (Li et al. 2024, Berto et al. 2024), Diffusion models, etc
  • 2024 Women in Data Science and Maths Seminar: AI and the Future of Optimization (by Madeleine Udell @ Stanford University) (link)
  • 2025 AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms (by AlphaEvolve team @ Google DeepMind) (link)
  • Combining Large Language Models and OR/MS to Make Smarter Decisions (by Boussioux @ University of Washington, and Wei Sun @ IBM Research) (link)
• (Optional) Explainable AI: Survey (De Bock et al. 2024, Bertsimas 2019), Counterfactual explanations (Guidotti 2022, Carrizosa et al. 2024, Maragno et al. 2024), Tree-based explanations, Neurosymbolic AI, …
  • 2022 NeEDS Seminar: The Counterfactual Explanation—Yet More Algorithms as a Solution to Explain Complex Models? (by David Martens @ University of Antwerp) (link)
  • 2021 GdR RO Seminar: Combinatorial optimization and interpretable machine learning (by Thibaut Vidal @ Ecole Polytechnique Montréal) (link)

Part IV — Reading list

• Anderson, Ross, Huchette, Joey, Ma, Will, Tjandraatmadja, Christian, Vielma, Juan Pablo (2020). Strong Mixed-Integer Programming Formulations for Trained Neural Networks. Mathematical Programming, 183(1), 3–39. (link)
• Bunel, Rudy, Lu, Jingyue, Turkaslan, Ilker, Torr, Philip H. S., Kohli, Pushmeet, Kumar, M. Pawan (2020). Branch and Bound for Piecewise Linear Neural Network Verification. Journal of Machine Learning Research, 21(42), 1–39.
• Wasserkrug, Segev, Boussioux, Leonard, den Hertog, Dick, Mirzazadeh, Farzaneh, Birbil, Ş. İlker, Kurtz, Jannis, Maragno, Donato (2025). Enhancing Decision Making Through the Integration of Large Language Models and Operations Research Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 39(27), 28643–28650. (link)
• Ahmaditeshnizi, Ali, Gao, Wenzhi, Udell, Madeleine (2024). OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models. Proceedings of the 41st International Conference on Machine Learning, 577–596.
• Huang, Chenyu, Tang, Zhengyang, Hu, Shixi, Jiang, Ruoqing, Zheng, Xin, Ge, Dongdong, Wang, Benyou, Wang, Zizhuo (2025). ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling. Operations Research. (link)
• Li, Sirui, Kulkarni, Janardhan, Menache, Ishai, Wu, Cathy, Li, Beibin (2024). Towards Foundation Models for Mixed Integer Linear Programming. The Thirteenth International Conference on Learning Representations.
• Berto, Federico, Hua, Chuanbo, Zepeda, Nayeli Gast, Hottung, Andre, Wouda, Niels, Lan, Leon, Tierney, Kevin, Park, Jinkyoo (2024). RouteFinder: Towards Foundation Models for Vehicle Routing Problems. ICML 2024 Workshop on Foundation Models in the Wild.
• De Bock, Koen W., Coussement, Kristof, Caigny, Arno De, Słowinski, Roman, Baesens, Bart, Boute, Robert N., Choi, Tsan-Ming, Delen, Dursun, Kraus, Mathias, Lessmann, Stefan, Maldonado, Sebastian, Martens, David, Oskarsdottir, Maria, Vairetti, Carla, Verbeke, Wouter, Weber, Richard (2024). Explainable AI for Operational Research: A Defining Framework, Methods, Applications, and a Research Agenda. European Journal of Operational Research, 317(2), 249–272. (link)
• Bertsimas, Dimitris (2019). Machine Learning Under a Modern Optimization Lens. Dynamic Ideas LLC.
• Guidotti, Riccardo (2022). Counterfactual Explanations and How to Find Them: Literature Review and Benchmarking. Data Mining and Knowledge Discovery. (link)
• Carrizosa, Emilio, Ramirez-Ayerbe, Jasone, Romero Morales, Dolores (2024). Mathematical Optimization Modelling for Group Counterfactual Explanations. European Journal of Operational Research, 319(2), 399–412. (link)
• Maragno, Donato, Kurtz, Jannis, Rober, Tabea E., Goedhart, Rob, Birbil, Ş. İlker, den Hertog, Dick (2024). Finding Regions of Counterfactual Explanations via Robust Optimization. INFORMS Journal on Computing, 36(5), 1316–1334. (link)