problemreductions/rules/
minimumcostmaximumflow_minimumcostcirculation.rs

1//! Reduction from MinimumCostMaximumFlow to MinimumCostCirculation.
2//!
3//! Standard textbook equivalence: a minimum-cost maximum-flow instance
4//! `(G, s, t, c, cost)` can be solved as a minimum-cost circulation on
5//! the augmented graph `G' = G + (t -> s)` where the new return arc has
6//! capacity `U = sum_{e in delta^+(s)} u_e` and cost `-B` with
7//! `B = 1 + sum_{e in E} c_e`.
8//!
9//! Because `B` strictly exceeds the cost of any feasible `s-t` flow,
10//! the negative return arc forces the circulation to push the flow
11//! value `|f|` as large as possible (lex priority), and ties on the
12//! flow value are broken by minimizing the original arc cost — exactly
13//! the lexicographic objective of MinimumCostMaximumFlow.
14//!
15//! Reference: MIT 6.854 Course Staff, "Min-cost flow algorithms",
16//! <https://courses.csail.mit.edu/6.854/21/Scribe/s10-minCostFlowAlg/s10-minCostFlowAlg.html>.
17
18use crate::models::graph::{MinimumCostCirculation, MinimumCostMaximumFlow};
19use crate::reduction;
20use crate::rules::traits::{ReduceTo, ReductionResult};
21use crate::topology::DirectedGraph;
22
23/// Result of reducing MinimumCostMaximumFlow to MinimumCostCirculation.
24///
25/// The target circulation graph keeps every original arc in order and
26/// appends a single return arc `(t, s)` at the end. The original arc
27/// count `num_original_arcs` is the number of flow variables to recover
28/// when extracting a witness configuration.
29#[derive(Debug, Clone)]
30pub struct ReductionMCMFToMCC {
31    target: MinimumCostCirculation,
32    num_original_arcs: usize,
33}
34
35impl ReductionResult for ReductionMCMFToMCC {
36    type Source = MinimumCostMaximumFlow;
37    type Target = MinimumCostCirculation;
38
39    fn target_problem(&self) -> &MinimumCostCirculation {
40        &self.target
41    }
42
43    /// Extract the source flow by discarding the return arc: the first
44    /// `num_original_arcs` entries of the circulation are exactly the
45    /// flow values on the original arcs.
46    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
47        target_solution[..self.num_original_arcs].to_vec()
48    }
49}
50
51#[reduction(
52    overhead = {
53        num_vertices = "num_vertices",
54        num_arcs = "num_arcs + 1",
55    }
56)]
57impl ReduceTo<MinimumCostCirculation> for MinimumCostMaximumFlow {
58    type Result = ReductionMCMFToMCC;
59
60    fn reduce_to(&self) -> Self::Result {
61        let n = self.num_vertices();
62        let m = self.num_arcs();
63        let source = self.source();
64        let sink = self.sink();
65
66        // U = sum of capacities of arcs leaving the source.
67        let u_bound: i64 = self
68            .graph()
69            .arcs()
70            .iter()
71            .zip(self.capacities().iter())
72            .filter_map(|(&(u, _), &cap)| if u == source { Some(cap) } else { None })
73            .sum();
74
75        // B = 1 + sum of all original arc costs. Strictly exceeds any
76        // simple s-t path cost, so the return arc's negative cost
77        // dominates all positive original costs lexicographically.
78        let b_const: i64 = 1 + self.costs().iter().sum::<i64>();
79
80        // Keep every original arc and append the return arc (t, s).
81        let mut arcs = self.graph().arcs();
82        arcs.push((sink, source));
83
84        let mut capacities = self.capacities().to_vec();
85        capacities.push(u_bound);
86
87        let mut costs = self.costs().to_vec();
88        costs.push(-b_const);
89
90        let target = MinimumCostCirculation::new(DirectedGraph::new(n, arcs), capacities, costs);
91
92        ReductionMCMFToMCC {
93            target,
94            num_original_arcs: m,
95        }
96    }
97}
98
99#[cfg(feature = "example-db")]
100pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
101    use crate::export::SolutionPair;
102
103    vec![crate::example_db::specs::RuleExampleSpec {
104        id: "minimumcostmaximumflow_to_minimumcostcirculation",
105        build: || {
106            // Canonical 4-vertex diamond from issue #1029/#1031.
107            // Optimal source flow: [2, 1, 1, 1, 2] with value 3, cost 7.
108            // Target circulation appends return arc (3 -> 0) with
109            // flow value 3, giving config [2, 1, 1, 1, 2, 3].
110            let source = MinimumCostMaximumFlow::new(
111                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]),
112                0,
113                3,
114                vec![2, 1, 1, 1, 2],
115                vec![1, 0, 0, 1, 2],
116            );
117            crate::example_db::specs::rule_example_with_witness::<_, MinimumCostCirculation>(
118                source,
119                SolutionPair {
120                    source_config: vec![2, 1, 1, 1, 2],
121                    target_config: vec![2, 1, 1, 1, 2, 3],
122                },
123            )
124        },
125    }]
126}
127
128#[cfg(test)]
129#[path = "../unit_tests/rules/minimumcostmaximumflow_minimumcostcirculation.rs"]
130mod tests;
problemreductions/rules/minimumcostmaximumflow_minimumcostcirculation.rs

problemreductions/rules/
minimumcostmaximumflow_minimumcostcirculation.rs
