problemreductions/rules/
undirectedflowlowerbounds_ilp.rs

1//! Reduction from UndirectedFlowLowerBounds to ILP<i32>.
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//! Overhead: 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<i32>.
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<i32>,
41    num_edges: usize,
42}
43
44impl ReductionResult for ReductionUFLBToILP {
45    type Source = UndirectedFlowLowerBounds;
46    type Target = ILP<i32>;
47
48    fn target_problem(&self) -> &ILP<i32> {
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(&self, target_solution: &[usize]) -> Vec<usize> {
58        let e = self.num_edges;
59        target_solution[2 * e..3 * e]
60            .iter()
61            .map(|&z| 1 - z)
62            .collect()
63    }
64}
65
66#[reduction(
67    overhead = {
68        num_vars = "3 * num_edges",
69        num_constraints = "4 * num_edges + num_vertices + 1",
70    }
71)]
72impl ReduceTo<ILP<i32>> for UndirectedFlowLowerBounds {
73    type Result = ReductionUFLBToILP;
74
75    fn reduce_to(&self) -> Self::Result {
76        let edges = self.graph().edges();
77        let e = edges.len();
78        let n = self.num_vertices();
79        let num_vars = 3 * e;
80
81        let f_uv = |edge: usize| 2 * edge;
82        let f_vu = |edge: usize| 2 * edge + 1;
83        let z = |edge: usize| 2 * e + edge;
84
85        let mut constraints = Vec::new();
86
87        for (edge_idx, _) in edges.iter().enumerate() {
88            let cap = self.capacities()[edge_idx] as f64;
89            let lower = self.lower_bounds()[edge_idx] as f64;
90
91            // z_e ≤ 1 (binary)
92            constraints.push(LinearConstraint::le(vec![(z(edge_idx), 1.0)], 1.0));
93
94            // f_{uv} ≤ cap * z_e  =>  f_{uv} - cap*z_e ≤ 0
95            constraints.push(LinearConstraint::le(
96                vec![(f_uv(edge_idx), 1.0), (z(edge_idx), -cap)],
97                0.0,
98            ));
99
100            // f_{vu} ≤ cap * (1 - z_e)  =>  f_{vu} + cap*z_e ≤ cap
101            constraints.push(LinearConstraint::le(
102                vec![(f_vu(edge_idx), 1.0), (z(edge_idx), cap)],
103                cap,
104            ));
105
106            if lower > 0.0 {
107                // f_{uv} ≥ lower * z_e  =>  f_{uv} - lower*z_e ≥ 0
108                constraints.push(LinearConstraint::ge(
109                    vec![(f_uv(edge_idx), 1.0), (z(edge_idx), -lower)],
110                    0.0,
111                ));
112
113                // f_{vu} ≥ lower * (1 - z_e)  =>  f_{vu} + lower*z_e ≥ lower
114                constraints.push(LinearConstraint::ge(
115                    vec![(f_vu(edge_idx), 1.0), (z(edge_idx), lower)],
116                    lower,
117                ));
118            }
119        }
120
121        // Flow conservation at non-terminal vertices
122        for vertex in 0..n {
123            if vertex == self.source() || vertex == self.sink() {
124                continue;
125            }
126
127            let mut terms: Vec<(usize, f64)> = Vec::new();
128            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
129                if vertex == u {
130                    // f_{uv} leaves vertex u, f_{vu} enters
131                    terms.push((f_uv(edge_idx), -1.0));
132                    terms.push((f_vu(edge_idx), 1.0));
133                } else if vertex == v {
134                    // f_{uv} enters vertex v, f_{vu} leaves
135                    terms.push((f_uv(edge_idx), 1.0));
136                    terms.push((f_vu(edge_idx), -1.0));
137                }
138            }
139
140            if !terms.is_empty() {
141                constraints.push(LinearConstraint::eq(terms, 0.0));
142            }
143        }
144
145        // Net flow into sink ≥ requirement
146        let sink = self.sink();
147        let mut sink_terms: Vec<(usize, f64)> = Vec::new();
148        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
149            if v == sink {
150                // f_{uv} flows into sink, f_{vu} flows out
151                sink_terms.push((f_uv(edge_idx), 1.0));
152                sink_terms.push((f_vu(edge_idx), -1.0));
153            } else if u == sink {
154                // f_{vu} flows into sink (from v side), f_{uv} flows out
155                sink_terms.push((f_uv(edge_idx), -1.0));
156                sink_terms.push((f_vu(edge_idx), 1.0));
157            }
158        }
159        constraints.push(LinearConstraint::ge(sink_terms, self.requirement() as f64));
160
161        ReductionUFLBToILP {
162            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
163            num_edges: e,
164        }
165    }
166}
167
168#[cfg(feature = "example-db")]
169pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
170    use crate::topology::SimpleGraph;
171
172    vec![crate::example_db::specs::RuleExampleSpec {
173        id: "undirectedflowlowerbounds_to_ilp",
174        build: || {
175            // 3-vertex graph: edge (0,1) cap=2 lower=1, edge (1,2) cap=2 lower=1
176            // source=0, sink=2, requirement=1
177            let source = UndirectedFlowLowerBounds::new(
178                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
179                vec![2, 2],
180                vec![1, 1],
181                0,
182                2,
183                1,
184            );
185            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
186        },
187    }]
188}
189
190#[cfg(test)]
191#[path = "../unit_tests/rules/undirectedflowlowerbounds_ilp.rs"]
192mod tests;
problemreductions/rules/undirectedflowlowerbounds_ilp.rs

problemreductions/rules/
undirectedflowlowerbounds_ilp.rs
