Lectures

You can download the lecture slides and watch the recordings here. We will try to upload lectures prior to their corresponding classes. Suggested Readings may include books or publications that are available via the University of Toronto Libraries. External users should seek these resources out at libraries they have access to whenever possible.

• 

  Course Overview
  tl;dr: A brief summary of the main topics we will study and the syllabus.
  [slides] [video]
  
• 

  Introduction to Integer Programming
  tl;dr: Integer Programming modeling and algorithms.
  [slides] [video]
  

  Suggested Readings:

  • Chapters 1, 2, 7, 13, 14 of Integer Programming by Wolsey
• 

  Empirical Algorithmics
  tl;dr: Algorithms for hard problems and how to analyze their performance.
  [slides] [video]
  

  Suggested Readings:

  • Chapters 1, 4 of Stochastic Local Search by Hoos and Stützle
• 

  Algorithm Configuration
  tl;dr: How to find good parameter configurations for algorithms.
  [slides] [video]
  

  Suggested Readings:

  • Largely based on Hoos, Holger H. “Automated algorithm configuration and parameter tuning.” Autonomous search. Springer, Berlin, Heidelberg, 2011. 37-71.
• 

  Learning in Exact Solvers
  tl;dr: Approaches for using ML in Exact (MIP) Solvers.
  [slides] [video]
  
• 

  Project talk + Learning to Branch
  tl;dr: Discussion of project ideas + learning to branch in MIP
  [slides] [video]
  

  Suggested Readings:

  • Khalil, Elias, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. “Learning to branch in mixed integer programming.” In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 30, no. 1. 2016.
  • Lodi, Andrea, and Giulia Zarpellon. “On learning and branching: a survey.” Top 25, no. 2 (2017): 207-236.
• 

  Reinforcement Learning for Algorithms
  tl;dr: Discrete optimization algorithms as iterative procedures that can be optimized with reinforcement learning
  [slides] [video]
  

  Suggested Readings:

  • Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L. (2017). Learning Combinatorial Optimization Algorithms over Graphs. Advances in Neural Information Processing Systems, 30, 6348-6358.
  • Mazyavkina, Nina, et al. “Reinforcement learning for combinatorial optimization: A survey.” Computers & Operations Research (2021): 105400.
• 

  Graph Neural Networks
  tl;dr: Representing graphs with GNNs and applications in optimization
  [slides] [video]
  

  Suggested Readings:

  • Petar Veličković, Theoretical Foundations of Graph Neural Networks
  • Cappart, Quentin, et al. “Combinatorial optimization and reasoning with graph neural networks.” arXiv preprint arXiv:2102.09544 (2021)
• 

  Learning Theory
  tl;dr: Intro to learning theory and applications to data-driven algorithm design
  [slides] [video]
  

  Suggested Readings:

  • Vivek Srikumar course on Computational Learning Theory at University of Utah, particularly the slides on “Agnostic Learning” and “Shattering and the VC dimension”
  • Balcan, Maria-Florina. “Data-driven algorithm design.” arXiv preprint arXiv:2011.07177 (2020).
• 

  Other settings where learning aids optimization
  tl;dr:
  [slides] [video]
  

  Suggested Readings:

  • Mao, Hongzi, et al. “Learning scheduling algorithms for data processing clusters.” Proceedings of the ACM Special Interest Group on Data Communication. 2019. 270-288.
  • Vaezipoor, Pashootan, et al. “Learning Branching Heuristics for Propositional Model Counting.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 14. 2021.