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
122
//! Optimality certification.
//!
//! **An optimal minimum-cost flow can be verified in polynomial time,
//! independently of how it was computed.** So correctness here is not an
//! argument that the solver is right in general: it is a proof that *this*
//! answer to *this* instance is optimal, checkable by code that has never
//! seen the solver.
//!
//! | Check | Claim | Method |
//! |---|---|---|
//! | [`certify_feasibility`] | the flow is feasible | conservation, bounds, integrality — `O(m)` |
//! | [`certify_dual_optimality`] | the flow is optimal | complementary slackness: potentials π with `c_π ≥ 0` on every residual arc |
//! | [`certify_no_negative_cycle`] | the flow is optimal | no negative cycle in the residual graph |
//!
//! # Two constraints
//!
//! **The certifiers never see the solver's prices.** Every entry point here
//! takes `(&Problem, &[Flow])` and nothing else. There is no argument through
//! which a solver could hand over its own price array, so a solver whose
//! prices are wrong cannot certify its own bug. The dual certificate recomputes
//! potentials from scratch, treating the flow as if it arrived from an
//! untrusted third party.
//!
//! **The two optimality proofs share no code path.** They are separate modules
//! using separate algorithms over separately-built representations of the
//! residual graph: the dual certificate relaxes shortest-path distances
//! (Bellman–Ford) and then checks every arc against them; the cycle check runs
//! Howard's policy iteration for the exact minimum cycle mean. The two claims
//! are mathematically equivalent, which is the point — if they ever disagree,
//! one of them is defective, and [`certify`] says so
//! ([`VerifyError::CertifiersDisagree`]) rather than trusting either.
//!
//! # Cost
//!
//! Certification is `O(n·m)`, materially more than a solve. It belongs in
//! tests, in `debug` builds and behind the `certify-on-solve` feature — not on
//! a hot production path.
pub use ;
pub use ;
pub use certify_feasibility;
use crate;
use crateVerifyError;
use crateProblem;
/// Proof that a flow is feasible and optimal.
/// Certify `flows` as a feasible, optimal solution of `problem`.
///
/// Runs the feasibility check, then both optimality proofs, then checks the
/// two proofs against each other.
///
/// # Errors
///
/// A [`VerifyError`] naming the counterexample: the arc outside its bounds,
/// the node where conservation fails, the residual arc with negative reduced
/// cost, or the negative cycle. [`VerifyError::CertifiersDisagree`] means the
/// two optimality proofs contradict each other and both are suspect.