# Online Learning for Scheduling MIP Heuristics

arXiv: https://arxiv.org/abs/2304.03755 · HTML: https://mlsanity.com/paper/2304.03755/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 4 Apr 2023.

## Builds on (most cited first, 12 of 12)

- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [ParamILS: An Automatic Algorithm Configuration Framework](https://mlsanity.com/paper/1401.3492/) (2014)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Learning to Select Cuts for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2105.13645/) (2021)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm](https://mlsanity.com/paper/2005.10026/) (2020)
- [Adaptive Cut Selection in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2202.10962/) (2022)
- [A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP](https://mlsanity.com/paper/2007.03948/) (2020)
- [Improving Primal Heuristics for Mixed Integer Programming Problems based on Problem Reduction: A Learning-based Approach](https://mlsanity.com/paper/2209.13217/) (2022)

## Built on by (most cited first, 6 of 6)

- [Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming](https://mlsanity.com/paper/2402.05501/) (2024)
- [Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search](https://mlsanity.com/paper/2312.16767/) (2023)
- [Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem](https://mlsanity.com/paper/2412.14382/) (2024)
- [Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic](https://mlsanity.com/paper/2408.02960/) (2024)
- [Influence branching for learning to solve mixed-integer programs online](https://mlsanity.com/paper/2510.04273/) (2025)
- [Reinforcement Learning Methods for Neighborhood Selection in Local Search](https://mlsanity.com/paper/2601.07948/) (2026)

## Abstract (arXiv)

Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic's behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving - two broad and complex classes of heuristics - as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4%.