eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
//! 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.

mod cycle;
mod dual;
mod feasibility;

pub use cycle::{CycleCertificate, certify_no_negative_cycle};
pub use dual::{DualCertificate, certify_dual_optimality};
pub use feasibility::certify_feasibility;

use crate::arith::{Flow, Objective};
use crate::error::VerifyError;
use crate::problem::Problem;

/// Proof that a flow is feasible and optimal.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct Certificate {
    /// Node potentials witnessing complementary slackness. Recomputed here;
    /// unrelated to any price array the solver may hold.
    pub potentials: Vec<crate::arith::Price>,
    /// Exact minimum cycle mean of the residual graph as `(numerator,
    /// denominator)` with a positive denominator, or `None` when the residual
    /// graph is acyclic. Non-negative for an optimal flow.
    pub minimum_cycle_mean: Option<(i128, i128)>,
    /// Cost of the certified flow.
    pub objective: Objective,
}

/// 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.
pub fn certify(problem: &Problem, flows: &[Flow]) -> Result<Certificate, VerifyError> {
    certify_feasibility(problem, flows)?;

    let dual = certify_dual_optimality(problem, flows);
    let cycle = certify_no_negative_cycle(problem, flows);

    // Separate "this flow is not optimal" (a verdict) from "verification could
    // not be carried out" (a failure). Only verdicts are cross-checked.
    let dual_says_optimal = match &dual {
        Ok(_) => true,
        Err(VerifyError::NegativeReducedCost { .. } | VerifyError::PotentialsDoNotExist { .. }) => {
            false
        }
        Err(other) => return Err(other.clone()),
    };
    let cycle_says_optimal = match &cycle {
        Ok(_) => true,
        Err(VerifyError::NegativeCycle { .. }) => false,
        Err(other) => return Err(other.clone()),
    };

    if dual_says_optimal != cycle_says_optimal {
        return Err(VerifyError::CertifiersDisagree {
            dual_verdict: if dual_says_optimal {
                "optimal"
            } else {
                "not optimal"
            },
            cycle_verdict: if cycle_says_optimal {
                "optimal"
            } else {
                "not optimal"
            },
        });
    }

    // Agreed and negative: report the dual counterexample, which names an arc.
    let potentials = dual?.potentials;
    let minimum_cycle_mean = cycle?.minimum_mean;

    Ok(Certificate {
        potentials,
        minimum_cycle_mean,
        objective: problem.objective(flows)?,
    })
}