# Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 47 references that are in the map.
- First posted on arXiv 18 Dec 2024.

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

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Algorithms for multi-armed bandit problems](https://mlsanity.com/paper/1402.6028/) (2014)
- [Learning to Schedule Heuristics in Branch-and-Bound](https://mlsanity.com/paper/2103.10294/) (2021)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [The SCIP Optimization Suite 9.0](https://mlsanity.com/paper/2402.17702/) (2024)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods](https://mlsanity.com/paper/2406.06954/) (2024)
- [Adapting Behaviour for Learning Progress](https://mlsanity.com/paper/1912.06910/) (2019)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search](https://mlsanity.com/paper/2312.16767/) (2023)
- [Online Learning for Scheduling MIP Heuristics](https://mlsanity.com/paper/2304.03755/) (2023)
- [Local Branching Relaxation Heuristics for Integer Linear Programs](https://mlsanity.com/paper/2212.08183/) (2022)
- [A General Large Neighborhood Search Framework for Solving Integer Linear Programs](https://mlsanity.com/paper/2004.00422/) (2020)

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

- [FORGE: Foundational Optimization Representations from Graph Embeddings](https://mlsanity.com/paper/2508.20330/) (2025)
- [ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search](https://mlsanity.com/paper/2508.06736/) (2025)
- [ID-PaS+ : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programs](https://mlsanity.com/paper/2512.10211/) (2025)
- [SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization](https://mlsanity.com/paper/2609.31179/) (2026)

## Abstract (arXiv)

Mixed-integer programming (MIP) is a powerful paradigm for modeling and solving various important combinatorial optimization problems. Recently, learning-based approaches have shown a potential to speed up MIP solving via offline training that then guides important design decisions during the search. However, a significant drawback of these methods is their heavy reliance on offline training, which requires collecting training datasets and computationally costly training epochs yet offering only limited generalization to unseen (larger) instances. In this paper, we propose Balans, an adaptive meta-solver for MIPs with online learning capability that does not require any supervision or apriori training. At its core, Balans is based on adaptive large-neighborhood search, operating on top of an MIP solver by successive applications of destroy and repair neighborhood operators. During the search, the selection among different neighborhood definitions is guided on the fly for the instance at hand via multi-armed bandit algorithms. Our extensive experiments on hard optimization instances show that Balans offers significant performance gains over the default MIP solver, is better than committing to any single best neighborhood, and improves over the state-of-the-art large-neighborhood search for MIPs. Finally, we release Balans as a highly configurable, MIP solver agnostic, open-source software.