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(&self, target_solution: &[usize]) -> Vec<usize> {
29        // Extract B (m x k) then C (k x n) — first m*k + k*n variables
30        let total = self.m * self.k + self.k * self.n;
31        target_solution[..total].to_vec()
32    }
33}
34
35#[reduction(
36    overhead = {
37        num_vars = "rows * rank + rank * cols + rows * rank * cols + rows * cols",
38        num_constraints = "3 * rows * rank * cols + rank * rows * cols + rows * cols + rows * cols",
39    }
40)]
41impl ReduceTo<ILP<bool>> for BMF {
42    type Result = ReductionBMFToILP;
43
44    fn reduce_to(&self) -> Self::Result {
45        let m = self.rows();
46        let n = self.cols();
47        let k = self.rank();
48
49        // Variable layout:
50        // b_{i,r}: m*k variables at indices [0, m*k)
51        // c_{r,j}: k*n variables at indices [m*k, m*k + k*n)
52        // p_{i,r,j}: m*k*n variables at indices [m*k + k*n, m*k + k*n + m*k*n)
53        // w_{i,j}: m*n variables at indices [m*k + k*n + m*k*n, m*k + k*n + m*k*n + m*n)
54        let b_offset = 0;
55        let c_offset = m * k;
56        let p_offset = m * k + k * n;
57        let w_offset = p_offset + m * k * n;
58        let num_vars = w_offset + m * n;
59
60        let mut constraints = Vec::new();
61
62        for i in 0..m {
63            for j in 0..n {
64                for r in 0..k {
65                    let p_idx = p_offset + i * k * n + r * n + j;
66                    let b_idx = b_offset + i * k + r;
67                    let c_idx = c_offset + r * n + j;
68
69                    // McCormick: p_{i,r,j} = b_{i,r} * c_{r,j}
70                    constraints.extend(mccormick_product(p_idx, b_idx, c_idx));
71                }
72
73                let w_idx = w_offset + i * n + j;
74
75                // w_{i,j} >= p_{i,r,j} for all r
76                for r in 0..k {
77                    let p_idx = p_offset + i * k * n + r * n + j;
78                    constraints.push(LinearConstraint::ge(vec![(w_idx, 1.0), (p_idx, -1.0)], 0.0));
79                }
80
81                // w_{i,j} <= sum_r p_{i,r,j}
82                let mut w_upper_terms = vec![(w_idx, 1.0)];
83                for r in 0..k {
84                    let p_idx = p_offset + i * k * n + r * n + j;
85                    w_upper_terms.push((p_idx, -1.0));
86                }
87                constraints.push(LinearConstraint::le(w_upper_terms, 0.0));
88
89                // Exact factorization: w_{i,j} = A_{i,j}
90                let a_val = if self.matrix()[i][j] { 1.0 } else { 0.0 };
91                constraints.push(LinearConstraint::eq(vec![(w_idx, 1.0)], a_val));
92            }
93        }
94
95        // Objective: minimize sum_{i,r} b_{i,r} + sum_{r,j} c_{r,j} (total factor size)
96        let mut objective: Vec<(usize, f64)> =
97            (0..m * k).map(|idx| (b_offset + idx, 1.0)).collect();
98        objective.extend((0..k * n).map(|idx| (c_offset + idx, 1.0)));
99
100        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
101        ReductionBMFToILP { target, m, n, k }
102    }
103}
104
105#[cfg(feature = "example-db")]
106pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
107    vec![crate::example_db::specs::RuleExampleSpec {
108        id: "bmf_to_ilp",
109        build: || {
110            // 2x2 identity matrix, rank 2
111            let source = BMF::new(vec![vec![true, false], vec![false, true]], 2);
112            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
113        },
114    }]
115}
116
117#[cfg(test)]
118#[path = "../unit_tests/rules/bmf_ilp.rs"]
119mod tests;
problemreductions/rules/bmf_ilp.rs

problemreductions/rules/
bmf_ilp.rs
