AI for Discrete Optimization (IMEN891N, Fall 2025)

Introduction

Recent progress in Artificial Intelligence (AI) has demonstrated its power to tackle NP-hard discrete optimization problems and improve the decision-making process. Numerous research articles have been published in both traditional Operations Research (OR) journals and top AI conferences, reflecting increasing interest in this emerging field.

This course is designed to prepare students to conduct their own research at the intersection of AI and discrete optimization. We will focus primarily on scheduling and routing problems, graph optimization problems, and general mixed-integer programming (MIP). The course will cover two core topics:

(i) Data-driven algorithm design: Using AI to improve the performance of optimization algorithms
(ii) Data-driven optimization: Leveraging learned data to make better decisions under uncertainty.

Prerequisites

Strongly recommended

IMEN662 Discrete Optimization
IMEN260 Operations Research I (or IMEN661 Advanced Linear Programming)
IMEN272 Probability and Statistics for Engineers (or equivalent)

Not required, but useful

IMEN764 Dynamic Programming & Reinforcement Learning Applications (or CSED627 Reinforcement Learning)
Basic concepts in various machine learning models
- Only deep reinforcement learning and bandit models will be quickly reviewed

Course Logistics

The course is designed to be comprehensive and interactive with the components below. For each topic, a list of reading materials will be provided. Students may propose additional papers to instructor for discussion.

Lecture: The instructor will present the main concepts and techniques.
In-class presentation: Some classes will be reserved for student presentations. An assigned team must select a research paper among the given list and explain it to the class (25 minutes). Each student must be involved in at least one presentation.
Referee report: At the end of each topic, students must select a research paper from the given list and write a referee report with critical analysis (min 2 pages, similar to a peer-review in a AI conference). During the course, four reports will be assigned.
Final project: Students in a team will develop a new method that applies AI to discrete optimization.
- A proposal must be submitted at the end of week 6 (max 2 pages).
- In week 11, a highlight talk will be given by each team (5 minutes).
- The final results will be presented at the end of the course (30 minutes), which will be peer-reviewed by other students.
- A final report must be submitted (max 16 pages).
- The results should include an evaluation of the proposed method unless it is theoretical.

Grade policy

In-class presentation: 15%
Referee reports: 25%
Final project: 50%
Participation and attendance: 10%

Course Schedule

(♦: Potential slots for in-class presentation by students)

Week	Date	Topic(s)	Assignment due dates
		Part I: Basic AI techniques
1	9/2	Introduction: Motivation & trends [DOTs 23] CO w/ DRL, [DOTs 24] AI OPT modeling
	9/4	Deep Reinforcement Learning (DRL) – Graph Neural Networks (GNN) [Stanford CS224W] Lecture 6.2, 6.3, 7.1
2	9/9	Deep Reinforcement Learning (DRL) – Graph Neural Networks (GNN) [Stanford CS224W] Lecture 7.2, 7.3, [Google Talks 21] Intro to GNN
	9/11	Deep Reinforcement Learning (DRL) – Basic reinforcement learning [MIT 6.S091] Intro to DRL, [Stanford CS231n] DRL	Team formation
3	9/16	Deep Reinforcement Learning (DRL) – Basic reinforcement learning [Stanford CS234] Q-Learning, VFA, Policy Gradient
	9/18	Applications of DRL: Routing and scheduling problems [Stanford CS234] PPO, ♦[Kwon et al. NeurIPS 20] (video)
4	9/23	Simulation-based learning – Bandit models [Rutgers CS 550] v1, v2, v3, v4
	9/25	Simulation-based learning – Thompson sampling [Google Talks] TS for Online Decision Making ♦[Kool et al. ICLR 18] (video)
		Part II-1: Data-driven algorithm design: MIP solving
5	9/30	Branch & cut in a MIP solver [CO@Work 20] MIP solving v1, v2, v3, v4
	10/2	Learn-to-branch [CO@Work 24] ML augmented B&B, [IPAM 23] ML in MIP	Report 1
6	10/7	Holiday
	10/9	Holiday
