Balans

A modular, extensible, solver-agnostic meta-solver for MIP

Balans is an online-learning meta-solver designed to tackle Mixed-Integer Programming problems (MIPs) through multi-armed bandit-based adaptive large neighborhood search strategy, ALNS(MIP).

The framework integrates several powerful components into a highly configurable, modular, extensible, solver-agnostic, open-source software:

MABWiser for contextual multi-armed bandits
ALNS for adaptive large neighborhood search
SCIP and Gurobi for solving mixed-integer linear programming problems

More broadly, Balans is an integration technology at the intersection of adaptive search, meta-heuristics, multi-armed bandits, and mixed integer programming. When configured with a single neighborhood, it generalizes and subsumes prior work on Large Neighborhood Search for MIP, LNS(MIP).

How It Works

Balans iteratively improves solutions through a bandit-guided destroy-and-repair loop

Step 1

📖

Read MIP

Load a MIP instance (.mps/.lp) via the built-in solver reader

Step 2

🎯

Initial Solution

Find a feasible starting solution with the MIP solver

Step 3

🎰

Bandit Selection

Multi-armed bandit selects destroy & repair operators

Step 4

🔄

ALNS Loop

Iteratively improve via adaptive neighborhood search

Quick Start

Get started with Balans in just a few lines of Python

Install

pip install balans

Python

# Balans meta-solver for solving mixed-integer programming problems
from balans.solver import Balans

# Balans with default configuration
balans = Balans()

# Solve
result = balans.solve("mip_instance.mps")

# Results
print("Best solution:", result.best_state.solution())
print("Best solution objective:", result.best_state.objective())

Custom Configuration

# Supply a custom JSON configuration file
from balans.solver import Balans
balans = Balans(config="/path/to/config.json")

Command Line

# Run directly from the command line after pip install
balans mip_instance.mps
balans mip_instance.mps config.json

ParBalans

Parallel multi-armed bandits-based adaptive large neighborhood search

Parallelization

ParBalans

ParBalans extends the Balans framework with parallelization strategies at both the outer configuration level (n_jobs) and the inner branch-and-bound level (n_mip_jobs) to exploit modern multicore architectures. It runs multiple Balans configurations in parallel and returns the best found solution across all processes.

Alican Yılmaz, Junyang Cai, Serdar Kadıoğlu, Bistra Dilkina · arXiv 2025

arXiv'25 Code

@misc{parbalans,
  title         = {ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search},
  author        = {Alican Yilmaz and Junyang Cai and Serdar Kadıoğlu and Bistra Dilkina},
  year          = {2025},
  eprint        = {2508.06736},
  archivePrefix = {arXiv},
  primaryClass  = {cs.AI},
  url           = {https://arxiv.org/abs/2508.06736}
}

ParBalans — Python

# Parallel version of Balans, that runs several configurations in parallel
from balans.solver import ParBalans

if __name__ == '__main__':

    # ParBalans to run different Balans configs in parallel and save results
    parbalans = ParBalans(n_jobs=2,           # Outer-level: parallel Balans configurations
                          n_mip_jobs=1,       # Inner-level: parallel BnB search (Gurobi only)
                          mip_solver="scip",
                          output_dir="parbalans_results/",
                          balans_generator=ParBalans.TOP_CONFIGS)

    # Run a mip instance to retrieve several results
    instance_path = "mip_instance.mps"
    best_solution, best_objective = parbalans.run(instance_path)

    # Results of the best found solution and the objective
    print("Best solution:", best_solution)
    print("Best solution objective:", best_objective)

Citation

@inproceedings{balans,
  title     = {Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problems},
  author    = {Cai, Junyang and Kadıoğlu, Serdar and Dilkina, Bistra},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {2566--2574},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/286},
  url       = {https://doi.org/10.24963/ijcai.2025/286},
}

@misc{parbalans,
  title         = {ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search},
  author        = {Alican Yilmaz and Junyang Cai and Serdar Kadıoğlu and Bistra Dilkina},
  year          = {2025},
  eprint        = {2508.06736},
  archivePrefix = {arXiv},
  primaryClass  = {cs.AI},
  url           = {https://arxiv.org/abs/2508.06736},
}