eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
//! Dual optimality certificate by complementary slackness.
//!
//! A flow `f` is optimal exactly when node potentials π exist with
//!
//! ```text
//! c_π(u,v) = c(u,v) − π(u) + π(v) ≥ 0   for every residual arc (u,v)
//! ```
//!
//! These are the **reduced cost optimality conditions**
//! [cite: AHUJA-MAGNANTI-ORLIN §9.3 Thm 9.3]. That is a complete mathematical
//! proof of optimality, not a comparison: around any residual cycle the π terms
//! telescope away, so non-negative reduced costs mean no residual cycle has
//! negative cost, and a flow with no negative residual cycle is optimal
//! [cite: AHUJA-MAGNANTI-ORLIN §9.3 Thm 9.1].
//!
//! ⚠ Not to be confused with what the same section calls the *complementary
//! slackness* optimality conditions (Thm 9.4). Those are an equivalent
//! statement on the **original** network, in terms of flow values — if
//! `c_π > 0` then `x = 0`; if `0 < x < u` then `c_π = 0`; if `c_π < 0` then
//! `x = u`. This module checks Thm 9.3, on the residual network.
//!
//! # Independence
//!
//! π is recomputed here from the problem and the flow alone. The solver's own
//! prices are not an argument to this function and cannot be supplied — the
//! entry point takes `(&Problem, &[Flow])`. A solver that produced a wrong
//! flow *and* prices consistent with it would still be caught, because these
//! potentials are derived from the flow independently.
//!
//! # Method
//!
//! Potentials come from Bellman–Ford shortest distances on the residual graph,
//! started from a virtual source joined to every node at zero cost — hence
//! every `d(v)` starting at 0. With `π = −d`, the relaxation invariant
//! `d(v) ≤ d(u) + c(u,v)` is precisely `c_π(u,v) ≥ 0`.
//!
//! The distances are only a *witness*. The proof is the explicit pass over
//! every residual arc that follows, which would reject a wrong π whatever
//! produced it — so a defect in the relaxation cannot manufacture a
//! certificate, only fail to find one.
//!
//! `O(n·m)` worst case, with an early exit once a full pass changes nothing.

use crate::arith::{Cost, Flow, Price, add, neg, reduced_cost};
use crate::error::VerifyError;
use crate::problem::Problem;

/// Potentials witnessing that a flow is optimal.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct DualCertificate {
    /// π, one entry per node. Every residual arc satisfies `c_π ≥ 0`.
    pub potentials: Vec<Price>,
}

/// Residual arcs of `flows`, as `(tail, head, cost)`.
///
/// An arc below its capacity can take more flow forwards; an arc above its
/// lower bound can give flow back, at the negated cost. Self-loops are
/// included: a negative-cost self-loop that is not saturated is a one-arc
/// negative cycle, and a certifier that skipped it would miss that.
fn residual_arcs(problem: &Problem, flows: &[Flow]) -> Result<Vec<(u32, u32, Cost)>, VerifyError> {
    let mut arcs = Vec::with_capacity(problem.arc_count());
    for (arc, &flow) in problem.arcs().iter().zip(flows) {
        let tail = arc.tail as u32;
        let head = arc.head as u32;
        if flow < arc.upper {
            arcs.push((tail, head, arc.cost));
        }
        if flow > arc.lower {
            arcs.push((head, tail, neg(arc.cost, "reverse residual arc cost")?));
        }
    }
    Ok(arcs)
}

