problemreductions/rules/
undirectedflowlowerbounds_ilp.rs

1//! Reduction from UndirectedFlowLowerBounds to `ILP<i64, i64, Bounded>`.
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 (up to 5 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//! 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, 5*|E| + |V| + 1 constraints.
25
26use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
27use crate::models::graph::UndirectedFlowLowerBounds;
28use crate::reduction;
29use crate::rules::ilp_helpers::bounded_flow_requirement;
30use crate::rules::traits::{ReduceTo, ReductionResult};
31use crate::topology::Graph;
32
33/// Result of reducing UndirectedFlowLowerBounds to `ILP<i64, i64, Bounded>`.
34///
35/// Variable layout:
36/// - `f_{uv}` at 2*e (flow u→v on edge e)
37/// - `f_{vu}` at 2*e + 1 (flow v→u on edge e)
38/// - `z_e` at 2*|E| + e (orientation indicator: 1 = u→v direction)
39#[derive(Debug, Clone)]
40pub struct ReductionUFLBToILP {
41    target: ILP<i64, i64, Bounded>,
42    num_edges: usize,
43}
44
45impl ReductionResult for ReductionUFLBToILP {
46    type Source = UndirectedFlowLowerBounds;
47    type Target = ILP<i64, i64, Bounded>;
48
49    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
50        &self.target
51    }
52
53    /// Extract edge orientation from ILP: z_e values at indices [2*|E|..3*|E|).
54    ///
55    /// The model encodes orientation as config[e] = 0 for u→v, 1 for v→u.
56    /// The ILP uses z_e = 1 for u→v, z_e = 0 for v→u.
57    /// So we return 1 - z_e to match the model's convention.
58    fn extract_solution(
59        &self,
60        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
61    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
62        crate::rules::traits::validate_target_witness(
63            self.target_problem(),
64            target_solution,
65            |value| value.value.is_some(),
66            "target ILP assignment is infeasible",
67        )?;
68
69        Ok({
70            let e = self.num_edges;
71            target_solution[2 * e..3 * e]
72                .iter()
73                .map(|&z| z == 0)
74                .collect()
75        })
76    }
77}
78
79#[crate::aggregate_reduction(ilp_feasibility)]
80impl crate::rules::AggregateReductionResult for ReductionUFLBToILP {}
81
82#[reduction(
83    transform = upper_bound {
84        max_constraint_magnitude_bits = "max_capacity_bits + num_edges + 1",
85        num_vars = "3 * num_edges",
86        num_constraints = "5 * num_edges + num_vertices + 1",
87        num_nonzeros = "(3 * num_edges) * (5 * num_edges + num_vertices + 1)",
88    },
89)]
90impl ReduceTo<ILP<i64, i64, Bounded>> for UndirectedFlowLowerBounds {
91    type Result = ReductionUFLBToILP;
92
93    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
94        let edges = self.graph().edges();
95        let e = edges.len();
96        let n = self.num_vertices();
97        let num_vars = 3 * e;
98        let f_uv = |edge: usize| 2 * edge;
99        let f_vu = |edge: usize| 2 * edge + 1;
100        let z = |edge: usize| 2 * e + edge;
101
102        let mut constraints = Vec::new();
103
104        for (edge_idx, _) in edges.iter().enumerate() {
105            let cap = self.capacities()[edge_idx];
106            let lower = self.lower_bounds()[edge_idx];
107
108            // z_e ≤ 1 (binary)
109            constraints.push(LinearConstraint::le(vec![(z(edge_idx), 1)], 1));
110
111            // f_{uv} ≤ cap * z_e  =>  f_{uv} - cap*z_e ≤ 0
112            constraints.push(LinearConstraint::le(
113                vec![(f_uv(edge_idx), 1), (z(edge_idx), -cap)],
114                0,
115            ));
116
117            // f_{vu} ≤ cap * (1 - z_e)  =>  f_{vu} + cap*z_e ≤ cap
118            constraints.push(LinearConstraint::le(
119                vec![(f_vu(edge_idx), 1), (z(edge_idx), cap)],
120                cap,
121            ));
122
123            if lower > 0 {
124                // f_{uv} ≥ lower * z_e  =>  f_{uv} - lower*z_e ≥ 0
125                constraints.push(LinearConstraint::ge(
126                    vec![(f_uv(edge_idx), 1), (z(edge_idx), -lower)],
127                    0,
128                ));
129
130                // f_{vu} ≥ lower * (1 - z_e)  =>  f_{vu} + lower*z_e ≥ lower
131                constraints.push(LinearConstraint::ge(
132                    vec![(f_vu(edge_idx), 1), (z(edge_idx), lower)],
133                    lower,
134                ));
135            }
136        }
137
138        // Flow conservation at non-terminal vertices
139        for vertex in 0..n {
140            if vertex == self.source() || vertex == self.sink() {
141                continue;
142            }
143
144            let mut terms: Vec<(usize, i64)> = Vec::new();
145            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
146                if vertex == u {
147                    // f_{uv} leaves vertex u, f_{vu} enters
148                    terms.push((f_uv(edge_idx), -1));
149                    terms.push((f_vu(edge_idx), 1));
150                }
151                if vertex == v {
152                    // f_{uv} enters vertex v, f_{vu} leaves
153                    terms.push((f_uv(edge_idx), 1));
154                    terms.push((f_vu(edge_idx), -1));
155                }
156            }
157
158            if !terms.is_empty() {
159                constraints.push(LinearConstraint::eq(terms, 0));
160            }
161        }
162
163        // Net flow into sink ≥ requirement
164        let sink = self.sink();
165        let mut sink_terms: Vec<(usize, i64)> = Vec::new();
166        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
167            if v == sink {
168                // f_{uv} flows into sink, f_{vu} flows out
169                sink_terms.push((f_uv(edge_idx), 1));
170                sink_terms.push((f_vu(edge_idx), -1));
171            }
172            if u == sink {
173                // f_{vu} flows into sink (from v side), f_{uv} flows out
174                sink_terms.push((f_uv(edge_idx), -1));
175                sink_terms.push((f_vu(edge_idx), 1));
176            }
177        }
178        let requirement =
179            bounded_flow_requirement(self.requirement(), self.capacities().iter().copied());
180        constraints.push(LinearConstraint::ge(sink_terms, requirement));
181
182        let mut variables = self
183            .capacities()
184            .iter()
185            .flat_map(|&capacity| std::iter::repeat_n(capacity, 2))
186            .map(|capacity| IntegerVariable::new(Some(0), Some(capacity)))
187            .collect::<Result<Vec<_>, _>>()
188            .map_err(Self::target_construction)?;
189        variables.resize(num_vars, IntegerVariable::binary());
190
191        Ok(ReductionUFLBToILP {
192            target: ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
193                .map_err(Self::target_construction)?,
194            num_edges: e,
195        })
196    }
197}
198
199#[cfg(feature = "example-db")]
200pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
201    use crate::topology::SimpleGraph;
202
203    vec![crate::example_db::specs::RuleExampleSpec {
204        id: "undirectedflowlowerbounds_to_ilp",
205        build: || {
206            // 3-vertex graph: edge (0,1) cap=2 lower=1, edge (1,2) cap=2 lower=1
207            // source=0, sink=2, requirement=1
208            let source = UndirectedFlowLowerBounds::new(
209                SimpleGraph::new(3, vec![(0, 1), (1, 2)]),
210                vec![2, 2],
211                vec![1, 1],
212                0,
213                2,
214                1,
215            );
216            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
217        },
218    }]
219}
220
221#[cfg(test)]
222#[path = "../unit_tests/rules/undirectedflowlowerbounds_ilp.rs"]
223mod tests;
problemreductions/rules/undirectedflowlowerbounds_ilp.rs

problemreductions/rules/
undirectedflowlowerbounds_ilp.rs
