Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

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

Created by
  • Haebom

Author

Junyang Cai, Serdar Kadioglu, Bistra Dilkina

Outline

In this paper, we propose Balans, an adaptive meta-solver for mixed-integer programming (MIP) with online learning capabilities without prior training. Balans is based on an adaptive large-neighborhood search running on top of a MIP solver, repeatedly applying destroy and repair neighborhood operators. The selection among various neighborhood definitions is made on an instance-by-instance basis, in real time, via a multi-armed bandit algorithm. Experimental results show that Balans outperforms basic MIP solvers, outperforms fixing on a single optimal neighborhood, and outperforms state-of-the-art large-neighborhood searches for MIP. Balans is highly configurable and is released as open-source software independent of the MIP solver.

Takeaways, Limitations

Takeaways:
Suggesting the possibility of accelerating the solution speed of MIP problems through online learning without prior training.
Effective application of multi-armed bandit algorithm for optimal selection among various neighborhood definitions.
It outperforms existing MIP solvers and large-scale neighborhood search techniques.
Providing increased accessibility and potential for research expansion through open source software releases.
Limitations:
Generalization performance for specific types of MIP problems may require further study.
Further research may be needed on parameter tuning of the multi-armed bandit algorithm.
Additional validation may be needed for scalability to large-scale problems.
👍