/// Certify optimality of `flows` by exhibiting node potentials.
///
/// Does **not** check feasibility — that is [`certify_feasibility`](super::certify_feasibility),
/// and [`certify`](super::certify) runs both.
///
/// # Errors
///
/// [`VerifyError::PotentialsDoNotExist`] when the residual graph has a
/// negative cycle, so no potential function exists;
/// [`VerifyError::NegativeReducedCost`] when a residual arc refutes the
/// candidate potentials; [`VerifyError::LengthMismatch`] for a mis-sized flow
/// vector.
pub fn certify_dual_optimality(
    problem: &Problem,
    flows: &[Flow],
) -> Result<DualCertificate, VerifyError> {
    if flows.len() != problem.arc_count() {
        return Err(VerifyError::LengthMismatch {
            expected: problem.arc_count(),
            found: flows.len(),
        });
    }

    let node_count = problem.node_count();
    let arcs = residual_arcs(problem, flows)?;
    let mut distance = vec![0 as Cost; node_count];

    // A shortest path out of the virtual source uses at most n − 1 real arcs,
    // so a relaxation still firing on pass n proves a negative cycle.
    for round in 0..=node_count {
        let mut relaxed: Option<usize> = None;
        for &(tail, head, cost) in &arcs {
            let (u, v) = (tail as usize, head as usize);
            let candidate = add(distance[u], cost, "residual shortest-path distance")?;
            if candidate < distance[v] {
                distance[v] = candidate;
                relaxed = Some(v);
            }
        }
        match relaxed {
            None => break,
            Some(node) if round == node_count => {
                return Err(VerifyError::PotentialsDoNotExist { node });
            }
            Some(_) => {}
        }
    }

    let mut potentials = Vec::with_capacity(node_count);
    for &d in &distance {
        potentials.push(neg(d, "node potential")?);
    }

    // The proof. Everything above merely proposed π.
    for &(tail, head, cost) in &arcs {
        let (u, v) = (tail as usize, head as usize);
        let rc = reduced_cost(cost, potentials[u], potentials[v])?;
        if rc < 0 {
            return Err(VerifyError::NegativeReducedCost {
                tail: u,
                head: v,
                reduced_cost: rc,
            });
        }
    }

    Ok(DualCertificate { potentials })
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Two parallel routes 0→1→3 (cost 2) and 0→2→3 (cost 4), one unit to move.
    fn diamond() -> Problem {
        Problem::builder(4)
            .supply(0, 1)
            .supply(3, -1)
            .edge(0, 1, 1, 1)
            .edge(1, 3, 1, 1)
            .edge(0, 2, 1, 2)
            .edge(2, 3, 1, 2)
            .build()
            .unwrap()
    }

    #[test]
    fn certifies_the_cheap_route() {
        let certificate = certify_dual_optimality(&diamond(), &[1, 1, 0, 0]).unwrap();
        assert_eq!(certificate.potentials.len(), 4);
    }

    #[test]
    fn refuses_the_expensive_route() {
        // Feasible, but 4 instead of 2. Sending the unit down the cheap route
        // and taking it back off the dear one is a residual cycle of cost −2,
        // so this flow is refuted either way the relaxation reaches it: no
        // potential function exists at all, and had one been proposed, some
        // residual arc would refute it. Both are complete refutations, and
        // which one surfaces depends only on arc order.
        let err = certify_dual_optimality(&diamond(), &[0, 0, 1, 1]).unwrap_err();
        assert!(
            matches!(
                err,
                VerifyError::PotentialsDoNotExist { .. } | VerifyError::NegativeReducedCost { .. }
            ),
            "expected a refutation, got {err:?}"
        );
    }

    #[test]
    fn potentials_actually_satisfy_the_inequality() {
        let problem = diamond();
        let flows = [1, 1, 0, 0];
        let certificate = certify_dual_optimality(&problem, &flows).unwrap();
        for &(tail, head, cost) in &residual_arcs(&problem, &flows).unwrap() {
            let (u, v) = (tail as usize, head as usize);
            let rc =
                reduced_cost(cost, certificate.potentials[u], certificate.potentials[v]).unwrap();
            assert!(rc >= 0, "residual arc {u}→{v} has reduced cost {rc}");
        }
    }

    #[test]
    fn detects_a_negative_residual_cycle() {
        // A two-arc cycle whose net cost is negative and which the given flow
        // leaves entirely un-exploited.
        let problem = Problem::builder(2)
            .edge(0, 1, 5, -3)
            .edge(1, 0, 5, 1)
            .build()
            .unwrap();
        let err = certify_dual_optimality(&problem, &[0, 0]).unwrap_err();
        assert!(
            matches!(
                err,
                VerifyError::PotentialsDoNotExist { .. } | VerifyError::NegativeReducedCost { .. }
            ),
            "expected refutation, got {err:?}"
        );
    }

    #[test]
    fn an_unsaturated_negative_self_loop_is_not_optimal() {
        let problem = Problem::builder(1).arc(0, 0, 0, 4, -1).build().unwrap();
        assert!(certify_dual_optimality(&problem, &[0]).is_err());
        assert!(certify_dual_optimality(&problem, &[4]).is_ok());
    }

    #[test]
    fn rejects_a_mis_sized_flow_vector() {
        assert_eq!(
            certify_dual_optimality(&diamond(), &[1, 1]),
            Err(VerifyError::LengthMismatch {
                expected: 4,
                found: 2
            })
        );
    }
}