Fast, flexible and scalable b-matching in hypergraphs.
A solver for b-matching problems in hypergraphs, combining graph reductions, integer linear programming, and local search into a flexible algorithm pipeline.
Experiment data is available on Zenodo. For reproducing paper results, see reproducibility/reproducibility.md.
# Clone & build
git clone https://github.com/HeiHGM/Bmatching.git
cd Bmatching
./compile.sh
# Try it right away on bundled examples
./build/app/bmatching_cli --graph examples/small.hgr --algorithms greedy --capacity 1
# Weighted hypergraph with reductions
./build/app/bmatching_cli --graph examples/weighted.hgr --algorithms reductions,greedy,unfold --capacity 2
# Compact output (weight, size, time only)
./build/app/bmatching_cli --graph examples/weighted.hgr --algorithms reductions,greedy,unfold --quietbrew install --HEAD HeiHGM/bmatching/bmatching
bmatching --graph examples/weighted.hgr --algorithms greedy --capacity 2 --quietPrerequisites: CMake >= 3.20, a C++17 compiler, and ncurses dev headers.
./compile.sh # Release build (default)
./compile.sh Debug # Debug buildOr manually:
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j$(nproc)All external dependencies (Abseil, Protobuf, GoogleTest, Easylogging++, wide-integer) are fetched automatically via CMake's FetchContent.
| Option | Default | Description |
|---|---|---|
BMATCHING_USE_GUROBI |
OFF | Enable Gurobi ILP solver (requires local install, set GUROBI_HOME) |
BMATCHING_USE_SCIP |
OFF | Enable SCIP solver |
BMATCHING_USE_BSUITOR |
OFF | Enable bSuitor algorithm (fetched via git) |
BMATCHING_USE_KARP_SIPSER |
OFF | Enable Karp-Sipser algorithm (fetched via git) |
BMATCHING_USE_HASHING |
OFF | Enable edge hashing for Weighted Domination reduction |
BMATCHING_USE_TCMALLOC |
OFF | Use tcmalloc from gperftools |
BMATCHING_ENABLE_LOGGING |
OFF | Enable easylogging++ log output |
BMATCHING_FREE_MEMORY_CHECK |
OFF | Enable free memory checking in runner |
BUILD_TESTING |
ON | Build unit tests |
Example with Gurobi and bSuitor enabled:
cmake -B build \
-DCMAKE_BUILD_TYPE=Release \
-DBMATCHING_USE_GUROBI=ON \
-DBMATCHING_USE_BSUITOR=ON
cmake --build build -j$(nproc)After building, the CLI is available at:
build/app/bmatching_cli
bmatching_cli --graph <file> --algorithms <algo1,algo2,...> [options]| Flag | Description |
|---|---|
--graph <path> |
Path to the hypergraph file |
--algorithms <list> |
Comma-separated algorithm pipeline (e.g. reductions,greedy,unfold) |
| Flag | Default | Description |
|---|---|---|
--capacity <int> |
1 | Node capacity (-1 = use node weights from file) |
--format <str> |
hgr |
Input format: hgr or graph |
--ordering_method <str> |
bmindegree_dynamic |
Greedy ordering method (see below) |
--timeout <float> |
60.0 | Solver timeout in seconds (ilp_exact, presolved_ilp, scip, local_improvement) |
--max_tries <int> |
1000 | Max iterations for ILS / local search |
--iters <int> |
10 | Local improvement iterations |
--distance <int> |
5 | Edges per local improvement neighborhood |
--backend <str> |
gurobi |
Solver backend for local_improvement: gurobi or scip |
--disable_hint |
false | Don't mark reductions solution as exact |
--max_runs <int> |
10 | Maximum reduction rounds |
--reps <int> |
1 | Number of reduction repetitions |
--inplace |
false | Use newer ILS interface internally |
| Flag | Default | Description |
|---|---|---|
--quiet |
false | Only print weight, size, exactness, and time |
--output <path> |
stdout | Write result to file |
--output_format <str> |
text |
Output format: text, json, or binary |
Algorithms are chained via --algorithms as a comma-separated pipeline. Each algorithm in the pipeline runs in sequence on the same hypergraph and matching state.
Greedily adds edges to a b-matching using a chosen ordering strategy.
Available --ordering_method values:
| Ordering Method | Description |
|---|---|
default_order |
Iterates over edges in index order, adds all possible edges |
bmaximize |
Uses a three-compartment data structure, greedily adds the first free edge |
bweight |
Sorts edges by weight, adds in descending order |
bratio_static |
Scales edge weight by vertex capacities, sorts descending |
bmult_static |
Scales edge by minimal vertex capacity, sorts descending |
bratio_dynamic |
Scales by residual capacity, recalculates after each addition |
bmindegree_dynamic |
Scales by residual capacity / vertex degree, recalculates dynamically |
bmindegree1_dynamic |
Uses product of 1/degree as ordering |
# Greedy with weight-based ordering
bmatching_cli --graph input.hgr --algorithms greedy --ordering_method bweight --capacity 3
# Greedy with dynamic scaling (default ordering)
bmatching_cli --graph input.hgr --algorithms greedy --capacity 5Reduces the graph size using b-matching reductions. Always pair with unfold afterwards to recover the full solution.
# Reductions + greedy on the remainder
bmatching_cli --graph input.hgr --algorithms reductions,greedy,unfold --capacity 5
# With extra reduction rounds
bmatching_cli --graph input.hgr --algorithms reductions,greedy,unfold \
--max_runs 20 --reps 3 --capacity 1Iterated local search: improves an existing solution by searching for beneficial edge swaps, then perturbs to escape local optima. Requires an a priori solution (run greedy first).
# Greedy + ILS refinement
bmatching_cli --graph input.hgr --algorithms greedy,ils --max_tries 5000 --capacity 1
# Full pipeline: reductions + greedy + ILS + unfold
bmatching_cli --graph input.hgr --algorithms reductions,greedy,ils,unfold \
--max_tries 10000 --capacity 3
# ILS in-place mode
bmatching_cli --graph input.hgr --algorithms greedy,ils \
--max_tries 5000 --inplace --capacity 1Exactly solves the b-matching using Gurobi ILP. Requires BMATCHING_USE_GUROBI=ON.
# Exact solve with 5-minute timeout
bmatching_cli --graph input.hgr --algorithms ilp_exact --timeout 300 --capacity 1
# Reductions first, then exact solve on the remainder
bmatching_cli --graph input.hgr --algorithms reductions,ilp_exact,unfold \
--timeout 300 --capacity 1Solves the reduced (presolved) graph exactly using Gurobi ILP. Designed to run after reductions. Requires BMATCHING_USE_GUROBI=ON.
bmatching_cli --graph input.hgr --algorithms reductions,presolved_ilp,unfold \
--timeout 300 --capacity 1Solves the reduced graph exactly using the SCIP solver. Requires BMATCHING_USE_SCIP=ON.
bmatching_cli --graph input.hgr --algorithms reductions,scip,unfold \
--timeout 120 --capacity 3Iteratively improves solution quality by solving small ILP subproblems around selected edges. Requires an a priori solution and either Gurobi or SCIP.
# Local improvement with Gurobi backend
bmatching_cli --graph input.hgr --algorithms reductions,greedy,local_improvement,unfold \
--backend gurobi --iters 20 --distance 10 --timeout 60 --max_tries 1000 --capacity 1
# Local improvement with SCIP backend
bmatching_cli --graph input.hgr --algorithms reductions,greedy,local_improvement,unfold \
--backend scip --iters 10 --distance 5 --timeout 30 --max_tries 500 --capacity 3For comparison, the runner can link external solvers. Enable at build time:
| Algorithm | Build Flag | Authors | Capacity |
|---|---|---|---|
| bSuitor | BMATCHING_USE_BSUITOR=ON |
Khan et al. | any |
| kss / ksmd | BMATCHING_USE_KARP_SIPSER=ON |
Dufosse et al. | 1 only |
bmatching_cli --graph input.hgr --algorithms greedy --capacity 2Prints the full result as text to stdout.
bmatching_cli --graph input.hgr --algorithms reductions,greedy,unfold --quietweight: 42
size: 15
exact: false
time_ms: 1.234
bmatching_cli --graph input.hgr --algorithms greedy --output_format json --output result.jsonbmatching_cli --graph input.hgr --algorithms greedy --output_format binary --output result.pbLogging is disabled by default. To enable: set BMATCHING_ENABLE_LOGGING=ON at cmake configure time.
When enabled, control verbosity at runtime:
bmatching_cli --graph input.hgr --algorithms greedy --undefok=v --v=8| Level | Functions |
|---|---|
| 8 | addToMatching, removeFromMatching |
Spack manages system dependencies on compute clusters:
git clone --depth=100 --branch=releases/v0.20 https://github.com/spack/spack.git
cd spack && . share/spack/setup-env.sh
cd /path/to/Bmatching
spack env activate .
spack install
spack loadThen build as usual.
If you use this software in your research, please cite:
Ernestine Großmann, Felix Joos, Henrik Reinstädtler, and Christian Schulz. Engineering Hypergraph b-Matching Algorithms. Journal of Graph Algorithms and Applications (JGAA), 30(1):1--24, 2026. DOI: 10.7155/jgaa.v30i1.3166
@article{GrossmannJRS26,
author = {Gro{\ss}mann, Ernestine and Joos, Felix and Reinst{\"a}dtler, Henrik and Schulz, Christian},
title = {Engineering Hypergraph $b$-Matching Algorithms},
journal = {Journal of Graph Algorithms and Applications},
volume = {30},
number = {1},
pages = {1--24},
year = {2026},
doi = {10.7155/jgaa.v30i1.3166}
}