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(
47        &self,
48        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
49    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
50        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
51
52        Ok(target_solution[..self.num_original_arcs].to_vec())
53    }
54}
55
56#[reduction(
57    transform = exact {
58        num_vertices = "num_vertices",
59        num_arcs = "num_arcs + 1",
60    }
61)]
62impl ReduceTo<MinimumCostCirculation> for MinimumCostMaximumFlow {
63    type Result = ReductionMCMFToMCC;
64
65    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
66        let n = self.num_vertices();
67        let m = self.num_arcs();
68        let source = self.source();
69        let sink = self.sink();
70
71        // U = sum of capacities of arcs leaving the source.
72        let u_bound = self
73            .graph()
74            .arcs()
75            .iter()
76            .zip(self.capacities().iter())
77            .filter_map(|(&(u, _), &cap)| if u == source { Some(cap) } else { None })
78            .try_fold(0_i64, |total, capacity| total.checked_add(capacity))
79            .ok_or_else(|| {
80                crate::rules::ReductionError::integer_overflow::<
81                    MinimumCostMaximumFlow,
82                    MinimumCostCirculation,
83                >("summing capacities leaving the source")
84            })?;
85
86        // B = 1 + sum of all original arc costs. Strictly exceeds any
87        // simple s-t path cost, so the return arc's negative cost
88        // dominates all positive original costs lexicographically.
89        let cost_sum = self
90            .costs()
91            .iter()
92            .try_fold(0_i64, |total, &cost| total.checked_add(cost))
93            .ok_or_else(|| {
94                crate::rules::ReductionError::integer_overflow::<
95                    MinimumCostMaximumFlow,
96                    MinimumCostCirculation,
97                >("summing arc costs")
98            })?;
99        let b_const = cost_sum.checked_add(1).ok_or_else(|| {
100            crate::rules::ReductionError::integer_overflow::<
101                MinimumCostMaximumFlow,
102                MinimumCostCirculation,
103            >("adding one to the arc-cost sum")
104        })?;
105
106        // Keep every original arc and append the return arc (t, s).
107        let mut arcs = self.graph().arcs();
108        arcs.push((sink, source));
109
110        let mut capacities = self.capacities().to_vec();
111        capacities.push(u_bound);
112
113        let mut costs = self.costs().to_vec();
114        costs.push(b_const.checked_neg().ok_or_else(|| {
115            crate::rules::ReductionError::integer_overflow::<
116                MinimumCostMaximumFlow,
117                MinimumCostCirculation,
118            >("negating the return-arc cost")
119        })?);
120
121        let target = MinimumCostCirculation::new(DirectedGraph::new(n, arcs), capacities, costs);
122
123        Ok(ReductionMCMFToMCC {
124            target,
125            num_original_arcs: m,
126        })
127    }
128}
129
130#[cfg(feature = "example-db")]
131pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
132    use crate::export::SolutionPair;
133
134    vec![crate::example_db::specs::RuleExampleSpec {
135        id: "minimumcostmaximumflow_to_minimumcostcirculation",
136        build: || {
137            // Canonical 4-vertex diamond from issue #1029/#1031.
138            // Optimal source flow: [2, 1, 1, 1, 2] with value 3, cost 7.
139            // Target circulation appends return arc (3 -> 0) with
140            // flow value 3, giving config [2, 1, 1, 1, 2, 3].
141            let source = MinimumCostMaximumFlow::new(
142                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]),
143                0,
144                3,
145                vec![2, 1, 1, 1, 2],
146                vec![1, 0, 0, 1, 2],
147            );
148            crate::example_db::specs::rule_example_with_witness::<_, MinimumCostCirculation>(
149                source,
150                SolutionPair {
151                    source_config: serde_json::json!(vec![2, 1, 1, 1, 2]),
152                    target_config: serde_json::json!(vec![2, 1, 1, 1, 2, 3]),
153                },
154            )
155        },
156    }]
157}
158
159#[cfg(test)]
160#[path = "../unit_tests/rules/minimumcostmaximumflow_minimumcostcirculation.rs"]
161mod tests;
problemreductions/rules/minimumcostmaximumflow_minimumcostcirculation.rs

problemreductions/rules/
minimumcostmaximumflow_minimumcostcirculation.rs
