1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//! 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};
//!
//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
//! // 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());
//! # Ok(())
//! # }
//! ```
//!
//! # 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.
pub use ;
pub use ;
pub use ;
pub use ;
pub use ;
/// Solve and certify in one step.
///
/// Equivalent to [`solve`] followed by [`verify::certify`]. Useful when the
/// caller wants the proof unconditionally rather than behind the
/// `certify-on-solve` feature; costs an extra `O(n·m)`.
///
/// # Errors
///
/// [`SolveOrVerifyError::Solve`] if no optimal flow could be produced,
/// [`SolveOrVerifyError::Verify`] if the flow produced fails certification —
/// which would be a defect in this crate, reported rather than hidden.
/// Failure of [`solve_certified`].