problemreductions/rules/
minimumedgecostflow_ilp.rs

1//! Reduction from MinimumEdgeCostFlow to `ILP<i64, i64, Bounded>`.
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) · y_a    — linking: forces y_a = 1 when f_a > 0 (m constraints)
9//!   y_a ≤ 1             — binary bound on indicators (m constraints)
10//!   conservation at non-isolated non-terminal vertices (at most |V|-2 rows)
11//!   net flow into sink ≥ R (1 constraint)
12//!
13//! Total: at most 2m + |V| - 1 constraints. Capacity is also a variable bound.
14//!
15//! Objective: minimize Σ p(a) · y_a.
16//! Extraction: first m variables are the flow values.
17
18use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
19use crate::models::graph::MinimumEdgeCostFlow;
20use crate::reduction;
21use crate::rules::traits::{ReduceTo, ReductionResult};
22
23/// Result of reducing MinimumEdgeCostFlow to `ILP<i64, i64, Bounded>`.
24///
25/// Variable layout:
26/// - `f_a` at index a for a in 0..num_edges (flow on arc a)
27/// - `y_a` at index num_edges + a for a in 0..num_edges (binary indicator)
28#[derive(Debug, Clone)]
29pub struct ReductionMECFToILP {
30    target: ILP<i64, i64, Bounded>,
31    num_edges: usize,
32}
33
34impl ReductionResult for ReductionMECFToILP {
35    type Source = MinimumEdgeCostFlow;
36    type Target = ILP<i64, i64, Bounded>;
37
38    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
39        &self.target
40    }
41
42    /// Extract flow solution: first m variables are the flow values.
43    fn extract_solution(
44        &self,
45        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
46    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
47        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
48
49        crate::rules::ilp_helpers::decode_usize_values(&target_solution[..self.num_edges])
50    }
51}
52
53// Linking and indicator rows contribute at most 3m nonzeros. Conservation
54// and the sink row together use each arc at most once per endpoint: at most 2m.
55#[reduction(transform = {
56    exact {
57        num_vars = "2 * num_edges",
58    },
59    upper_bound {
60        max_constraint_magnitude_bits = "max_capacity * (num_edges + 1) + 2",
61        num_constraints = "2 * num_edges + num_vertices - 1",
62        num_nonzeros = "5 * num_edges",
63    },
64})]
65impl ReduceTo<ILP<i64, i64, Bounded>> 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(
123            sink_terms,
124            crate::rules::ilp_helpers::bounded_flow_requirement(
125                self.required_flow(),
126                self.capacities().iter().copied(),
127            ),
128        ));
129
130        // Objective: minimize Σ p(a) · y_a
131        let objective: Vec<(usize, i64)> = (0..m).map(|a| (y(a), self.prices()[a])).collect();
132
133        let mut variables = self
134            .capacities()
135            .iter()
136            .map(|&capacity| IntegerVariable::new(Some(0), Some(capacity)))
137            .collect::<Result<Vec<_>, _>>()
138            .map_err(Self::target_construction)?;
139        variables.resize(num_vars, IntegerVariable::binary());
140
141        Ok(ReductionMECFToILP {
142            target: ILP::with_variables(
143                variables,
144                constraints,
145                objective,
146                ObjectiveSense::Minimize,
147            )
148            .map_err(Self::target_construction)?,
149            num_edges: m,
150        })
151    }
152}
153
154#[cfg(feature = "example-db")]
155pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
156    use crate::topology::DirectedGraph;
157
158    vec![crate::example_db::specs::RuleExampleSpec {
159        id: "minimumedgecostflow_to_ilp",
160        build: || {
161            let source = MinimumEdgeCostFlow::new(
162                DirectedGraph::new(5, vec![(0, 1), (0, 2), (0, 3), (1, 4), (2, 4), (3, 4)]),
163                vec![3, 1, 2, 0, 0, 0],
164                vec![2, 2, 2, 2, 2, 2],
165                0,
166                4,
167                3,
168            );
169            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
170        },
171    }]
172}
173
174#[cfg(test)]
175#[path = "../unit_tests/rules/minimumedgecostflow_ilp.rs"]
176mod tests;
problemreductions/rules/minimumedgecostflow_ilp.rs

problemreductions/rules/
minimumedgecostflow_ilp.rs
