ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search

• URL: http://arxiv.org/abs/2508.06736v1
• Date: Fri, 08 Aug 2025 22:30:19 GMT
• Title: ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search
• Authors: Alican Yilmaz, Junyang Cai, Serdar Kadioglu, Bistra Dilkina,
• Abstract summary: This paper investigates the parallelization capabilities of Balans, a proposed adaptive large neighborhood search for MIPs.<n>We introduce ParBalans, an extension that leverages both solver-level and algorithmic-level parallelism to improve performance on challenging MIP instances.<n>Our experimental results demonstrate that ParBalans exhibits competitive performance compared to the state-of-the-art commercial solver Gurobi.
• Score: 12.249099965011458
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Applying a Random-Key Optimizer on Mixed Integer Programs [0.36700088931938835]
  Mixed-Integer Programs (MIPs) are NP-hard optimization models that arise in a broad range of decision-making applications.<n>This paper explores the use of the Random-Key integer (RKO) framework as a flexible, metaheuristic alternative for computing high-quality solutions to MIPs.
  arXiv  Detail & Related papers  (2026-02-25T18:20:03Z)
• Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems [0.4636927061010061]
  We provide a vast experimental study of semidefinite programming relaxations of Quadratic unconstrained binary optimization problems.<n>We test on QUBO reformulations of industry-based instances of the (open) vehicle routing problem and the (affinity-based) slotting problem.
  arXiv  Detail & Related papers  (2025-03-13T18:51:45Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space.<n>We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• APB: Accelerating Distributed Long-Context Inference by Passing Compressed Context Blocks across GPUs [81.5049387116454]
  We introduce APB, an efficient long-context inference framework.<n>APB uses multi-host approximate attention to enhance prefill speed.<n>APB achieves speeds of up to 9.2x, 4.2x, and 1.6x compared with FlashAttn, RingAttn, and StarAttn, respectively.
  arXiv  Detail & Related papers  (2025-02-17T17:59:56Z)
• Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem [13.381261742433367]
  Mixed-integer programming (MIP) is a powerful paradigm for modeling and solving various important optimization problems.<n>We propose Balans, an adaptive meta-solver for MIPs with online learning capability that does not require any supervision or apriori training.<n>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.
  arXiv  Detail & Related papers  (2024-12-18T22:32:13Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
  We introduce two novel formulations of online learning problems rooted in the paradigm of Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB) We design algorithms that combine a sampling strategy with a classic approximation algorithm for correlation and study their theoretical guarantees. Our results are the first examples of clustering-time algorithms that work for the case of PE-CMAB in which the underlying offline optimization problem is NP-hard.
  arXiv  Detail & Related papers  (2024-02-02T13:31:24Z)
• A unified consensus-based parallel ADMM algorithm for high-dimensional regression with combined regularizations [3.280169909938912]
  parallel alternating multipliers (ADMM) is widely recognized for its effectiveness in handling large-scale distributed datasets. The proposed algorithms serve to demonstrate the reliability, stability, and scalability of a financial example.
  arXiv  Detail & Related papers  (2023-11-21T03:30:38Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  We introduce a novel GP regression to incorporate the subgroup feedback. Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches. We execute our algorithm on two disparate social problems.
  arXiv  Detail & Related papers  (2021-07-07T03:57:22Z)
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity [48.98199700043158]
  We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process. We prove an upper bound on the number of calls to the generative models needed for MDP-GapE to identify a near-optimal action with high probability.
  arXiv  Detail & Related papers  (2020-06-10T15:05:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.