problemreductions/rules/
boundedcomponentspanningforest_ilp.rs

1//! Reduction from BoundedComponentSpanningForest to ILP<i32>.
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::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12
13#[derive(Debug, Clone)]
14pub struct ReductionBCSFToILP {
15    target: ILP<i32>,
16    n: usize,
17    k: usize,
18}
19
20impl ReductionResult for ReductionBCSFToILP {
21    type Source = BoundedComponentSpanningForest<SimpleGraph, i32>;
22    type Target = ILP<i32>;
23
24    fn target_problem(&self) -> &ILP<i32> {
25        &self.target
26    }
27
28    /// One-hot decode: for each vertex v, output the unique component c with x_{v,c} = 1.
29    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
30        let n = self.n;
31        let k = self.k;
32        (0..n)
33            .map(|v| {
34                (0..k)
35                    .find(|&c| target_solution[v * k + c] == 1)
36                    .unwrap_or(0)
37            })
38            .collect()
39    }
40}
41
42#[reduction(
43    overhead = {
44        num_vars = "3 * num_vertices * max_components + 2 * max_components + 2 * num_edges * max_components",
45        num_constraints = "num_vertices + max_components + max_components + 2 * max_components + num_vertices * max_components + 4 * num_vertices * max_components + 4 * num_edges * max_components + num_vertices * max_components",
46    }
47)]
48impl ReduceTo<ILP<i32>> for BoundedComponentSpanningForest<SimpleGraph, i32> {
49    type Result = ReductionBCSFToILP;
50
51    fn reduce_to(&self) -> Self::Result {
52        let n = self.num_vertices();
53        let edges = self.graph().edges();
54        let m = edges.len();
55        let k = self.max_components();
56
57        let x_idx = |v: usize, c: usize| -> usize { v * k + c };
58        let u_idx = |c: usize| -> usize { n * k + c };
59        let r_idx = |v: usize, c: usize| -> usize { n * k + k + v * k + c };
60        let s_idx = |c: usize| -> usize { 2 * n * k + k + c };
61        let b_idx = |v: usize, c: usize| -> usize { 2 * n * k + 2 * k + v * k + c };
62        let f_idx =
63            |i: usize, eta: usize, c: usize| -> usize { 3 * n * k + 2 * k + (i * 2 + eta) * k + c };
64
65        let num_vars = 3 * n * k + 2 * k + 2 * m * k;
66        let n_f64 = n as f64;
67        let mut constraints = Vec::new();
68
69        // 1) Assignment: sum_c x_{v,c} = 1 for each vertex v
70        for v in 0..n {
71            let terms: Vec<(usize, f64)> = (0..k).map(|c| (x_idx(v, c), 1.0)).collect();
72            constraints.push(LinearConstraint::eq(terms, 1.0));
73        }
74
75        // 2) Weight bound: sum_v w_v * x_{v,c} <= B for each component c
76        for c in 0..k {
77            let terms: Vec<(usize, f64)> = self
78                .weights()
79                .iter()
80                .enumerate()
81                .map(|(v, &w)| (x_idx(v, c), w as f64))
82                .collect();
83            constraints.push(LinearConstraint::le(terms, *self.max_weight() as f64));
84        }
85
86        // 3) Size: s_c = sum_v x_{v,c}
87        for c in 0..k {
88            let mut terms: Vec<(usize, f64)> = vec![(s_idx(c), -1.0)];
89            for v in 0..n {
90                terms.push((x_idx(v, c), 1.0));
91            }
92            constraints.push(LinearConstraint::eq(terms, 0.0));
93        }
94
95        // 4) Nonempty indicator: u_c <= s_c and s_c <= n * u_c
96        for c in 0..k {
97            constraints.push(LinearConstraint::le(
98                vec![(u_idx(c), 1.0), (s_idx(c), -1.0)],
99                0.0,
100            ));
101            constraints.push(LinearConstraint::le(
102                vec![(s_idx(c), 1.0), (u_idx(c), -n_f64)],
103                0.0,
104            ));
105        }
106
107        // 5) Root selection: sum_v r_{v,c} = u_c and r_{v,c} <= x_{v,c}
108        for c in 0..k {
109            let mut terms: Vec<(usize, f64)> = (0..n).map(|v| (r_idx(v, c), 1.0)).collect();
110            terms.push((u_idx(c), -1.0));
111            constraints.push(LinearConstraint::eq(terms, 0.0));
112
113            for v in 0..n {
114                constraints.push(LinearConstraint::le(
115                    vec![(r_idx(v, c), 1.0), (x_idx(v, c), -1.0)],
116                    0.0,
117                ));
118            }
119        }
120
121        // 6) Product linearization: b_{v,c} = s_c * r_{v,c}
122        for v in 0..n {
123            for c in 0..k {
124                // b <= s_c
125                constraints.push(LinearConstraint::le(
126                    vec![(b_idx(v, c), 1.0), (s_idx(c), -1.0)],
127                    0.0,
128                ));
129                // b <= n * r
130                constraints.push(LinearConstraint::le(
131                    vec![(b_idx(v, c), 1.0), (r_idx(v, c), -n_f64)],
132                    0.0,
133                ));
134                // b >= s - n*(1-r) => b - s - n*r >= -n
135                constraints.push(LinearConstraint::ge(
136                    vec![(b_idx(v, c), 1.0), (s_idx(c), -1.0), (r_idx(v, c), -n_f64)],
137                    -n_f64,
138                ));
139                // b >= 0
140                constraints.push(LinearConstraint::ge(vec![(b_idx(v, c), 1.0)], 0.0));
141            }
142        }
143
144        // 7) Flow capacity: 0 <= f_{i,eta,c} <= (n-1)*x_{u_i,c} and <= (n-1)*x_{v_i,c}
145        let cap = (n as f64) - 1.0;
146        for (i, &(u_e, v_e)) in edges.iter().enumerate() {
147            for eta in 0..2usize {
148                for c in 0..k {
149                    constraints.push(LinearConstraint::ge(vec![(f_idx(i, eta, c), 1.0)], 0.0));
150                    constraints.push(LinearConstraint::le(
151                        vec![(f_idx(i, eta, c), 1.0), (x_idx(u_e, c), -cap)],
152                        0.0,
153                    ));
154                    constraints.push(LinearConstraint::le(
155                        vec![(f_idx(i, eta, c), 1.0), (x_idx(v_e, c), -cap)],
156                        0.0,
157                    ));
158                }
159            }
160        }
161
162        // 8) Flow conservation: net_flow(v,c) = b_{v,c} - x_{v,c}
163        for v in 0..n {
164            for c in 0..k {
165                let mut terms: Vec<(usize, f64)> = Vec::new();
166
167                for (i, &(u_e, v_e)) in edges.iter().enumerate() {
168                    if u_e == v {
169                        terms.push((f_idx(i, 0, c), 1.0));
170                        terms.push((f_idx(i, 1, c), -1.0));
171                    }
172                    if v_e == v {
173                        terms.push((f_idx(i, 0, c), -1.0));
174                        terms.push((f_idx(i, 1, c), 1.0));
175                    }
176                }
177
178                terms.push((b_idx(v, c), -1.0));
179                terms.push((x_idx(v, c), 1.0));
180                constraints.push(LinearConstraint::eq(terms, 0.0));
181            }
182        }
183
184        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
185        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<i32>>::reduce_to(&source);
203            let ilp_sol = crate::solvers::ILPSolver::new()
204                .solve(reduction.target_problem())
205                .expect("ILP should be solvable");
206            let extracted = reduction.extract_solution(&ilp_sol);
207            crate::example_db::specs::rule_example_with_witness::<_, ILP<i32>>(
208                source,
209                SolutionPair {
210                    source_config: extracted,
211                    target_config: ilp_sol,
212                },
213            )
214        },
215    }]
216}
217
218#[cfg(test)]
219#[path = "../unit_tests/rules/boundedcomponentspanningforest_ilp.rs"]
220mod tests;
problemreductions/rules/boundedcomponentspanningforest_ilp.rs

problemreductions/rules/
boundedcomponentspanningforest_ilp.rs
