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] CO w/ DRL, [DOTs] 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, [PyTorch] 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.2020 NeurIPS] (video)
4	9/23	Simulation-based learning – Bandit models [Rutgers CS 550] v1, v2, v3, v4
	9/25	Simulation-based learning – Bandit models and others [Google Talks] TS for Online Decision Making ♦[Kool et al. 2018 ICLR] (video)
		Part II: Data-driven algorithm design
5	9/30	Branch & cut in a MIP solver [CO@Work 2020] MIP solving v1, v2, v3, v4
	10/2	Learn-to-branch / Learn-to-cut [CO@Work 2024] ML augmented B&B, [IPAM 2023] ML in MIP	Report 1
6	10/7	Holiday
	10/9	Holiday
7	10/14	Learn-to-branch / Learn-to-cut ♦[Gasse et al. NeurIPS 2019] (video), [IPAM 2021] RL for IP: Learning to cut	Proposal for the final project
	10/16	Large Neighborhood Search (LNS)
8	10/21	Large Neighborhood Search (LNS)
	10/23	Branch & price – Theory
9	10/28	INFORMS Annual Meeting
	10/30	INFORMS Annual Meeting
10	11/4	Learning for branch & price / column generation ♦	Report 2
	11/6	KIIE Fall Conference
11	11/11	Algorithm with prediction
	11/13	Algorithm with prediction	Highlight talk
12	11/18	Neural algorithmic reasoning, Automated algorithm configuration ♦
		Part III: Data-driven optimization
	11/20	Optimization under uncertainty – Theory	Report 3
13	11/25	Optimization under uncertainty – Data-driven robust optimization
	11/27	Optimization under uncertainty – Data-driven robust optimization ♦
14	12/2	Decision-focused learning
	12/4	Decision-focused learning ♦
		Part IV: Finale
15	12/9	Recent topics – Optimization over a trained neural network, Generative AI ♦
	12/11	Recent topics – Explainable AI	Report 4
16	12/16	Final project presentation
	12/18	Final project presentation	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.