Recent Advances in Integrating Machine Learning and Combinatorial Optimization - Tutorial at AAAI-21

AAAI 2021

Presented by: Elias B. Khalil (University of Toronto), Andrea Lodi (Polytechnique Montréal), Bistra Dilkina (University of Southern California), Didier Chételat (Polytechnique Montréal), Maxime Gasse (Polytechnique Montréal), Antoine Prouvost (Polytechnique Montréal), Giulia Zarpellon (Polytechnique Montréal) and Laurent Charlin (HEC Montréal) This tutorial will provide an overview of the recent impact machine learning is having on combinatorial optimization, particularly under the Mixed Integer Programming (MIP) framework. Topics covered will include ML and reinforcement learning for predicting feasible solutions, improving exact solvers with ML, a software framework for learning in exact MIP solvers, and the emerging paradigm of decision-focused learning. The tutorial targets both junior and senior researchers in two prominent areas of interest to the AAAI community: (1) Machine learning researchers looking for a challenging application domain, namely combinatorial optimization; (2) Optimization practitioners and researchers who may benefit from learning about recent advances in ML methods for improving combinatorial optimization algorithms. Basic prerequisites of the tutorial include: (1) Combinatorial optimization: basic understanding of optimization modeling, algorithm design, computational complexity. (2) Machine learning: basic knowledge of paradigms such as supervised and reinforcement learning; common techniques such as neural networks. Author bios: Elias B. Khalil is an Assistant Professor of Industrial Engineering at the University of Toronto since July 2020. Prior to that, he was the IVADO Postdoctoral Scholar at Polytechnique Montréal. Elias obtained his Ph.D. from the College of Computing at Georgia Tech, where he was an IBM Ph.D. Fellow (2016). As Canada Excellence Research Chair in Data Science for Real-Time Decision-Making at Polytechnique Montréal, Dr. Andrea Lodi holds Canada’s main chair in operations research. He has been Herman Goldstine Fellow at IBM in 2005–2006. He is author of more than 80 publications in the top journals of Mathematical Optimization. Bistra Dilkina is a co-Director of the Center for AI in Society (CAIS) at the University of Southern California (USC), and an Associate Professor of Computer Science at the Viterbi School of Engineering. Her work spans discrete optimization, network design, and machine learning with a strong focus on sustainability applications. Didier Chételat is a machine learning researcher at the Canada Excellence Research Chair in Data Science for Real Time Decision Making, under the leadership of Andrea Lodi. He obtained his Ph.D. in Statistics at Cornell University in 2015. His main research interests center around deep learning for combinatorial optimization. Maxime Gasse is a machine learning researcher within the Canada Excellence Research Chair in Data Science for Real-Time Decision-Making at Polytechnique Montréal, and also part of the MILA research institute on artificial intelligence. His research interests include probabilistic graphical models, structured prediction problems, questions regarding causality, and combinatorial optimization problems. Antoine Prouvost is a Ph.D. candidate in Polytechnique Montréal under supervision of Prof. Andrea Lodi at CERC DS4DM and Prof. Yoshua Bengio at Mila. I work at the interplay of deep learning and operations research, building combinatorial optimization algorithm that leverage machine learning to adapt to different problem structure. Giulia Zarpellon obtained her Ph.D. in Applied Mathematics at Polytechnique Montréal, under the supervision of Prof. Andrea Lodi, and a master’s degree in Mathematics at University of Padova. Her main research interests are in the integration of mathematical optimization and machine learning. Laurent Charlin is an assistant professor of artificial intelligence at HEC Montréal. He earned a master’s and PhD respectively from the universities of Waterloo and Toronto and was a postdoc at Columbia, Princeton and McGill. He develops machine learning models to analyze large collections of data and help in decision-making.

00:00 Part 1: Introduction to combinatorial optimization & tutorial overview 21:07 Part 2: The pure ML approach: predicting feasible solutions 52:34 Part 3: The hybrid approach: improving exact solvers with ML 1:25:20 Part 4: Machine learning for MIP solving: challenges & literature 2:02:55 Part 5: Ecole: A python framework for learning in exact MIP solvers 2:20:00 Part 6: Decision-focused Learning 2:49:20 Part 7: Concluding remarks