ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search
This work addresses computational efficiency for researchers and practitioners dealing with large, complex MIP instances, but it is incremental as it extends an existing method.
The paper tackles the challenge of accelerating Mixed-Integer Programming (MIP) solutions by parallelizing the Balans algorithm, resulting in ParBalans, which shows competitive performance against the state-of-the-art solver Gurobi on hard benchmarks.
Solving Mixed-Integer Programming (MIP) problems often requires substantial computational resources due to their combinatorial nature. Parallelization has emerged as a critical strategy to accelerate solution times and enhance scalability to tackle large, complex instances. This paper investigates the parallelization capabilities of Balans, a recently proposed multi-armed bandits-based adaptive large neighborhood search for MIPs. While Balans's modular architecture inherently supports parallel exploration of diverse parameter configurations, this potential has not been thoroughly examined. To address this gap, we introduce ParBalans, an extension that leverages both solver-level and algorithmic-level parallelism to improve performance on challenging MIP instances. Our experimental results demonstrate that ParBalans exhibits competitive performance compared to the state-of-the-art commercial solver Gurobi, particularly on hard optimization benchmarks.