problemreductions/rules/
undirectedtwocommodityintegralflow_ilp.rs

1//! Reduction from UndirectedTwoCommodityIntegralFlow to `ILP<i64, i64, Bounded>`.
2//!
3//! For each undirected edge {u,v} (indexed by e), we introduce 4 flow variables:
4//!   f1_{uv} = 4*e + 0  (commodity 1 flow u→v)
5//!   f1_{vu} = 4*e + 1  (commodity 1 flow v→u)
6//!   f2_{uv} = 4*e + 2  (commodity 2 flow u→v)
7//!   f2_{vu} = 4*e + 3  (commodity 2 flow v→u)
8//!
9//! Additional binary indicator variables for capacity sharing:
10//!   d1_e = 4*|E| + 2*e     (1 if commodity 1 uses forward direction on edge e)
11//!   d2_e = 4*|E| + 2*e + 1 (1 if commodity 2 uses forward direction on edge e)
12//!
13//! For each edge e with capacity c_e, the joint capacity constraint is:
14//!   max(f1_{uv}, f1_{vu}) + max(f2_{uv}, f2_{vu}) ≤ c_e
15//!
16//! Since this is `ILP<i64, i64, Bounded>`, we use direction indicators d1_e, d2_e ∈ {0,1} to linearize:
17//!   f1_{uv} ≤ c_e * d1_e;  f1_{vu} ≤ c_e * (1 - d1_e)
18//!   f2_{uv} ≤ c_e * d2_e;  f2_{vu} ≤ c_e * (1 - d2_e)
19//!   f1_{uv} + f1_{vu} + f2_{uv} + f2_{vu} ≤ c_e  (joint capacity)
20//!
21//! Variable layout (6 variables per edge):
22//!   [0..4*E): f1_{uv}, f1_{vu}, f2_{uv}, f2_{vu} per edge
23//!   [4*E..6*E): d1_e, d2_e per edge
24//!
25//! Constraints per edge (7 per edge) + flow conservation (2 per non-terminal vertex) + net flow (2)
26
27use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
28use crate::models::graph::UndirectedTwoCommodityIntegralFlow;
29use crate::reduction;
30use crate::rules::ilp_helpers::bounded_flow_requirement;
31use crate::rules::traits::{ReduceTo, ReductionResult};
32use crate::topology::Graph;
33
34/// Result of reducing UndirectedTwoCommodityIntegralFlow to `ILP<i64, i64, Bounded>`.
35///
36/// Variable layout:
37/// - `f1_{uv}` at 4*e + 0, `f1_{vu}` at 4*e + 1 (commodity 1 flows on edge e)
38/// - `f2_{uv}` at 4*e + 2, `f2_{vu}` at 4*e + 3 (commodity 2 flows on edge e)
39/// - `d1_e` at 4*|E| + 2*e, `d2_e` at 4*|E| + 2*e + 1 (direction indicators)
40#[derive(Debug, Clone)]
41pub struct ReductionU2CIFToILP {
42    target: ILP<i64, i64, Bounded>,
43    num_edges: usize,
44}
45
46impl ReductionResult for ReductionU2CIFToILP {
47    type Source = UndirectedTwoCommodityIntegralFlow;
48    type Target = ILP<i64, i64, Bounded>;
49
50    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
51        &self.target
52    }
53
54    /// Extract flow solution: first 4*|E| variables are the flow values.
55    fn extract_solution(
56        &self,
57        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
58    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
59        crate::rules::traits::validate_target_witness(
60            self.target_problem(),
61            target_solution,
62            |value| value.value.is_some(),
63            "target ILP assignment is infeasible",
64        )?;
65
66        crate::rules::ilp_helpers::decode_usize_values(&target_solution[..4 * self.num_edges])
67    }
68}
69
70#[crate::aggregate_reduction(ilp_feasibility)]
71impl crate::rules::AggregateReductionResult for ReductionU2CIFToILP {}
72
73#[reduction(transform = {
74    exact {
75        num_vars = "6 * num_edges",
76        num_constraints = "7 * num_edges + num_conservation_constraints + 2",
77    },
78    upper_bound {
79        max_constraint_magnitude_bits = "max_capacity_bits + num_edges + 1",
80        num_nonzeros = "(6 * num_edges) * (7 * num_edges + num_conservation_constraints + 2)",
81    },
82})]
83impl ReduceTo<ILP<i64, i64, Bounded>> for UndirectedTwoCommodityIntegralFlow {
84    type Result = ReductionU2CIFToILP;
85
86    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
87        let edges = self.graph().edges();
88        let e = edges.len();
89        let n = self.num_vertices();
90        // 4*e flow variables + 2*e direction indicators = 6*e total
91        let num_vars = 6 * e;
92        // Variable index helpers
93        let f1_uv = |edge: usize| 4 * edge;
94        let f1_vu = |edge: usize| 4 * edge + 1;
95        let f2_uv = |edge: usize| 4 * edge + 2;
96        let f2_vu = |edge: usize| 4 * edge + 3;
97        let d1 = |edge: usize| 4 * e + 2 * edge;
98        let d2 = |edge: usize| 4 * e + 2 * edge + 1;
99
100        let mut constraints = Vec::with_capacity(7 * e + self.num_conservation_constraints() + 2);
101
102        for (edge_idx, (_u, _v)) in edges.iter().enumerate() {
103            let cap = self.capacities()[edge_idx];
104
105            // Direction indicators are binary: d1_e ≤ 1, d2_e ≤ 1
106            constraints.push(LinearConstraint::le(vec![(d1(edge_idx), 1)], 1));
107            constraints.push(LinearConstraint::le(vec![(d2(edge_idx), 1)], 1));
108
109            // Commodity 1 anti-parallel: f1_{uv} ≤ cap * d1_e
110            // => f1_{uv} - cap * d1_e ≤ 0
111            constraints.push(LinearConstraint::le(
112                vec![(f1_uv(edge_idx), 1), (d1(edge_idx), -cap)],
113                0,
114            ));
115            // f1_{vu} ≤ cap * (1 - d1_e) => f1_{vu} + cap*d1_e ≤ cap
116            constraints.push(LinearConstraint::le(
117                vec![(f1_vu(edge_idx), 1), (d1(edge_idx), cap)],
118                cap,
119            ));
120
121            // Commodity 2 anti-parallel: f2_{uv} ≤ cap * d2_e
122            constraints.push(LinearConstraint::le(
123                vec![(f2_uv(edge_idx), 1), (d2(edge_idx), -cap)],
124                0,
125            ));
126            // f2_{vu} ≤ cap * (1 - d2_e)
127            constraints.push(LinearConstraint::le(
128                vec![(f2_vu(edge_idx), 1), (d2(edge_idx), cap)],
129                cap,
130            ));
131
132            // Joint capacity: f1_{uv} + f1_{vu} + f2_{uv} + f2_{vu} ≤ cap
133            constraints.push(LinearConstraint::le(
134                vec![
135                    (f1_uv(edge_idx), 1),
136                    (f1_vu(edge_idx), 1),
137                    (f2_uv(edge_idx), 1),
138                    (f2_vu(edge_idx), 1),
139                ],
140                cap,
141            ));
142        }
143
144        // Each commodity is conserved at every vertex except its own source and sink.
145        for (commodity, source, sink) in [
146            (1, self.source_1(), self.sink_1()),
147            (2, self.source_2(), self.sink_2()),
148        ] {
149            for vertex in 0..n {
150                if vertex == source || vertex == sink {
151                    continue;
152                }
153
154                let mut terms = Vec::new();
155                for (edge_idx, &(u, v)) in edges.iter().enumerate() {
156                    let (uv, vu) = if commodity == 1 {
157                        (f1_uv(edge_idx), f1_vu(edge_idx))
158                    } else {
159                        (f2_uv(edge_idx), f2_vu(edge_idx))
160                    };
161                    if vertex == u {
162                        terms.push((uv, -1));
163                        terms.push((vu, 1));
164                    }
165                    if vertex == v {
166                        terms.push((uv, 1));
167                        terms.push((vu, -1));
168                    }
169                }
170                constraints.push(LinearConstraint::eq(terms, 0));
171            }
172        }
173
174        // Net flow into each sink must meet its normalized requirement.
175        for (sink, requirement, flow_offset) in [
176            (self.sink_1(), self.requirement_1(), 0),
177            (self.sink_2(), self.requirement_2(), 2),
178        ] {
179            let mut terms = Vec::new();
180            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
181                let uv = 4 * edge_idx + flow_offset;
182                let vu = uv + 1;
183                if sink == v {
184                    terms.push((uv, 1));
185                    terms.push((vu, -1));
186                }
187                if sink == u {
188                    terms.push((uv, -1));
189                    terms.push((vu, 1));
190                }
191            }
192            let requirement =
193                bounded_flow_requirement(requirement, self.capacities().iter().copied());
194            constraints.push(LinearConstraint::ge(terms, requirement));
195        }
196
197        let mut variables = self
198            .capacities()
199            .iter()
200            .flat_map(|&capacity| std::iter::repeat_n(capacity, 4))
201            .map(|capacity| IntegerVariable::new(Some(0), Some(capacity)))
202            .collect::<Result<Vec<_>, _>>()
203            .map_err(Self::target_construction)?;
204        variables.resize(num_vars, IntegerVariable::binary());
205
206        Ok(ReductionU2CIFToILP {
207            target: ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
208                .map_err(Self::target_construction)?,
209            num_edges: e,
210        })
211    }
212}
213
214#[cfg(feature = "example-db")]
215pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
216    use crate::export::SolutionPair;
217    use crate::topology::SimpleGraph;
218
219    vec![crate::example_db::specs::RuleExampleSpec {
220        id: "undirectedtwocommodityintegralflow_to_ilp",
221        build: || {
222            // 4-vertex graph: edges (0,2),(1,2),(2,3); capacities [1,1,2]
223            // s1=0, t1=3, s2=1, t2=3, R1=1, R2=1
224            // f1 routes 0→2→3 (1 unit), f2 routes 1→2→3 (1 unit)
225            let source = UndirectedTwoCommodityIntegralFlow::new(
226                SimpleGraph::new(4, vec![(0, 2), (1, 2), (2, 3)]),
227                vec![1, 1, 2],
228                0,
229                3,
230                1,
231                3,
232                1,
233                1,
234            );
235            let reduction: ReductionU2CIFToILP =
236                ReduceTo::<ILP<i64, i64, Bounded>>::reduce_to(&source)
237                    .expect("reduction should succeed");
238            let solver = crate::solvers::ILPSolver::new();
239            let target_config = solver
240                .solve(reduction.target_problem())
241                .expect("canonical example should be feasible");
242            let source_config = reduction.extract_solution(&target_config).unwrap();
243            crate::example_db::specs::rule_example_with_witness::<_, ILP<i64, i64, Bounded>>(
244                source,
245                SolutionPair {
246                    source_config: serde_json::to_value(source_config)
247                        .expect("solution serialization must succeed"),
248                    target_config: serde_json::to_value(target_config)
249                        .expect("solution serialization must succeed"),
250                },
251            )
252        },
253    }]
254}
255
256#[cfg(test)]
257#[path = "../unit_tests/rules/undirectedtwocommodityintegralflow_ilp.rs"]
258mod tests;
problemreductions/rules/undirectedtwocommodityintegralflow_ilp.rs

problemreductions/rules/
undirectedtwocommodityintegralflow_ilp.rs
