Skip to main content

Crate eo_mcf

Crate eo_mcf 

Source
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) ≥ 0 on 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::deterministic the 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, and Problem::memory_estimate states the allocation up front. The DIMACS reader will not allocate on the strength of a header it has not yet read past — see dimacs::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.
ProblemBuilder
Incremental builder for a Problem.
Solution
An optimal flow, with the evidence to check it.
SolveStats
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.
SolverOptions
Knobs for a solve. Defaults are the measured-good settings; every field is a documented trade, not a magic number.

Enums§

ActiveNodeOrder
Order in which nodes with excess are selected for discharge.
BuildError
Building a Problem failed: the network description is not a well-formed min-cost-flow instance.
DimacsError
Reading a DIMACS min-cost-flow file failed.
SolveError
Solving failed.
SolveOrVerifyError
Failure of solve_certified.
VerifyError
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 u32 index 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 u32 index width.

Functions§

solve
Solve problem with default options.
solve_certified
Solve and certify in one step.
solve_with
Solve problem with explicit options.

Type Aliases§

Capacity
Arc capacity and residual capacity.
Cost
Arc cost, as supplied by the caller and as scaled internally.
Flow
Flow on an arc, and node excess.
Objective
Total cost of a flow. Widened: Σ cost × flow outgrows Cost routinely.
Price
Node price (solver) or potential (dual certificate).