Summary of Balans: Multi-armed Bandits-based Adaptive Large Neighborhood Search For Mixed-integer Programming Problem, by Junyang Cai et al.
Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem
by Junyang Cai, Serdar Kadioglu, Bistra Dilkina
First submitted to arxiv on: 18 Dec 2024
Categories
- Main: Artificial Intelligence (cs.AI)
- Secondary: Machine Learning (cs.LG); Optimization and Control (math.OC)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary A recent surge in learning-based approaches has shown promise in accelerating Mixed-Integer Programming (MIP) solving by offline training that guides critical design decisions during search. However, these methods rely heavily on offline training, which requires collecting datasets and computationally costly epochs, yet offers limited generalization to unseen instances. This paper proposes Balans, an adaptive meta-solver for MIPs with online learning capabilities that don’t require supervision or apriori training. Balans is built upon adaptive large-neighborhood search, operating on top of a MIP solver by applying destroy and repair neighborhood operators in succession. During the search, multi-armed bandit algorithms guide the selection among different neighborhood definitions for the instance at hand. Our experiments show that Balans outperforms the default MIP solver, is better than committing to any single best neighborhood, and improves upon state-of-the-art large-neighborhood search for MIPs. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary Balans is a new way to solve complex optimization problems. It uses a special type of problem-solving called Mixed-Integer Programming (MIP). Usually, computers need lots of training data to get good at solving these kinds of problems. But Balans doesn’t need any training! Instead, it figures out the best way to solve each problem as it goes along. This helps Balans solve the problems much faster than usual computer programs. Scientists tested Balans on many different types of optimization problems and found that it worked really well. They even made Balans available for other scientists to use. |
Keywords
» Artificial intelligence » Generalization » Online learning » Optimization
