eo-mcf
A minimum-cost-flow solver in pure Rust: cost-scaling push-relabel (Goldberg 1997) with independent optimality certification.
- Exact. Integer arithmetic throughout. Overflow is a typed error, never a wrap and never a panic.
- Certified.
verify::certifyproves 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.
deterministicmode 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 ;
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 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:
# 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
docs/TESTING.md describes the test suite and how to run
the heavier benchmark and fuzzing tiers.
License
Dual-licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE)
- MIT license (LICENSE-MIT)
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.