problemreductions/rules/
sparsematrixcompression_ilp.rs

1//! Reduction from SparseMatrixCompression to ILP.
2//!
3//! Assign each row one shift value and forbid any pair of shifted 1-entries
4//! from colliding in the storage vector.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, SparseMatrixCompression, ILP};
7use crate::reduction;
8use crate::rules::traits::{ReduceTo, ReductionResult};
9
10#[derive(Debug, Clone)]
11pub struct ReductionSMCToILP {
12    target: ILP<bool>,
13    num_rows: usize,
14    bound_k: usize,
15}
16
17impl ReductionResult for ReductionSMCToILP {
18    type Source = SparseMatrixCompression;
19    type Target = ILP<bool>;
20
21    fn target_problem(&self) -> &ILP<bool> {
22        &self.target
23    }
24
25    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
26        // For each row r, output the unique zero-based shift g with x_{r,g} = 1
27        (0..self.num_rows)
28            .map(|r| {
29                (0..self.bound_k)
30                    .find(|&g| target_solution[r * self.bound_k + g] == 1)
31                    .unwrap_or(0)
32            })
33            .collect()
34    }
35}
36
37#[reduction(
38    overhead = {
39        num_vars = "num_rows * bound_k",
40        num_constraints = "num_rows + num_rows * num_rows * bound_k * bound_k",
41    }
42)]
43impl ReduceTo<ILP<bool>> for SparseMatrixCompression {
44    type Result = ReductionSMCToILP;
45
46    fn reduce_to(&self) -> Self::Result {
47        let m = self.num_rows();
48        let n = self.num_cols();
49        let k = self.bound_k();
50
51        // Variable layout:
52        // x_{r,g}: m*K binary variables at [0, m*K)
53        //   x_{r*K + g} = 1 iff row r uses shift g (zero-based)
54        let num_vars = m * k;
55        let mut constraints = Vec::new();
56
57        // Each row assigned exactly one shift
58        for r in 0..m {
59            let terms: Vec<(usize, f64)> = (0..k).map(|g| (r * k + g, 1.0)).collect();
60            constraints.push(LinearConstraint::eq(terms, 1.0));
61        }
62
63        // Collision constraints:
64        // x_{r,g} + x_{s,h} <= 1 whenever A_{r,i} = A_{s,j} = 1 and i + g = j + h
65        // (for different rows r != s, or same row r = s but different columns i != j)
66        for r in 0..m {
67            for s in (r + 1)..m {
68                for i in 0..n {
69                    if !self.matrix()[r][i] {
70                        continue;
71                    }
72                    for j in 0..n {
73                        if !self.matrix()[s][j] {
74                            continue;
75                        }
76                        // Collision when i + g = j + h, i.e., g - h = j - i
77                        for g in 0..k {
78                            // h = g + i - j (must be in [0, k))
79                            let gi = g + i;
80                            if gi < j {
81                                continue;
82                            }
83                            let h = gi - j;
84                            if h >= k {
85                                continue;
86                            }
87                            constraints.push(LinearConstraint::le(
88                                vec![(r * k + g, 1.0), (s * k + h, 1.0)],
89                                1.0,
90                            ));
91                        }
92                    }
93                }
94            }
95        }
96
97        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
98        ReductionSMCToILP {
99            target,
100            num_rows: m,
101            bound_k: k,
102        }
103    }
104}
105
106#[cfg(feature = "example-db")]
107pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
108    use crate::export::SolutionPair;
109    vec![crate::example_db::specs::RuleExampleSpec {
110        id: "sparsematrixcompression_to_ilp",
111        build: || {
112            let source = SparseMatrixCompression::new(
113                vec![
114                    vec![true, false, false, true],
115                    vec![false, true, false, false],
116                    vec![false, false, true, false],
117                    vec![true, false, false, false],
118                ],
119                2,
120            );
121            let reduction: ReductionSMCToILP = ReduceTo::<ILP<bool>>::reduce_to(&source);
122            let ilp_solver = crate::solvers::ILPSolver::new();
123            let target_config = ilp_solver
124                .solve(reduction.target_problem())
125                .expect("ILP should be solvable");
126            let extracted = reduction.extract_solution(&target_config);
127            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
128                source,
129                SolutionPair {
130                    source_config: extracted,
131                    target_config,
132                },
133            )
134        },
135    }]
136}
137
138#[cfg(test)]
139#[path = "../unit_tests/rules/sparsematrixcompression_ilp.rs"]
140mod tests;
problemreductions/rules/sparsematrixcompression_ilp.rs

problemreductions/rules/
sparsematrixcompression_ilp.rs
