eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
//! Feasibility verifier.
//!
//! Flow conservation at every node, bounds on every arc, integrality by
//! construction. `O(m)`, no oracle, no potentials, no assumptions about where
//! the flow came from.
//!
//! Conservation sums are accumulated in `i128`. On a network where many
//! high-capacity arcs meet at one node the per-node sum can exceed the flow
//! type even though every individual flow is in range, and a verifier that
//! wrapped there would pass a flow that does not conserve.

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

/// Check that `flows` is a feasible flow for `problem`.
///
/// # Errors
///
/// [`VerifyError::LengthMismatch`] if the vector is not one entry per arc,
/// [`VerifyError::CapacityViolated`] for the first arc outside its bounds, or
/// [`VerifyError::ConservationViolated`] for the first node whose net outflow
/// does not equal its supply.
pub fn certify_feasibility(problem: &Problem, flows: &[Flow]) -> Result<(), VerifyError> {
    if flows.len() != problem.arc_count() {
        return Err(VerifyError::LengthMismatch {
            expected: problem.arc_count(),
            found: flows.len(),
        });
    }

    for (index, (arc, &flow)) in problem.arcs().iter().zip(flows).enumerate() {
        if flow < arc.lower || flow > arc.upper {
            return Err(VerifyError::CapacityViolated {
                arc: index,
                flow,
                lower: arc.lower,
                upper: arc.upper,
            });
        }
    }

    // Net outflow per node. A self-loop adds to both sides and cancels, which
    // is exactly its effect on conservation.
    let mut net = vec![0 as Objective; problem.node_count()];
    for (arc, &flow) in problem.arcs().iter().zip(flows) {
        let f = Objective::from(flow);
        net[arc.tail] = add_i128(net[arc.tail], f, "net outflow")?;
        net[arc.head] = add_i128(net[arc.head], -f, "net outflow")?;
    }

    for (node, (&balance, &supply)) in net.iter().zip(problem.supplies()).enumerate() {
        if balance != Objective::from(supply) {
            return Err(VerifyError::ConservationViolated {
                node,
                net: balance,
                supply,
            });
        }
    }

    Ok(())
}

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

    fn instance() -> Problem {
        Problem::builder(3)
            .supply(0, 4)
            .supply(2, -4)
            .edge(0, 1, 5, 1)
            .edge(1, 2, 5, 1)
            .build()
            .unwrap()
    }

    #[test]
    fn accepts_a_feasible_flow() {
        assert_eq!(certify_feasibility(&instance(), &[4, 4]), Ok(()));
    }

    #[test]
    fn rejects_a_wrong_length_vector() {
        assert_eq!(
            certify_feasibility(&instance(), &[4]),
            Err(VerifyError::LengthMismatch {
                expected: 2,
                found: 1
            })
        );
    }

    #[test]
    fn rejects_an_over_capacity_arc() {
        assert_eq!(
            certify_feasibility(&instance(), &[9, 9]),
            Err(VerifyError::CapacityViolated {
                arc: 0,
                flow: 9,
                lower: 0,
                upper: 5
            })
        );
    }

    #[test]
    fn rejects_a_negative_flow() {
        assert_eq!(
            certify_feasibility(&instance(), &[-1, 4]),
            Err(VerifyError::CapacityViolated {
                arc: 0,
                flow: -1,
                lower: 0,
                upper: 5
            })
        );
    }

    #[test]
    fn rejects_broken_conservation() {
        // 4 out of node 0 but only 3 arriving at node 2.
        assert_eq!(
            certify_feasibility(&instance(), &[4, 3]),
            Err(VerifyError::ConservationViolated {
                node: 1,
                net: -1,
                supply: 0
            })
        );
    }

    #[test]
    fn honours_lower_bounds() {
        let p = Problem::builder(2)
            .supply(0, 3)
            .supply(1, -3)
            .arc(0, 1, 3, 5, 1)
            .build()
            .unwrap();
        assert_eq!(certify_feasibility(&p, &[3]), Ok(()));
        assert_eq!(
            certify_feasibility(&p, &[2]),
            Err(VerifyError::CapacityViolated {
                arc: 0,
                flow: 2,
                lower: 3,
                upper: 5
            })
        );
    }

    #[test]
    fn self_loops_do_not_disturb_conservation() {
        let p = Problem::builder(2)
            .supply(0, 1)
            .supply(1, -1)
            .arc(0, 0, 0, 7, 2)
            .edge(0, 1, 1, 0)
            .build()
            .unwrap();
        assert_eq!(certify_feasibility(&p, &[5, 1]), Ok(()));
    }
}