problemreductions/rules/
undirectedflowlowerbounds_ilp.rs

1//! Reduction from UndirectedFlowLowerBounds to `ILP<i64>`.
2//!
3//! For each undirected edge e = {u,v} (indexed by e), we introduce:
4//!   f_{uv} = 2*e      (flow in u→v direction, ≥ 0)
5//!   f_{vu} = 2*e + 1  (flow in v→u direction, ≥ 0)
6//!   z_e    = 2*|E| + e (binary orientation: 1 if u→v, 0 if v→u)
7//!
8//! Constraints per edge (4 constraints):
9//!   z_e ≤ 1  (force binary)
10//!   f_{uv} ≤ cap[e] * z_e        (only if oriented u→v)
11//!   f_{vu} ≤ cap[e] * (1 - z_e)  (only if oriented v→u)
12//!   f_{uv} ≥ lower[e] * z_e      (must carry at least lower bound if oriented u→v)
13//!   f_{vu} ≥ lower[e] * (1 - z_e)(must carry at least lower bound if oriented v→u)
14//! Since we need all 4: linearized as:
15//!   z_e ≤ 1
16//!   f_{uv} - cap[e]*z_e ≤ 0
17//!   f_{vu} + cap[e]*z_e ≤ cap[e]
18//!   f_{uv} - lower[e]*z_e ≥ 0    (only lower bound if positive)
19//!   f_{vu} - lower[e]*(1-z_e) ≥ 0 => f_{vu} + lower[e]*z_e ≥ lower[e]
20//!
21//! Flow conservation at non-terminal vertices.
22//! Net flow into sink ≥ requirement.
23//!
24//! Size upper bound: 3*|E| variables, 4*|E| + |V| + 1 constraints (conservative for non-terminals).
25
26use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
27use crate::models::graph::UndirectedFlowLowerBounds;
28use crate::reduction;
29use crate::rules::traits::{ReduceTo, ReductionResult};
30use crate::topology::Graph;
31
32/// Result of reducing UndirectedFlowLowerBounds to `ILP<i64>`.
33///
34/// Variable layout:
35/// - `f_{uv}` at 2*e (flow u→v on edge e)
36/// - `f_{vu}` at 2*e + 1 (flow v→u on edge e)
37/// - `z_e` at 2*|E| + e (orientation indicator: 1 = u→v direction)
38#[derive(Debug, Clone)]
39pub struct ReductionUFLBToILP {
40    target: ILP<i64>,
41    num_edges: usize,
42}
43
44impl ReductionResult for ReductionUFLBToILP {
45    type Source = UndirectedFlowLowerBounds;
46    type Target = ILP<i64>;
47
48    fn target_problem(&self) -> &ILP<i64> {
49        &self.target
50    }
51
52    /// Extract edge orientation from ILP: z_e values at indices [2*|E|..3*|E|).
53    ///
54    /// The model encodes orientation as config[e] = 0 for u→v, 1 for v→u.
55    /// The ILP uses z_e = 1 for u→v, z_e = 0 for v→u.
56    /// So we return 1 - z_e to match the model's convention.
57    fn extract_solution(
58        &self,
59        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
60    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
61        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
62
63        Ok({
64            let e = self.num_edges;
65            target_solution[2 * e..3 * e]
66                .iter()
67                .map(|&z| z == 0)
68                .collect()
69        })
70    }
71}
72
73#[reduction(
74    transform = exact {
75        num_vars = "3 * num_edges",
76        num_constraints = "4 * num_edges + num_vertices + 1",
77    },
78    unavailable = {
79        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
80    }
81)]
82impl ReduceTo<ILP<i64>> for UndirectedFlowLowerBounds {
83    type Result = ReductionUFLBToILP;
84
85    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
86        let edges = self.graph().edges();
87        let e = edges.len();
88        let n = self.num_vertices();
89        let num_vars = 3 * e;
90        let f_uv = |edge: usize| 2 * edge;
91        let f_vu = |edge: usize| 2 * edge + 1;
92        let z = |edge: usize| 2 * e + edge;
93
94        let mut constraints = Vec::new();
95
96        for (edge_idx, _) in edges.iter().enumerate() {
97            let cap = self.capacities()[edge_idx];
98            let lower = self.lower_bounds()[edge_idx];
99
100            // z_e ≤ 1 (binary)
101            constraints.push(LinearConstraint::le(vec![(z(edge_idx), 1)], 1));
102
103            // f_{uv} ≤ cap * z_e  =>  f_{uv} - cap*z_e ≤ 0
104            constraints.push(LinearConstraint::le(
105                vec![(f_uv(edge_idx), 1), (z(edge_idx), -cap)],
106                0,
107            ));
108
109            // f_{vu} ≤ cap * (1 - z_e)  =>  f_{vu} + cap*z_e ≤ cap
110            constraints.push(LinearConstraint::le(
111                vec![(f_vu(edge_idx), 1), (z(edge_idx), cap)],
112                cap,
113            ));
114
115            if lower > 0 {
116                // f_{uv} ≥ lower * z_e  =>  f_{uv} - lower*z_e ≥ 0
117                constraints.push(LinearConstraint::ge(
118                    vec![(f_uv(edge_idx), 1), (z(edge_idx), -lower)],
119                    0,
120                ));
121
122                // f_{vu} ≥ lower * (1 - z_e)  =>  f_{vu} + lower*z_e ≥ lower
123                constraints.push(LinearConstraint::ge(
124                    vec![(f_vu(edge_idx), 1), (z(edge_idx), lower)],
125                    lower,
126                ));
127            }
128        }
129
130        // Flow conservation at non-terminal vertices
131        for vertex in 0..n {
132            if vertex == self.source() || vertex == self.sink() {
133                continue;
134            }
135
136            let mut terms: Vec<(usize, i64)> = Vec::new();
137            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
138                if vertex == u {
139                    // f_{uv} leaves vertex u, f_{vu} enters
140                    terms.push((f_uv(edge_idx), -1));
141                    terms.push((f_vu(edge_idx), 1));
142                } else if vertex == v {
143                    // f_{uv} enters vertex v, f_{vu} leaves
144                    terms.push((f_uv(edge_idx), 1));
145                    terms.push((f_vu(edge_idx), -1));
146                }
147            }
148
149            if !terms.is_empty() {
150                constraints.push(LinearConstraint::eq(terms, 0));
151            }
152        }
153
154        // Net flow into sink ≥ requirement
155        let sink = self.sink();
156        let mut sink_terms: Vec<(usize, i64)> = Vec::new();
157        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
158            if v == sink {
159                // f_{uv} flows into sink, f_{vu} flows out
160                sink_terms.push((f_uv(edge_idx), 1));
161                sink_terms.push((f_vu(edge_idx), -1));
162            } else if u == sink {
163                // f_{vu} flows into sink (from v side), f_{uv} flows out
164                sink_terms.push((f_uv(edge_idx), -1));
165                sink_terms.push((f_vu(edge_idx), 1));
166            }
167        }
168        constraints.push(LinearConstraint::ge(sink_terms, self.requirement()));
169
170        Ok(ReductionUFLBToILP {
171            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
172                .map_err(Self::target_construction)?,
173            num_edges: e,
174        })
175    }
176}
177
178#[cfg(feature = "example-db")]
179pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
180    use crate::topology::SimpleGraph;
181
182    vec![crate::example_db::specs::RuleExampleSpec {
183        id: "undirectedflowlowerbounds_to_ilp",
184        build: || {
185            // 3-vertex graph: edge (0,1) cap=2 lower=1, edge (1,2) cap=2 lower=1
186            // source=0, sink=2, requirement=1
187            let source = UndirectedFlowLowerBounds::new(
188                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
189                vec![2, 2],
190                vec![1, 1],
191                0,
192                2,
193                1,
194            );
195            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
196        },
197    }]
198}
199
200#[cfg(test)]
201#[path = "../unit_tests/rules/undirectedflowlowerbounds_ilp.rs"]
202mod tests;
problemreductions/rules/undirectedflowlowerbounds_ilp.rs

problemreductions/rules/
undirectedflowlowerbounds_ilp.rs
