eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
  • Coverage
  • 100%
    175 out of 175 items documented1 out of 13 items with examples
  • Size
  • Source code size: 321.9 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 1.6 MB This is the summed size of all files generated by rustdoc for all configured targets
  • Ø build duration
  • this release: 8s Average build duration of successful builds.
  • all releases: 8s Average build duration of successful builds in releases after 2024-10-23.
  • Links
  • Kimedes-Artificial-Intelligence/eo-mcf
    0 0 0
  • crates.io
  • Dependencies
  • Versions
  • Owners
  • kimedes-AI

eo-mcf

A minimum-cost-flow solver in pure Rust: cost-scaling push-relabel (Goldberg 1997) with independent optimality certification.

License: Apache-2.0 OR MIT

  • Exact. Integer arithmetic throughout. Overflow is a typed error, never a wrap and never a panic.
  • Certified. verify::certify proves a flow feasible and optimal from (&Problem, &[Flow]) alone — it does not look at the solver's state, so it can check any flow, whatever produced it.
  • Deterministic. No randomness, floating point, hash iteration or threads. deterministic mode additionally canonicalises arc order, so permuted input declarations give the same flow.
  • Portable. #![forbid(unsafe_code)], a single dependency (thiserror), no C code. CI covers Linux x86_64/aarch64, macOS aarch64 and Windows x86_64.

Lower bounds, negative costs, parallel arcs and self-loops are all handled. Infeasible instances are reported as infeasible.

Usage

use eo_mcf::{Problem, solve, verify};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Ship 4 units from node 0 to node 3. The cheap route is narrow,
    // so one unit is forced onto the dear one.
    let problem = Problem::builder(4)
        .supply(0, 4)
        .supply(3, -4)
        .edge(0, 1, 3, 1)   // tail, head, capacity, cost
        .edge(1, 3, 3, 1)
        .edge(0, 2, 4, 3)
        .edge(2, 3, 4, 3)
        .build()?;

    let solution = solve(&problem)?;
    assert_eq!(solution.objective(), 12);

    // Prove it optimal, independently of the solver.
    let certificate = verify::certify(&problem, solution.flows())?;
    assert_eq!(certificate.objective, solution.objective());

    Ok(())
}

Certification runs three checks: feasibility (conservation, capacity bounds, integrality), the reduced-cost optimality conditions via recomputed node potentials, and absence of a negative residual cycle via the exact minimum cycle mean. The two optimality checks are independent code paths. To run the certifiers on every solve in a test suite:

cargo test --features certify-on-solve

Cargo features

The five heur-* features are the efficiency heuristics from Goldberg (1997); all are enabled by default, and none of them changes the optimal objective value — CI builds and tests every combination. certify-on-solve is off by default.

Feature Effect
heur-global-update set-relabel price update (Goldberg 1997 §3.1)
heur-bucket-update the update's queue as Dial buckets — O(m + n) per sweep (Goldberg 1995 §6/§9)
heur-push-lookahead don't push into a node that cannot pass it on (§3.4)
heur-arc-fixing retire arcs whose reduced cost exceeds 2nε; their flow never changes again (§3.3)
heur-price-refinement re-prove the current flow ε-optimal for the new ε and skip the phase (§3.2)
certify-on-solve run the certifiers after every solve; costs O(n·m)

DIMACS

eo_mcf::dimacs reads and writes the DIMACS minimum-cost-flow format. A small CLI wraps it:

cargo build --release --manifest-path validation/benchmark/runner/Cargo.toml

cat > example.min <<'EOF'
p min 4 4
n 1 4
n 4 -4
a 1 2 0 3 1
a 2 4 0 3 1
a 1 3 0 4 3
a 3 4 0 4 3
EOF

validation/benchmark/runner/target/release/eo-mcf-runner certify < example.min
# s 12

Arc lines are a tail head lower upper cost, node ids 1-based. Malformed input is rejected with a specific error rather than guessed at.

Modes: solve (objective only), ans (objective and flows), certify (solve, then certify), split (solve with a read/parse/solve time breakdown).

Algorithm and references

The implementation notes — notation, invariants, the refine loop, each heuristic and its correctness argument — are in docs/ALGORITHM.md. Inline [cite: KEY §x.y] markers in code and docs resolve to the bibliography in validation/citations.toml.

The main sources:

  • Goldberg, A. V. (1997), An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm, Journal of Algorithms 22(1):1–29
  • Goldberg, A. V. (1995), Scaling Algorithms for the Shortest Paths Problem, SIAM J. Comput. 24(3):494–504
  • Goldberg, A. V. & Tarjan, R. E. (1990), Finding Minimum-Cost Circulations by Successive Approximation, Math. Oper. Res. 15(3):430–466
  • Király, Z. & Kovács, P. (2012), Efficient Implementations of Minimum-Cost Flow Algorithms, arXiv:1207.6381
  • Ahuja, R. K., Magnanti, T. L. & Orlin, J. B. (1993), Network Flows: Theory, Algorithms, and Applications, Prentice Hall

The code was written from the published literature alone; no existing solver source was consulted.

Development

cargo test                               # full suite
cargo test --features certify-on-solve   # additionally certify every solve
cargo test --no-default-features         # heuristics off — same answers, slower
cargo clippy --all-targets --all-features
cargo run --release --example bench      # performance table

docs/TESTING.md describes the test suite and how to run the heavier benchmark and fuzzing tiers.

License

Dual-licensed under either of

at your option.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this crate by you, as defined in the Apache-2.0 license, shall be dual-licensed as above, without any additional terms or conditions.