problemreductions/rules/
minimumedgecostflow_ilp.rs

1//! Reduction from MinimumEdgeCostFlow to `ILP<i64>`.
2//!
3//! Variables (2m total):
4//!   f_a  (a = 0..m-1)  — integer flow on arc a, domain {0, ..., c(a)}
5//!   y_a  (a = m..2m-1) — binary indicator: y_a = 1 iff f_a > 0
6//!
7//! Constraints:
8//!   f_a ≤ c(a)          — capacity (m constraints)
9//!   f_a ≤ c(a) · y_a    — linking: forces y_a = 1 when f_a > 0 (m constraints)
10//!   y_a ≤ 1             — binary bound on indicators (m constraints)
11//!   conservation at non-terminal vertices (|V|-2 equality constraints)
12//!   net flow into sink ≥ R (1 constraint)
13//!
14//! Total: 3m + |V| - 1 constraints (but we omit redundant capacity since
15//! linking already implies f_a ≤ c(a) when y_a ≤ 1).
16//! Actually we keep all for clarity: 2m + |V| - 1 constraints.
17//!
18//! Objective: minimize Σ p(a) · y_a.
19//! Extraction: first m variables are the flow values.
20
21use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
22use crate::models::graph::MinimumEdgeCostFlow;
23use crate::reduction;
24use crate::rules::traits::{ReduceTo, ReductionResult};
25
26/// Result of reducing MinimumEdgeCostFlow to `ILP<i64>`.
27///
28/// Variable layout:
29/// - `f_a` at index a for a in 0..num_edges (flow on arc a)
30/// - `y_a` at index num_edges + a for a in 0..num_edges (binary indicator)
31#[derive(Debug, Clone)]
32pub struct ReductionMECFToILP {
33    target: ILP<i64>,
34    num_edges: usize,
35}
36
37impl ReductionResult for ReductionMECFToILP {
38    type Source = MinimumEdgeCostFlow;
39    type Target = ILP<i64>;
40
41    fn target_problem(&self) -> &ILP<i64> {
42        &self.target
43    }
44
45    /// Extract flow solution: first m variables are the flow values.
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        crate::rules::ilp_helpers::decode_usize_values(&target_solution[..self.num_edges])
53    }
54}
55
56#[reduction(
57    transform = exact {
58        num_vars = "2 * num_edges",
59        num_constraints = "2 * num_edges + num_vertices - 1",
60    },
61    unavailable = {
62        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
63    }
64)]
65impl ReduceTo<ILP<i64>> for MinimumEdgeCostFlow {
66    type Result = ReductionMECFToILP;
67
68    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
69        let arcs = self.graph().arcs();
70        let m = arcs.len();
71        let n = self.num_vertices();
72        let num_vars = 2 * m;
73
74        let f = |a: usize| a; // flow variable index
75        let y = |a: usize| m + a; // indicator variable index
76
77        let mut constraints = Vec::new();
78
79        // 1. Linking: f_a - c(a) * y_a ≤ 0  (forces y_a = 1 when f_a > 0)
80        for a in 0..m {
81            constraints.push(LinearConstraint::le(
82                vec![(f(a), 1), (y(a), -self.capacities()[a])],
83                0,
84            ));
85        }
86
87        // 2. Binary bound: y_a ≤ 1
88        for a in 0..m {
89            constraints.push(LinearConstraint::le(vec![(y(a), 1)], 1));
90        }
91
92        // 3. Flow conservation at non-terminal vertices
93        for vertex in 0..n {
94            if vertex == self.source() || vertex == self.sink() {
95                continue;
96            }
97
98            let mut terms: Vec<(usize, i64)> = Vec::new();
99            for (a, &(u, v)) in arcs.iter().enumerate() {
100                if vertex == u {
101                    terms.push((f(a), -1)); // outgoing
102                } else if vertex == v {
103                    terms.push((f(a), 1)); // incoming
104                }
105            }
106
107            if !terms.is_empty() {
108                constraints.push(LinearConstraint::eq(terms, 0));
109            }
110        }
111
112        // 4. Flow requirement: net flow into sink ≥ R
113        let sink = self.sink();
114        let mut sink_terms: Vec<(usize, i64)> = Vec::new();
115        for (a, &(u, v)) in arcs.iter().enumerate() {
116            if v == sink {
117                sink_terms.push((f(a), 1));
118            } else if u == sink {
119                sink_terms.push((f(a), -1));
120            }
121        }
122        constraints.push(LinearConstraint::ge(sink_terms, self.required_flow()));
123
124        // Objective: minimize Σ p(a) · y_a
125        let objective: Vec<(usize, i64)> = (0..m).map(|a| (y(a), self.prices()[a])).collect();
126
127        Ok(ReductionMECFToILP {
128            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
129                .map_err(Self::target_construction)?,
130            num_edges: m,
131        })
132    }
133}
134
135#[cfg(feature = "example-db")]
136pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
137    use crate::topology::DirectedGraph;
138
139    vec![crate::example_db::specs::RuleExampleSpec {
140        id: "minimumedgecostflow_to_ilp",
141        build: || {
142            let source = MinimumEdgeCostFlow::new(
143                DirectedGraph::new(5, vec![(0, 1), (0, 2), (0, 3), (1, 4), (2, 4), (3, 4)]),
144                vec![3, 1, 2, 0, 0, 0],
145                vec![2, 2, 2, 2, 2, 2],
146                0,
147                4,
148                3,
149            );
150            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
151        },
152    }]
153}
154
155#[cfg(test)]
156#[path = "../unit_tests/rules/minimumedgecostflow_ilp.rs"]
157mod tests;
problemreductions/rules/minimumedgecostflow_ilp.rs

problemreductions/rules/
minimumedgecostflow_ilp.rs
