almo-mcf

Almost-linear minimum-cost flow is the research goal for this project. The current implementation ships an exact min-cost flow solver with a Python + Rust interface. The Python API mirrors NetworkX conventions while the Rust core provides an integer min-cost flow solver with lower bounds and node demands.

The solver now uses an IPM-style potential reduction method by default on larger instances, with rounding to exact optimality. Small instances and IPM non-convergence fall back to the classic successive shortest path routine, so the output stays exact even when the dynamic oracle is conservative.

Features

• Exact min-cost flow for directed graphs with:
  • node demands (sum must be zero)
  • per-edge lower/upper capacities
  • integer edge costs
• IPM + rounding pipeline with min-ratio cycle updates
• Capacity and cost scaling for large (U/C) bounds
• NetworkX-compatible adapter (min_cost_flow, min_cost_flow_cost)
• Rust core with Python bindings via maturin
• Solver telemetry (iterations, gap, termination) when requested
• Deterministic, reproducible results with an opt-out randomized mode

Installation

pip install almo-mcf

The PyPI package ships a Rust extension module. If you are installing from source, you need a Rust toolchain (stable) and a C compiler.

Release prep: the almo-mcf name is available on PyPI (verified via a 404 on https://pypi.org/project/almo-mcf/).

From source (editable)

# from the repository root
python -m pip install -U maturin
maturin develop

Quickstart (NetworkX)

import networkx as nx
from almo_mcf import min_cost_flow, min_cost_flow_cost

G = nx.DiGraph()
G.add_node("s", demand=-3)
G.add_node("t", demand=3)
G.add_edge("s", "t", capacity=5, weight=2)

flow = min_cost_flow(G)
print(flow)
print("cost:", min_cost_flow_cost(G, flow))

Examples

See examples/almo_usage.py for a longer walkthrough and examples/networkx_quickstart.py for a concise NetworkX entrypoint example.

IPM tuning + stats

from almo_mcf import min_cost_flow

flow, stats = min_cost_flow(
    G,
    use_ipm=True,            # force IPM path (set False for classic SSP)
    use_scaling=None,        # auto-detect large U/C, set True/False to override
    deterministic=True,      # default; set False for randomized cycle selection
    strategy="periodic_rebuild",
    rebuild_every=25,
    max_iters=250,
    tolerance=1e-9,
    seed=42,
    threads=2,
    approx_factor=0.2,
    return_stats=True,
)
print(stats)

Almost-Linear Mode

The solver defaults to the almost-linear IPM path on larger instances. The use_ipm flag forces the solver path, while deterministic=True disables randomized sampling in the dynamic oracle to match the derandomized pipeline from Paper 2. When return_stats=True, the stats dictionary includes a solver_mode key so you can log whether the run used ipm, ipm_scaled, classic, or classic_fallback.

flow, stats = min_cost_flow(
    G,
    use_ipm=True,       # prefer IPM for large graphs
    deterministic=True, # reproducible shifting instead of random sampling
    return_stats=True,
)
print(stats["solver_mode"])

Scaling for large capacity/cost bounds

When inputs contain very large capacities or costs, the solver automatically enables capacity/cost scaling to keep the IPM rounds within polynomial bounds. You can override this behavior via use_scaling=True or use_scaling=False, or call the explicit helper min_cost_flow_scaled.

For numerically extreme instances (very small residual slacks or huge U/C bounds), the Python API exposes clamp controls such as numerical_clamp_log, residual_min, and barrier_clamp_max. These guard the barrier and gradient computations against overflow/underflow. When experimenting with research-grade settings, enable log_numerical_clamping=True to see how often the solver clamps values.

Deterministic vs. randomized solver behavior

Deterministic mode is enabled by default, which fixes the min-ratio cycle updates and dynamic sparsification choices for reproducibility. To experiment with the original randomized behavior (useful for performance comparisons), set deterministic=False on solver calls such as min_cost_flow or the extension reducers like min_cost_flow_convex and max_flow_via_min_cost_circulation.

When deterministic mode is enabled, the solver uses stable tie-breaking on edge and node IDs, deterministic sparsification, and lexicographically smallest path embeddings. You can optionally provide deterministic_seed to influence tie-breaking hashes for debugging; this does not enable random sampling. The stats dictionary returned with return_stats=True includes deterministic_mode_used and seed_used so you can log reproducibility metadata.

Extensions (convex costs, max-flow, isotonic regression)

import networkx as nx
from almo_mcf import min_cost_flow_convex, max_flow_via_min_cost_circulation

G = nx.MultiDiGraph()
G.add_node("s", demand=-2)
G.add_node("t", demand=2)
G.add_edge("s", "t", capacity=2, convex_cost=[0, 1, 6])
G.add_edge("s", "t", capacity=2, convex_cost=[0, 2, 4])
flow = min_cost_flow_convex(G)

H = nx.DiGraph()
H.add_edge("s", "t", capacity=5)
max_flow_value, max_flow = max_flow_via_min_cost_circulation(H, "s", "t")

Supported NetworkX attributes

• Graph type: nx.DiGraph and nx.MultiDiGraph
• Node attributes:
  • demand (int)
• Edge attributes:
  • capacity (required, finite)
  • lower_capacity (optional, default 0)
  • weight or cost (int; weight is preferred to match NetworkX)

The output format matches networkx.min_cost_flow: dict[u][v] = flow.

Lower-level array API (Rust core binding)

If you need to avoid NetworkX overhead, you can call the Rust extension directly:

import numpy as np
from almo_mcf import _core

flow = _core.min_cost_flow_edges(
    n,
    np.asarray(tails, dtype=np.int64),
    np.asarray(heads, dtype=np.int64),
    np.asarray(lower, dtype=np.int64),
    np.asarray(upper, dtype=np.int64),
    np.asarray(cost, dtype=np.int64),
    np.asarray(demand, dtype=np.int64),
)

# Force scaling in the core solver (useful for very large U/C bounds).
flow, stats = _core.min_cost_flow_edges_with_scaling(
    n,
    np.asarray(tails, dtype=np.int64),
    np.asarray(heads, dtype=np.int64),
    np.asarray(lower, dtype=np.int64),
    np.asarray(upper, dtype=np.int64),
    np.asarray(cost, dtype=np.int64),
    np.asarray(demand, dtype=np.int64),
)

Inputs must be integer arrays with consistent lengths.

Limitations (current)

• All capacities must be explicit and finite.
• Performance is currently tuned for correctness and clarity, not large-scale instances.

Repository layout

python/almo_mcf/        # Python API + NetworkX adapter
rust/crates/almo-mcf-core/   # Rust solver core
rust/crates/almo-mcf-py/     # PyO3 bindings
tests/                 # pytest suite (NetworkX parity + regressions)

Development

Run tests

pytest -q

Benchmarks

There are benchmark scripts that compare IPM vs the classic successive shortest-path (SSP) routine across sizes and capacity/cost ranges:

python tests/bench_ipm_vs_ssp.py --runs 3 --nodes 30 60 --edges 150 300 --capacity 10 50 --cost 5 20
python tests/bench_ipm_vs_networkx.py --nodes 60 --edges 300 --runs 3

Build the Rust core

cargo build -p almo-mcf-core

Roadmap highlights

• Integrate the IPM solver and min-ratio cycle oracle from DESIGN_SPEC.md.
• Add dynamic oracle updates and almost-linear data structures.
• Expand benchmarks and performance tuning.

References

The IPM + min-ratio cycle approach follows the ideas in:

• Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. arXiv:2203.00671, 2022. https://arxiv.org/abs/2203.00671
• Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. arXiv:2309.16629, 2023. https://arxiv.org/abs/2309.16629

License

Apache 2.0. See LICENSE for details.