Machine Learning for/with Mixed-Integer Optimization

Course Description

The course covers recent results on combining the strengths of Machine Learning (ML)/ Artificial Intelligence (AI) and Mixed-Integer Optimization (MIO) technologies. It discusses how MIO can be used to enhance AI methods in settings with scarce and unreliable data, in high-stakes situations where interpretability and fairness play fundamental roles, and when tackling engineering problems requiring human-AI collaborations.

The course also explores how AI can be used to improve solving MIO problems, using it to learn ML-based alternatives to key heuristic components of MIO solvers such as branching, understand the key structural properties of a given instance, learn effective configurations of MIO solvers and predict the performance of a given algorithm, thus improving decision-making throughout the solution process.

Learning Objectives

After completing this course, students will be able to:

1. Formulate and solve AI/ML problems using MIO technology.
2. Apply different ML techniques in the context of mixed-integer optimization.
3. Read and write a paper at the intersection of AI/ML and MIO.

Weekly Topics and Readings

Week 7.1: MIO for Robustness and Outliers

• Bertsimas et al. “Robust classification.” INFORMS Journal on Optimization (2019).
• Gómez, A. “Outlier detection in time series via mixed-integer conic quadratic optimization.” SIAM Journal on Optimization (2021).
• Insolia et al. “Simultaneous feature selection and outlier detection with optimality guarantees.” Biometrics (2022).

Week 7.2: MIO for Graphical Models

• Gómez et al. “Real time solution of quadratic optimization problems with banded matrices and indicator variables.” Operations Research (2025).
• Liu et al. “A graph-based decomposition method for convex quadratic optimization with indicators.” Mathematical Programming (2022).

Week 9: MIP Algorithm Configuration and Runtime Prediction

• Hutter et al. “ParamILS: an automatic algorithm configuration framework.” Journal of Artificial Intelligence Research (2009).
• Lawless et al. “LLMs for cold-start cutting plane separator configuration.” CPAIOR (2025).

Week 10: ML for MIP Branching

• Khalil et al. “Learning to branch in mixed integer programming.” AAAI (2016).
• Gasse et al. “Exact Combinatorial Optimization with Graph Convolutional Neural Networks.” NeurIPS (2019).
• Cai et al. “Learning backdoors for mixed integer programs with contrastive learning.” ECAI (2024).

Week 11: ML for MIP Meta-heuristics

• Sonnerat et al. “Learning a large neighborhood search algorithm for mixed integer programs.” arXiv (2021).
• Huang et al. “Searching large neighborhoods for integer linear programs with contrastive learning.” ICML (2023).
• Huang et al. “Contrastive predict-and-search for mixed integer linear programs.” ICML (2024).

Week 12: MIO for Artificial Neural Networks

• Anderson et al. “Strong mixed-integer programming formulations for trained neural networks.” Mathematical Programming (2020).
• Tjandraatmadja et al. “The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification.” NeurIPS (2020).

Week 13: ML for MIP Branch-and-Bound: Beyond Branching

• Khalil et al. “Learning to run heuristics in tree search.” IJCAI (2017).
• Paulus et al. “Learning to cut by looking ahead: Cutting plane selection via imitation learning.” ICML (2022).
• Labassi et al. “Learning to compare nodes in branch and bound with graph neural networks.” NeurIPS (2024).

Week 14: ML for Combinatorial Optimization

• Dai et al. “Learning combinatorial optimization algorithms over graphs.” NeurIPS (2017).
• Cappart et al. “Combinatorial Optimization and Reasoning with Graph Neural Networks.” JMLR (2023).
• Sun and Yang. “Difusco: Graph-based diffusion solvers for combinatorial optimization.” NeurIPS (2023).