use crate::arith::{Cost, Flow, Price, add, neg, reduced_cost};
use crate::error::VerifyError;
use crate::problem::Problem;
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct DualCertificate {
pub potentials: Vec<Price>,
}
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)
}
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];
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")?);
}
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::*;
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() {
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() {
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
})
);
}
}