problemreductions/rules/
boundedcomponentspanningforest_ilp.rs

1//! Reduction from BoundedComponentSpanningForest to `ILP<i64>`.
2//!
3//! Assign every vertex to one of K components, bound weight, certify
4//! connectivity inside each used component via flow.
5//! See the paper entry for the full formulation.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::BoundedComponentSpanningForest;
9use crate::reduction;
10use crate::rules::ilp_helpers::one_hot_decode_rows;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::{Graph, SimpleGraph};
13
14#[derive(Debug, Clone)]
15pub struct ReductionBCSFToILP {
16    target: ILP<i64>,
17    n: usize,
18    k: usize,
19}
20
21impl ReductionResult for ReductionBCSFToILP {
22    type Source = BoundedComponentSpanningForest<SimpleGraph, i64>;
23    type Target = ILP<i64>;
24
25    fn target_problem(&self) -> &ILP<i64> {
26        &self.target
27    }
28
29    /// One-hot decode: for each vertex v, output the unique component c with x_{v,c} = 1.
30    fn extract_solution(
31        &self,
32        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
33    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
34        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
35
36        one_hot_decode_rows(target_solution, self.n, self.k, 0)
37    }
38}
39
40#[reduction(
41    transform = exact {
42        num_vars = "3 * num_vertices * max_components + 2 * max_components + 2 * num_edges * max_components",
43        num_constraints = "num_vertices + 5 * max_components + 6 * num_vertices * max_components + 6 * num_edges * max_components",
44    },
45    unavailable = {
46        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
47    }
48)]
49impl ReduceTo<ILP<i64>> for BoundedComponentSpanningForest<SimpleGraph, i64> {
50    type Result = ReductionBCSFToILP;
51
52    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
53        let n = self.num_vertices();
54        let edges = self.graph().edges();
55        let m = edges.len();
56        let k = self.max_components();
57
58        let x_idx = |v: usize, c: usize| -> usize { v * k + c };
59        let u_idx = |c: usize| -> usize { n * k + c };
60        let r_idx = |v: usize, c: usize| -> usize { n * k + k + v * k + c };
61        let s_idx = |c: usize| -> usize { 2 * n * k + k + c };
62        let b_idx = |v: usize, c: usize| -> usize { 2 * n * k + 2 * k + v * k + c };
63        let f_idx =
64            |i: usize, eta: usize, c: usize| -> usize { 3 * n * k + 2 * k + (i * 2 + eta) * k + c };
65
66        let num_vars = 3 * n * k + 2 * k + 2 * m * k;
67        let n_i64 = Self::exact_i64(n, "encoding the vertex count")?;
68        let mut constraints = Vec::new();
69        let weights = self.weights();
70        let max_weight = *self.max_weight();
71
72        // 1) Assignment: sum_c x_{v,c} = 1 for each vertex v
73        for v in 0..n {
74            let terms: Vec<(usize, i64)> = (0..k).map(|c| (x_idx(v, c), 1)).collect();
75            constraints.push(LinearConstraint::eq(terms, 1));
76        }
77
78        // 2) Weight bound: sum_v w_v * x_{v,c} <= B for each component c
79        for c in 0..k {
80            let terms: Vec<(usize, i64)> = weights
81                .iter()
82                .enumerate()
83                .map(|(vertex, &weight)| (x_idx(vertex, c), weight))
84                .collect();
85            constraints.push(LinearConstraint::le(terms, max_weight));
86        }
87
88        // 3) Size: s_c = sum_v x_{v,c}
89        for c in 0..k {
90            let mut terms: Vec<(usize, i64)> = vec![(s_idx(c), -1)];
91            for v in 0..n {
92                terms.push((x_idx(v, c), 1));
93            }
94            constraints.push(LinearConstraint::eq(terms, 0));
95        }
96
97        // 4) Nonempty indicator: u_c <= s_c and s_c <= n * u_c
98        for c in 0..k {
99            constraints.push(LinearConstraint::le(vec![(u_idx(c), 1), (s_idx(c), -1)], 0));
100            constraints.push(LinearConstraint::le(
101                vec![(s_idx(c), 1), (u_idx(c), -n_i64)],
102                0,
103            ));
104        }
105
106        // 5) Root selection: sum_v r_{v,c} = u_c and r_{v,c} <= x_{v,c}
107        for c in 0..k {
108            let mut terms: Vec<(usize, i64)> = (0..n).map(|v| (r_idx(v, c), 1)).collect();
109            terms.push((u_idx(c), -1));
110            constraints.push(LinearConstraint::eq(terms, 0));
111
112            for v in 0..n {
113                constraints.push(LinearConstraint::le(
114                    vec![(r_idx(v, c), 1), (x_idx(v, c), -1)],
115                    0,
116                ));
117            }
118        }
119
120        // 6) Product linearization: b_{v,c} = s_c * r_{v,c}
121        for v in 0..n {
122            for c in 0..k {
123                // b <= s_c
124                constraints.push(LinearConstraint::le(
125                    vec![(b_idx(v, c), 1), (s_idx(c), -1)],
126                    0,
127                ));
128                // b <= n * r
129                constraints.push(LinearConstraint::le(
130                    vec![(b_idx(v, c), 1), (r_idx(v, c), -n_i64)],
131                    0,
132                ));
133                // b >= s - n*(1-r) => b - s - n*r >= -n
134                constraints.push(LinearConstraint::ge(
135                    vec![(b_idx(v, c), 1), (s_idx(c), -1), (r_idx(v, c), -n_i64)],
136                    -n_i64,
137                ));
138                // b >= 0
139                constraints.push(LinearConstraint::ge(vec![(b_idx(v, c), 1)], 0));
140            }
141        }
142
143        // 7) Flow capacity: 0 <= f_{i,eta,c} <= (n-1)*x_{u_i,c} and <= (n-1)*x_{v_i,c}
144        let cap = n_i64 - 1;
145        for (i, &(u_e, v_e)) in edges.iter().enumerate() {
146            for eta in 0..2usize {
147                for c in 0..k {
148                    constraints.push(LinearConstraint::ge(vec![(f_idx(i, eta, c), 1)], 0));
149                    constraints.push(LinearConstraint::le(
150                        vec![(f_idx(i, eta, c), 1), (x_idx(u_e, c), -cap)],
151                        0,
152                    ));
153                    constraints.push(LinearConstraint::le(
154                        vec![(f_idx(i, eta, c), 1), (x_idx(v_e, c), -cap)],
155                        0,
156                    ));
157                }
158            }
159        }
160
161        // 8) Flow conservation: net_flow(v,c) = b_{v,c} - x_{v,c}
162        for v in 0..n {
163            for c in 0..k {
164                let mut terms: Vec<(usize, i64)> = Vec::new();
165
166                for (i, &(u_e, v_e)) in edges.iter().enumerate() {
167                    if u_e == v {
168                        terms.push((f_idx(i, 0, c), 1));
169                        terms.push((f_idx(i, 1, c), -1));
170                    }
171                    if v_e == v {
172                        terms.push((f_idx(i, 0, c), -1));
173                        terms.push((f_idx(i, 1, c), 1));
174                    }
175                }
176
177                terms.push((b_idx(v, c), -1));
178                terms.push((x_idx(v, c), 1));
179                constraints.push(LinearConstraint::eq(terms, 0));
180            }
181        }
182
183        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
184            .map_err(Self::target_construction)?;
185        Ok(ReductionBCSFToILP { target, n, k })
186    }
187}
188
189#[cfg(feature = "example-db")]
190pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
191    use crate::export::SolutionPair;
192    vec![crate::example_db::specs::RuleExampleSpec {
193        id: "boundedcomponentspanningforest_to_ilp",
194        build: || {
195            let source = BoundedComponentSpanningForest::new(
196                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
197                vec![1, 2, 2, 1],
198                2,
199                4,
200            );
201            let reduction: ReductionBCSFToILP =
202                crate::rules::ReduceTo::<ILP<i64>>::reduce_to(&source)
203                    .expect("reduction should succeed");
204            let ilp_sol = crate::solvers::ILPSolver::new()
205                .solve(reduction.target_problem())
206                .expect("ILP should be solvable");
207            let extracted = reduction.extract_solution(&ilp_sol).unwrap();
208            crate::example_db::specs::rule_example_with_witness::<_, ILP<i64>>(
209                source,
210                SolutionPair {
211                    source_config: serde_json::json!(extracted),
212                    target_config: serde_json::json!(ilp_sol),
213                },
214            )
215        },
216    }]
217}
218
219#[cfg(test)]
220#[path = "../unit_tests/rules/boundedcomponentspanningforest_ilp.rs"]
221mod tests;
problemreductions/rules/boundedcomponentspanningforest_ilp.rs

problemreductions/rules/
boundedcomponentspanningforest_ilp.rs
