Expand description
Minimum-cost flow, solved and certified.
eo-mcf solves the integral minimum-cost-flow problem with Goldberg’s
cost-scaling push-relabel algorithm, and ships an independent verify
subsystem that proves a given flow feasible and optimal without reference
to the solver.
use eo_mcf::{Problem, solve, verify};
// Move 4 units from node 0 to node 3. The direct arc is dearer than the
// two-hop route, but too narrow to carry everything.
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(), 3 * 2 + 1 * 6);
// The answer carries its own proof: feasible, and optimal by two
// independent arguments.
let certificate = verify::certify(&problem, solution.flows())?;
assert_eq!(certificate.objective, solution.objective());§Certification
Min-cost flow has a useful property: the optimal flow is generally not
unique, but the optimal cost always is, and optimality is checkable in
polynomial time — two correct solvers routinely return different flows at
the same cost. verify answers three questions:
- Feasible? Conservation, bounds, integrality.
- Optimal? Node potentials π with
c(u,v) − π(u) + π(v) ≥ 0on every residual arc — complementary slackness, a complete proof. - Optimal? No negative cycle in the residual graph, decided by the exact minimum cycle mean — a second proof sharing no code with the first.
The verifiers take (&Problem, &[Flow]) and nothing else, so the solver
cannot hand over its own prices and certify its own bug.
§Guarantees
- Exact. Integer arithmetic throughout; no floating point anywhere,
including in the rational cycle means. Overflow is a typed error
(
arith::Overflow), never a wrap and never a panic. - Deterministic. No randomness, no hash iteration, no threads. The same
input yields the same flow. With
SolverOptions::deterministicthe arc order is canonicalised first, so instances differing only in declaration order also yield the same flow, not merely the same cost. - Total.
#![forbid(unsafe_code)], no panicking paths in product code, no unbounded recursion, andProblem::memory_estimatestates the allocation up front. The DIMACS reader will not allocate on the strength of a header it has not yet read past — seedimacs::DEFAULT_READ_LIMIT. - Portable. Pure Rust, no C dependencies, no
fork(), no POSIX-only calls.
§References
Written from the published literature — Goldberg (1997), Goldberg & Tarjan
(1990, 1988), and the DIMACS format specification; no solver source was
consulted. docs/ALGORITHM.md holds the implementer’s notes and
validation/citations.toml the full bibliography.
Re-exports§
pub use verify::Certificate;pub use verify::certify;
Modules§
- dimacs
- DIMACS minimum-cost-flow format.
- oracle
- Independent reference implementations, for validation only.
- verify
- Optimality certification.
Structs§
- Arc
- One arc of the network, in the caller’s terms.
- Overflow
- An intermediate quantity did not fit its integer type.
- Problem
- A validated min-cost-flow instance.
- Problem
Builder - Incremental builder for a
Problem. - Solution
- An optimal flow, with the evidence to check it.
- Solve
Stats - What the solve did. Trend data for benchmarking; also the evidence that a heuristic changed the path to the optimum and not the optimum itself.
- Solver
Options - Knobs for a solve. Defaults are the measured-good settings; every field is a documented trade, not a magic number.
Enums§
- Active
Node Order - Order in which nodes with excess are selected for discharge.
- Build
Error - Building a
Problemfailed: the network description is not a well-formed min-cost-flow instance. - Dimacs
Error - Reading a DIMACS min-cost-flow file failed.
- Solve
Error - Solving failed.
- Solve
OrVerify Error - Failure of
solve_certified. - Verify
Error - A certificate could not be issued: the candidate solution is not feasible, not optimal, or not a solution to this problem at all.
Constants§
- MAX_
ARCS - Maximum number of arcs, set by the solver’s
u32index width. Each arc becomes a forward/reverse pair, so the residual arc index must also fit. - MAX_
NODES - Maximum number of nodes, set by the solver’s
u32index width.
Functions§
- solve
- Solve
problemwith default options. - solve_
certified - Solve and certify in one step.
- solve_
with - Solve
problemwith explicit options.