problemreductions/rules/
bmf_ilp.rs

1//! Reduction from BMF (Boolean Matrix Factorization) to ILP.
2//!
3//! Variables: binary b_{i,r}, c_{r,j}, McCormick product p_{i,r,j} = b_{i,r} * c_{r,j},
4//! reconstructed entry w_{i,j} = OR_r p_{i,r,j}. Pin w_{i,j} = A_{i,j} (exact factorization)
5//! and minimize sum_{i,r} b_{i,r} + sum_{r,j} c_{r,j} (total factor size).
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, BMF, ILP};
8use crate::reduction;
9use crate::rules::ilp_helpers::mccormick_product;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12#[derive(Debug, Clone)]
13pub struct ReductionBMFToILP {
14    target: ILP<bool>,
15    m: usize,
16    n: usize,
17    k: usize,
18}
19
20impl ReductionResult for ReductionBMFToILP {
21    type Source = BMF;
22    type Target = ILP<bool>;
23
24    fn target_problem(&self) -> &ILP<bool> {
25        &self.target
26    }
27
28    fn extract_solution(
29        &self,
30        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
31    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
32        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
33
34        let b = (0..self.m)
35            .map(|i| {
36                (0..self.k)
37                    .map(|r| target_solution[i * self.k + r] == 1)
38                    .collect()
39            })
40            .collect();
41        let c_offset = self.m * self.k;
42        let c = (0..self.k)
43            .map(|r| {
44                (0..self.n)
45                    .map(|j| target_solution[c_offset + r * self.n + j] == 1)
46                    .collect()
47            })
48            .collect();
49        Ok((b, c))
50    }
51}
52
53#[reduction(
54    transform = exact {
55        num_vars = "rows * rank + rank * cols + rows * rank * cols + rows * cols",
56        num_constraints = "3 * rows * rank * cols + rank * rows * cols + rows * cols + rows * cols",
57    },
58    unavailable = {
59        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
60    }
61)]
62impl ReduceTo<ILP<bool>> for BMF {
63    type Result = ReductionBMFToILP;
64
65    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
66        let m = self.rows();
67        let n = self.cols();
68        let k = self.rank();
69
70        // Variable layout:
71        // b_{i,r}: m*k variables at indices [0, m*k)
72        // c_{r,j}: k*n variables at indices [m*k, m*k + k*n)
73        // p_{i,r,j}: m*k*n variables at indices [m*k + k*n, m*k + k*n + m*k*n)
74        // w_{i,j}: m*n variables at indices [m*k + k*n + m*k*n, m*k + k*n + m*k*n + m*n)
75        let b_offset = 0;
76        let c_offset = m * k;
77        let p_offset = m * k + k * n;
78        let w_offset = p_offset + m * k * n;
79        let num_vars = w_offset + m * n;
80
81        let mut constraints = Vec::new();
82
83        for i in 0..m {
84            for j in 0..n {
85                for r in 0..k {
86                    let p_idx = p_offset + i * k * n + r * n + j;
87                    let b_idx = b_offset + i * k + r;
88                    let c_idx = c_offset + r * n + j;
89
90                    // McCormick: p_{i,r,j} = b_{i,r} * c_{r,j}
91                    constraints.extend(mccormick_product(p_idx, b_idx, c_idx));
92                }
93
94                let w_idx = w_offset + i * n + j;
95
96                // w_{i,j} >= p_{i,r,j} for all r
97                for r in 0..k {
98                    let p_idx = p_offset + i * k * n + r * n + j;
99                    constraints.push(LinearConstraint::ge(vec![(w_idx, 1), (p_idx, -1)], 0));
100                }
101
102                // w_{i,j} <= sum_r p_{i,r,j}
103                let mut w_upper_terms = vec![(w_idx, 1)];
104                for r in 0..k {
105                    let p_idx = p_offset + i * k * n + r * n + j;
106                    w_upper_terms.push((p_idx, -1));
107                }
108                constraints.push(LinearConstraint::le(w_upper_terms, 0));
109
110                // Exact factorization: w_{i,j} = A_{i,j}
111                let a_val = if self.matrix()[i][j] { 1 } else { 0 };
112                constraints.push(LinearConstraint::eq(vec![(w_idx, 1)], a_val));
113            }
114        }
115
116        // Objective: minimize sum_{i,r} b_{i,r} + sum_{r,j} c_{r,j} (total factor size)
117        let mut objective: Vec<(usize, i64)> = (0..m * k).map(|idx| (b_offset + idx, 1)).collect();
118        objective.extend((0..k * n).map(|idx| (c_offset + idx, 1)));
119
120        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
121            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
122        Ok(ReductionBMFToILP { target, m, n, k })
123    }
124}
125
126#[cfg(feature = "example-db")]
127pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
128    vec![crate::example_db::specs::RuleExampleSpec {
129        id: "bmf_to_ilp",
130        build: || {
131            // 2x2 identity matrix, rank 2
132            let source = BMF::new(vec![vec![true, false], vec![false, true]], 2);
133            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
134        },
135    }]
136}
137
138#[cfg(test)]
139#[path = "../unit_tests/rules/bmf_ilp.rs"]
140mod tests;
problemreductions/rules/bmf_ilp.rs

problemreductions/rules/
bmf_ilp.rs