7	10/14	Learn-to-branch ♦[Gasse et al. NeurIPS 19] (video)	Proposal for the final project
	10/16	Learn-to-cut [IPAM 21] RL for IP: Learning to cut
8	10/21	Learn-to-cut / Other topics in MIP solving
	10/23	Large Neighborhood Search (LNS) [AI4OPT 25] Synergy of ML and Comb. Solver, [IPAM 21] Solving MIP using NN
9	10/28	INFORMS Annual Meeting
	10/30	INFORMS Annual Meeting
10	11/4	Learning for branch & price / column generation [CO@Work 24] B&P Crash Course, [Scheduling Seminar 25] ML inside Decomposition
	11/6	Learning for branch & price / column generation
		Part II-2: Data-driven algorithm design: Combinatorial algorithms
11	11/11	Algorithm with prediction [Simons Inst. 22] ML for Algorithm Design, [UniBonn MA-INF1218] Ski Rental	Report 2
	11/13	Neural algorithmic reasoning [DS4DM 23] Melting Pot of NAR, [LoG 2022] Tutorial: NAR
12	11/18	Highlight talk (Student presentation)	Highlight talk
	11/20	Automated algorithm configuration [PPSN 20] Tutorial on Alg Config, [UAI 18] Bayesian Optimization
13	11/25	Automated algorithm configuration - Runtime analysis [AutoML 23] Survey for AAC
	11/27	Automated algorithm configuration - Generalization bounds [IPAM 21] How much data is sufficient …?
		Part III: Data-driven optimization
14	12/2	Optimization under uncertainty – Theory [Purdue CHE597] Stoc. Prog. and Benders
	12/4	Decision-focused learning [CPAIOR 24] DFL Tutorial, [RPI Seminar] Predict-then-optimize	Report 3
15	12/9	Data-driven robust optimization, Optimization over a trained neural network (lectures give as videos) [CO@Work 24] DL in RO, [Gurobi Webinar 25] Opt. over NN, In-class presentations ♦
		Part IV: Finale
	12/11	Recent topics – Large language models, Explainable AI (video lectures)
16	12/16	Final project presentation
	12/18	Final project presentation	Report 4, Final report

Note:

The corresponding reading materials and videos can be found here.
Students must select papers from the listed journals and conferences
The classes in Week 4 will be delivered online due to the instructor’s business trip.
Potential make-up classes are colored in blue.
- Video lectures for Part III may be provided instead.
Another make-up class for term project presentation in Week 16 may be scheduled.

Useful information

Resources – A list of useful resources for this course.
Previous Academic Events – A list of previous academic events related to this course.

Reference for in-class presentation

Week 3, 9/18 (Presentation: Group 1; Discussion: Kyungduk Moon)
- 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.
Week 4, 9/25 (Presentation: Group 5; Discussion: Group 3)
- Kool, W., van Hoof, H., & Welling, M. (2018). Attention, Learn to Solve Routing Problems! In ICLR.
Week 7, 10/12 (Presentation: Group 4; Discussion: Group 2)
- Gasse, M., Chetelat, D., Ferroni, N., Charlin, L., & Lodi, A. (2019). Exact Combinatorial Optimization with Graph Convolutional Neural Networks. In NeurIPS, 32.
Week 15, 12/9 (Presentation: Group 3; Discussion: Group 1)
- Zhang, X., Chen, L., Gendreau, M., & Langevin, A. (2022). Learning-Based Branch-and-Price Algorithms for the Vehicle Routing Problem with Time Windows and Two-Dimensional Loading Constraints. INFORMS Journal on Computing, 34(3), 1419–1436.
Week 15, 12/9 (Presentation: Group 2; Discussion: Group 4)
- Ferber, A., Wilder, B., Dilkina, B., & Tambe, M. (2020). MIPaaL: Mixed Integer Program as a Layer. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), Article 02.
Week 15, 12/9 (Presentation: Kyungduk Moon; Discussion: Group 5)
- Fischetti, M., & Jo, J. (2018). Deep neural networks and mixed integer linear optimization. Constraints, 23(3), 296–309.