use crate::arith::{Capacity, Cost, Flow, Objective, Overflow, Price, add, mul, reduced_cost, sub};
use crate::error::SolveError;
use crate::maxflow::FlowNetwork;
use crate::network::{Normalized, normalize};
use crate::problem::Problem;
#[cfg(feature = "heur-global-update")]
const UNREACHED: i64 = i64::MAX;
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
const BUCKET_NIL: u32 = u32::MAX;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum ActiveNodeOrder {
#[default]
Fifo,
Lifo,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub struct SolverOptions {
pub deterministic: bool,
pub scaling_factor: u32,
pub selection: ActiveNodeOrder,
pub max_operations: Option<u64>,
}
impl Default for SolverOptions {
fn default() -> Self {
Self {
deterministic: false,
scaling_factor: 32,
selection: ActiveNodeOrder::Fifo,
max_operations: None,
}
}
}
impl SolverOptions {
#[must_use]
pub fn with_deterministic(mut self, deterministic: bool) -> Self {
self.deterministic = deterministic;
self
}
#[must_use]
pub fn with_scaling_factor(mut self, scaling_factor: u32) -> Self {
self.scaling_factor = scaling_factor;
self
}
#[must_use]
pub fn with_selection(mut self, selection: ActiveNodeOrder) -> Self {
self.selection = selection;
self
}
#[must_use]
pub fn with_max_operations(mut self, max_operations: Option<u64>) -> Self {
self.max_operations = max_operations;
self
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub struct SolveStats {
pub scaling_phases: u32,
pub pushes: u64,
pub relabels: u64,
pub global_updates: u64,
pub lookahead_relabels: u64,
pub arcs_fixed: u64,
pub refinement_skips: u64,
pub update_truncations: u64,
pub early_exit: bool,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Solution {
flows: Vec<Flow>,
objective: Objective,
prices: Vec<Price>,
stats: SolveStats,
}
impl Solution {
#[must_use]
pub fn flows(&self) -> &[Flow] {
&self.flows
}
#[must_use]
pub fn objective(&self) -> Objective {
self.objective
}
#[must_use]
pub fn prices(&self) -> &[Price] {
&self.prices
}
#[must_use]
pub fn stats(&self) -> SolveStats {
self.stats
}
}
pub fn solve(problem: &Problem) -> Result<Solution, SolveError> {
solve_with(problem, &SolverOptions::default())
}
pub fn solve_with(problem: &Problem, options: &SolverOptions) -> Result<Solution, SolveError> {
if !options.deterministic {
return solve_inner(problem, options);
}
let (canonical, perm) = problem.canonical();
let solved = solve_inner(&canonical, options)?;
let mut flows = vec![0 as Flow; problem.arc_count()];
for (canonical_index, &original_index) in perm.iter().enumerate() {
flows[original_index] = solved.flows[canonical_index];
}
Ok(Solution { flows, ..solved })
}
fn solve_inner(problem: &Problem, options: &SolverOptions) -> Result<Solution, SolveError> {
let normalized = normalize(problem)?;
check_feasible(&normalized)?;
let mut engine = Engine::new(normalized, options)?;
engine.run()?;
let normalized = engine.normalized;
let flows = normalized.reconstruct();
let objective = problem.objective(&flows)?;
#[cfg(feature = "certify-on-solve")]
if let Err(error) = crate::verify::certify(problem, &flows) {
return Err(SolveError::SelfCertificationFailed(error));
}
Ok(Solution {
flows,
objective,
prices: engine.price,
stats: engine.stats,
})
}
fn check_feasible(normalized: &Normalized) -> Result<(), SolveError> {
let node_count = normalized.res.node_count;
let source = node_count;
let sink = node_count + 1;
let mut edges: Vec<(u32, u32, Capacity)> = normalized.forward_arcs().collect();
let mut required: i128 = 0;
for (v, &excess) in normalized.excess.iter().enumerate() {
let node = u32::try_from(v).map_err(|_| SolveError::InvariantViolated {
what: "node index exceeds u32 after a successful build",
})?;
match excess.cmp(&0) {
std::cmp::Ordering::Greater => {
edges.push((source as u32, node, excess));
required += i128::from(excess);
}
std::cmp::Ordering::Less => {
let demand = excess
.checked_neg()
.ok_or_else(|| Overflow::new("node demand after lower-bound substitution"))?;
edges.push((node, sink as u32, demand));
}
std::cmp::Ordering::Equal => {}
}
}
let routable = FlowNetwork::new(node_count + 2, &edges).max_flow(source, sink);
if routable == required {
Ok(())
} else {
Err(SolveError::Infeasible { routable, required })
}
}
struct Engine {
normalized: Normalized,
price: Vec<Price>,
current: Vec<u32>,
queue: std::collections::VecDeque<u32>,
queued: Vec<bool>,
selection: ActiveNodeOrder,
alpha: Cost,
budget: Option<u64>,
operations: u64,
relabels_since_update: u64,
stats: SolveStats,
#[cfg(feature = "heur-global-update")]
update_dist: Vec<i64>,
#[cfg(feature = "heur-global-update")]
update_lifted: Vec<Price>,
#[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
update_heap: std::collections::BinaryHeap<std::cmp::Reverse<(i64, u32)>>,
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
bucket_head: Vec<u32>,
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
bucket_arena: Vec<(u32, u32)>,
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
bucket_ceiling: i64,
#[cfg(feature = "heur-price-refinement")]
refine_dist: Vec<i64>,
#[cfg(feature = "heur-price-refinement")]
refine_indegree: Vec<u32>,
#[cfg(feature = "heur-price-refinement")]
refine_queue: std::collections::VecDeque<u32>,
#[cfg(feature = "heur-price-refinement")]
refine_price: Vec<Price>,
}
impl Engine {
fn new(normalized: Normalized, options: &SolverOptions) -> Result<Self, SolveError> {
let node_count = normalized.res.node_count;
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
let bucket_count = node_count.saturating_mul(2).saturating_add(1);
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
let arena_bound = node_count.saturating_add(normalized.res.head.len());
Ok(Self {
price: vec![0 as Price; node_count],
current: vec![0; node_count],
queue: std::collections::VecDeque::with_capacity(node_count),
queued: vec![false; node_count],
selection: options.selection,
alpha: Cost::from(options.scaling_factor.max(2)),
budget: options.max_operations,
operations: 0,
relabels_since_update: 0,
stats: SolveStats::default(),
#[cfg(feature = "heur-global-update")]
update_dist: vec![0; node_count],
#[cfg(feature = "heur-global-update")]
update_lifted: Vec::with_capacity(node_count),
#[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
update_heap: std::collections::BinaryHeap::with_capacity(node_count),
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
bucket_head: vec![BUCKET_NIL; bucket_count],
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
bucket_arena: Vec::with_capacity(arena_bound),
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
bucket_ceiling: (bucket_count - 1) as i64,
#[cfg(feature = "heur-price-refinement")]
refine_dist: vec![0; node_count],
#[cfg(feature = "heur-price-refinement")]
refine_indegree: vec![0; node_count],
#[cfg(feature = "heur-price-refinement")]
refine_queue: std::collections::VecDeque::with_capacity(node_count),
#[cfg(feature = "heur-price-refinement")]
refine_price: Vec::with_capacity(node_count),
normalized,
})
}
fn run(&mut self) -> Result<(), SolveError> {
let node_count = self.normalized.res.node_count;
if node_count == 0 || self.normalized.res.head.is_empty() {
return Ok(());
}
let scale = Cost::try_from(node_count)
.ok()
.and_then(|n| n.checked_add(1))
.ok_or_else(|| Overflow::new("cost scale factor n + 1"))?;
let mut max_abs: Cost = 1;
for slot in &mut self.normalized.res.cost {
let scaled = mul(*slot, scale, "scaled arc cost")?;
*slot = scaled;
let magnitude = scaled
.checked_abs()
.ok_or_else(|| Overflow::new("magnitude of scaled arc cost"))?;
max_abs = max_abs.max(magnitude);
}
let mut eps = max_abs;
loop {
eps = if eps <= 1 {
1
} else {
(eps / self.alpha).max(1)
};
#[cfg(feature = "heur-price-refinement")]
let skipped = self.stats.scaling_phases > 0 && self.price_refine(eps)?;
#[cfg(not(feature = "heur-price-refinement"))]
let skipped = false;
if skipped {
self.stats.refinement_skips += 1;
} else if self.refine(eps)? {
self.stats.scaling_phases += 1;
self.stats.early_exit = true;
return Ok(());
}
self.stats.scaling_phases += 1;
#[cfg(feature = "heur-arc-fixing")]
if eps > 1 {
self.fix_at_boundary(eps)?;
}
if eps == 1 {
return Ok(());
}
}
}
#[cfg(feature = "heur-arc-fixing")]
fn fix_at_boundary(&mut self, eps: Cost) -> Result<(), SolveError> {
let node_count = self.normalized.res.node_count;
let Some(threshold) = Cost::try_from(node_count)
.ok()
.and_then(|n| n.checked_mul(2))
.and_then(|n2| n2.checked_mul(eps))
else {
return Ok(());
};
for u in 0..node_count {
let mut i = self.normalized.res.first_out[u] as usize;
while i < self.normalized.res.active_end[u] as usize {
let res = &self.normalized.res;
if res.cap[i] > 0 {
let v = res.head[i] as usize;
let Ok(rc) = reduced_cost(res.cost[i], self.price[u], self.price[v]) else {
return Ok(());
};
if rc > threshold {
self.normalized.res.fix_pair(i, u);
self.stats.arcs_fixed += 1;
continue;
}
}
i += 1;
}
}
self.charge_many(node_count as u64)
}
#[cfg(feature = "heur-price-refinement")]
fn price_refine(&mut self, eps: Cost) -> Result<bool, SolveError> {
const PASS_CAP: u32 = 8;
let node_count = self.normalized.res.node_count;
for _ in 0..PASS_CAP {
self.refine_indegree.clear();
self.refine_indegree.resize(node_count, 0);
for u in 0..node_count {
for a in self.normalized.res.out_arcs(u) {
if self.normalized.res.cap[a] <= 0 {
continue;
}
let v = self.normalized.res.head[a] as usize;
let Ok(rc) =
reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])
else {
return Ok(false);
};
if rc < 0 {
self.refine_indegree[v] += 1;
}
}
}
self.refine_queue.clear();
for v in 0..node_count {
if self.refine_indegree[v] == 0 {
self.refine_queue.push_back(v as u32);
}
}
self.refine_dist.clear();
self.refine_dist.resize(node_count, 0);
let mut processed = 0usize;
while let Some(u) = self.refine_queue.pop_front() {
let u = u as usize;
processed += 1;
let du = self.refine_dist[u];
for a in self.normalized.res.out_arcs(u) {
if self.normalized.res.cap[a] <= 0 {
continue;
}
let v = self.normalized.res.head[a] as usize;
let Ok(rc) =
reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])
else {
return Ok(false);
};
if rc >= 0 {
continue;
}
let step = rc.saturating_add(eps - 1).div_euclid(eps);
let candidate = du.saturating_add(step);
if candidate < self.refine_dist[v] {
self.refine_dist[v] = candidate;
}
self.refine_indegree[v] -= 1;
if self.refine_indegree[v] == 0 {
self.refine_queue.push_back(v as u32);
}
}
}
if processed < node_count {
self.charge_many(node_count as u64)?;
return Ok(false);
}
let mut candidate = std::mem::take(&mut self.refine_price);
candidate.clear();
let mut raised_any = false;
for (&d, &price) in self.refine_dist.iter().zip(&self.price) {
let Some(units) = d.checked_neg() else {
self.refine_price = candidate;
return Ok(false);
};
raised_any |= units > 0;
let Ok(lift) = mul(units, eps, "refinement price lift") else {
self.refine_price = candidate;
return Ok(false);
};
let Ok(price) = add(price, lift, "refined price") else {
self.refine_price = candidate;
return Ok(false);
};
candidate.push(price);
}
let mut certified = true;
'verify: for u in 0..node_count {
for a in self.normalized.res.out_arcs(u) {
if self.normalized.res.cap[a] <= 0 {
continue;
}
let v = self.normalized.res.head[a] as usize;
let Ok(rc) =
reduced_cost(self.normalized.res.cost[a], candidate[u], candidate[v])
else {
self.refine_price = candidate;
return Ok(false);
};
if rc < -eps {
certified = false;
break 'verify;
}
}
}
self.price.copy_from_slice(&candidate);
self.refine_price = candidate;
self.charge_many(node_count as u64)?;
if certified {
return Ok(true);
}
if !raised_any {
return Ok(false);
}
}
Ok(false)
}
fn refine(&mut self, eps: Cost) -> Result<bool, SolveError> {
let node_count = self.normalized.res.node_count;
let mut saturated_any = false;
for u in 0..node_count {
for a in self.normalized.res.out_arcs(u) {
if self.normalized.res.cap[a] <= 0 {
continue;
}
let v = self.normalized.res.head[a] as usize;
if reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])? < 0 {
let delta = self.normalized.res.cap[a];
self.normalized.excess[u] =
sub(self.normalized.excess[u], delta, "node excess")?;
self.normalized.excess[v] =
add(self.normalized.excess[v], delta, "node excess")?;
self.normalized.res.push(a, delta);
saturated_any = true;
}
}
}
if !saturated_any && !self.normalized.excess.iter().any(|&e| e > 0) {
return Ok(true);
}
self.current
.copy_from_slice(&self.normalized.res.first_out[..node_count]);
self.queue.clear();
self.queued.iter_mut().for_each(|q| *q = false);
for u in 0..node_count {
if self.normalized.excess[u] > 0 {
self.activate(u);
}
}
self.relabels_since_update = 0;
self.global_update(eps)?;
while let Some(u) = self.next_active() {
if self.normalized.excess[u] <= 0 {
continue;
}
self.discharge(u, eps)?;
if self.relabels_since_update >= node_count as u64 {
self.relabels_since_update = 0;
self.global_update(eps)?;
self.current
.copy_from_slice(&self.normalized.res.first_out[..node_count]);
}
}
Ok(false)
}
fn discharge(&mut self, u: usize, eps: Cost) -> Result<(), SolveError> {
let span_end = self.normalized.res.live_end(u);
while self.normalized.excess[u] > 0 {
while self.current[u] < span_end {
let a = self.current[u] as usize;
if self.normalized.res.cap[a] <= 0 {
self.current[u] += 1;
continue;
}
let v = self.normalized.res.head[a] as usize;
if reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])? >= 0 {
self.current[u] += 1;
continue;
}
if self.lookahead(v, eps)? {
continue;
}
let delta = self.normalized.excess[u].min(self.normalized.res.cap[a]);
let was_active = self.normalized.excess[v] > 0;
self.normalized.res.push(a, delta);
self.normalized.excess[u] -= delta;
self.normalized.excess[v] = add(self.normalized.excess[v], delta, "node excess")?;
self.stats.pushes += 1;
self.charge()?;
if !was_active && self.normalized.excess[v] > 0 {
self.activate(v);
}
if self.normalized.excess[u] == 0 {
return Ok(());
}
}
if !self.relabel(u, eps)? {
return Err(SolveError::InvariantViolated {
what: "active node has excess but no residual outgoing arc",
});
}
self.current[u] = self.normalized.res.first_out[u];
}
Ok(())
}
fn relabel(&mut self, u: usize, eps: Cost) -> Result<bool, SolveError> {
let mut best: Option<Cost> = None;
for a in self.normalized.res.out_arcs(u) {
if self.normalized.res.cap[a] <= 0 {
continue;
}
let v = self.normalized.res.head[a] as usize;
let candidate = add(
self.normalized.res.cost[a],
self.price[v],
"relabel candidate",
)?;
best = Some(best.map_or(candidate, |b: Cost| b.min(candidate)));
}
let Some(minimum) = best else {
return Ok(false);
};
let raised = add(minimum, eps, "relabelled price")?;
if raised <= self.price[u] {
return Err(SolveError::InvariantViolated {
what: "relabel did not raise the price of an unadmissible node",
});
}
self.price[u] = raised;
self.stats.relabels += 1;
self.relabels_since_update += 1;
self.charge()?;
Ok(true)
}
#[cfg(feature = "heur-push-lookahead")]
fn has_admissible(&mut self, v: usize) -> Result<bool, Overflow> {
let span_end = self.normalized.res.live_end(v);
while self.current[v] < span_end {
let a = self.current[v] as usize;
if self.normalized.res.cap[a] > 0 {
let w = self.normalized.res.head[a] as usize;
if reduced_cost(self.normalized.res.cost[a], self.price[v], self.price[w])? < 0 {
return Ok(true);
}
}
self.current[v] += 1;
}
Ok(false)
}
#[cfg(feature = "heur-push-lookahead")]
fn lookahead(&mut self, v: usize, eps: Cost) -> Result<bool, SolveError> {
if self.normalized.excess[v] != 0 || self.has_admissible(v)? {
return Ok(false);
}
if !self.relabel(v, eps)? {
return Ok(false);
}
self.current[v] = self.normalized.res.first_out[v];
self.stats.lookahead_relabels += 1;
Ok(true)
}
#[cfg(not(feature = "heur-push-lookahead"))]
#[allow(clippy::unnecessary_wraps)]
fn lookahead(&mut self, _v: usize, _eps: Cost) -> Result<bool, SolveError> {
Ok(false)
}
#[cfg(feature = "heur-global-update")]
fn global_update(&mut self, eps: Cost) -> Result<(), SolveError> {
let node_count = self.normalized.res.node_count;
self.update_dist.clear();
self.update_dist.resize(node_count, UNREACHED);
if !self.update_sweep(eps)? {
return Ok(());
}
let ceiling = self.sweep_ceiling();
let fallback = self
.update_dist
.iter()
.copied()
.filter(|&d| d != UNREACHED)
.map(|d| d.min(ceiling))
.max()
.unwrap_or(0);
let mut lifted = std::mem::take(&mut self.update_lifted);
lifted.clear();
for (&distance, &price) in self.update_dist.iter().zip(&self.price) {
let d = if distance == UNREACHED {
fallback
} else {
distance.min(ceiling)
};
let Ok(lift) = mul(d, eps, "global update price lift") else {
self.update_lifted = lifted;
return Ok(());
};
let Ok(price) = add(price, lift, "globally updated price") else {
self.update_lifted = lifted;
return Ok(());
};
lifted.push(price);
}
self.price.copy_from_slice(&lifted);
self.update_lifted = lifted;
self.stats.global_updates += 1;
self.charge_many(node_count as u64)?;
Ok(())
}
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
#[inline]
fn sweep_ceiling(&self) -> i64 {
self.bucket_ceiling
}
#[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
#[inline]
#[allow(clippy::unused_self)]
fn sweep_ceiling(&self) -> i64 {
i64::MAX
}
#[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
fn update_sweep(&mut self, eps: Cost) -> Result<bool, SolveError> {
use std::cmp::Reverse;
self.update_heap.clear();
for (v, &excess) in self.normalized.excess.iter().enumerate() {
if excess < 0 {
self.update_dist[v] = 0;
self.update_heap.push(Reverse((0, v as u32)));
}
}
if self.update_heap.is_empty() {
return Ok(false);
}
while let Some(Reverse((d, w))) = self.update_heap.pop() {
let w = w as usize;
if d > self.update_dist[w] {
continue;
}
for a in self.normalized.res.out_arcs(w) {
let Some((v, candidate)) = self.relax(a, w, d, eps)? else {
continue;
};
self.update_dist[v] = candidate;
self.update_heap.push(Reverse((candidate, v as u32)));
}
}
Ok(true)
}
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
fn update_sweep(&mut self, eps: Cost) -> Result<bool, SolveError> {
let ceiling = self.bucket_ceiling;
self.bucket_head.fill(BUCKET_NIL);
self.bucket_arena.clear();
let mut seeded = false;
for v in 0..self.normalized.res.node_count {
if self.normalized.excess[v] < 0 {
self.update_dist[v] = 0;
let pushed = self.bucket_push(0, v);
debug_assert!(pushed, "a deficit seed must always fit the arena");
seeded = true;
}
}
if !seeded {
return Ok(false);
}
let mut index: i64 = 0;
let mut highest: i64 = 0;
while index <= highest {
loop {
let entry = self.bucket_head[index as usize];
if entry == BUCKET_NIL {
break;
}
let (node, next) = self.bucket_arena[entry as usize];
self.bucket_head[index as usize] = next;
let w = node as usize;
if self.update_dist[w] != index {
continue;
}
for a in self.normalized.res.out_arcs(w) {
let Some((v, candidate)) = self.relax(a, w, index, eps)? else {
continue;
};
self.update_dist[v] = candidate;
if candidate <= ceiling && self.bucket_push(candidate as usize, v) {
highest = highest.max(candidate);
} else {
self.stats.update_truncations += 1;
}
}
}
index += 1;
}
Ok(true)
}
#[cfg(feature = "heur-global-update")]
#[inline]
fn relax(
&self,
a: usize,
w: usize,
d: i64,
eps: Cost,
) -> Result<Option<(usize, i64)>, SolveError> {
let incoming = self.normalized.res.rev[a] as usize;
if self.normalized.res.cap[incoming] <= 0 {
return Ok(None);
}
let v = self.normalized.res.head[a] as usize;
let rc = reduced_cost(
self.normalized.res.cost[incoming],
self.price[v],
self.price[w],
)?;
let length = rc.div_euclid(eps).saturating_add(1).max(0);
let candidate = d.saturating_add(length);
if candidate < self.update_dist[v] {
Ok(Some((v, candidate)))
} else {
Ok(None)
}
}
#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
#[inline]
fn bucket_push(&mut self, index: usize, node: usize) -> bool {
let Ok(entry) = u32::try_from(self.bucket_arena.len()) else {
return false;
};
if entry == BUCKET_NIL {
return false;
}
self.bucket_arena
.push((node as u32, self.bucket_head[index]));
self.bucket_head[index] = entry;
true
}
#[cfg(not(feature = "heur-global-update"))]
#[allow(clippy::unnecessary_wraps)]
fn global_update(&mut self, _eps: Cost) -> Result<(), SolveError> {
Ok(())
}
fn activate(&mut self, v: usize) {
if self.queued[v] {
return;
}
self.queued[v] = true;
match self.selection {
ActiveNodeOrder::Fifo => self.queue.push_back(v as u32),
ActiveNodeOrder::Lifo => self.queue.push_front(v as u32),
}
}
fn next_active(&mut self) -> Option<usize> {
let v = self.queue.pop_front()? as usize;
self.queued[v] = false;
Some(v)
}
fn charge(&mut self) -> Result<(), SolveError> {
self.charge_many(1)
}
fn charge_many(&mut self, units: u64) -> Result<(), SolveError> {
self.operations = self.operations.saturating_add(units);
match self.budget {
Some(budget) if self.operations > budget => Err(SolveError::OperationBudgetExhausted {
budget,
scaling_phases: self.stats.scaling_phases,
}),
_ => Ok(()),
}
}
}