AI for Discrete Optimization (IMEN891N, Fall 2025)

(♦: In-class presentation by students)

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.