problemreductions/models/algebraic/
bmf.rs

1//! Boolean Matrix Factorization (BMF) problem implementation.
2//!
3//! Given a boolean matrix A, find matrices B and C such that
4//! the boolean product B * C approximates A.
5//! The boolean product `(B * C)[i,j] = OR_k (B[i,k] AND C[k,j])`.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::{OptimizationProblem, Problem};
9use crate::types::{Direction, SolutionSize};
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "BMF",
15        module_path: module_path!(),
16        description: "Boolean matrix factorization",
17        fields: &[
18            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "Target boolean matrix A" },
19            FieldInfo { name: "k", type_name: "usize", description: "Factorization rank" },
20        ],
21    }
22}
23
24/// The Boolean Matrix Factorization problem.
25///
26/// Given an m x n boolean matrix A and rank k, find:
27/// - B: m x k boolean matrix
28/// - C: k x n boolean matrix
29///
30/// Such that the Hamming distance between A and B*C is minimized.
31///
32/// # Example
33///
34/// ```
35/// use problemreductions::models::algebraic::BMF;
36/// use problemreductions::{Problem, Solver, BruteForce};
37///
38/// // 2x2 identity matrix
39/// let a = vec![
40///     vec![true, false],
41///     vec![false, true],
42/// ];
43/// let problem = BMF::new(a, 1);
44///
45/// let solver = BruteForce::new();
46/// let solutions = solver.find_all_best(&problem);
47///
48/// // Check the error
49/// for sol in &solutions {
50///     let error = problem.hamming_distance(sol);
51///     println!("Hamming error: {}", error);
52/// }
53/// ```
54#[derive(Debug, Clone, Serialize, Deserialize)]
55pub struct BMF {
56    /// The target matrix A (m x n).
57    matrix: Vec<Vec<bool>>,
58    /// Number of rows (m).
59    m: usize,
60    /// Number of columns (n).
61    n: usize,
62    /// Factorization rank.
63    k: usize,
64}
65
66impl BMF {
67    /// Create a new BMF problem.
68    ///
69    /// # Arguments
70    /// * `matrix` - The target m x n boolean matrix
71    /// * `k` - The factorization rank
72    pub fn new(matrix: Vec<Vec<bool>>, k: usize) -> Self {
73        let m = matrix.len();
74        let n = if m > 0 { matrix[0].len() } else { 0 };
75
76        // Validate matrix dimensions
77        for row in &matrix {
78            assert_eq!(row.len(), n, "All rows must have the same length");
79        }
80
81        Self { matrix, m, n, k }
82    }
83
84    /// Get the number of rows.
85    pub fn rows(&self) -> usize {
86        self.m
87    }
88
89    /// Get the number of columns.
90    pub fn cols(&self) -> usize {
91        self.n
92    }
93
94    /// Get the factorization rank.
95    pub fn rank(&self) -> usize {
96        self.k
97    }
98
99    /// Get the number of rows (alias for `rows()`).
100    pub fn m(&self) -> usize {
101        self.rows()
102    }
103
104    /// Get the number of columns (alias for `cols()`).
105    pub fn n(&self) -> usize {
106        self.cols()
107    }
108
109    /// Get the target matrix.
110    pub fn matrix(&self) -> &[Vec<bool>] {
111        &self.matrix
112    }
113
114    /// Extract matrices B and C from a configuration.
115    ///
116    /// Config layout: first m*k bits are B (row-major), next k*n bits are C (row-major).
117    pub fn extract_factors(&self, config: &[usize]) -> (Vec<Vec<bool>>, Vec<Vec<bool>>) {
118        let b_size = self.m * self.k;
119
120        // Extract B (m x k)
121        let b: Vec<Vec<bool>> = (0..self.m)
122            .map(|i| {
123                (0..self.k)
124                    .map(|j| config.get(i * self.k + j).copied().unwrap_or(0) == 1)
125                    .collect()
126            })
127            .collect();
128
129        // Extract C (k x n)
130        let c: Vec<Vec<bool>> = (0..self.k)
131            .map(|i| {
132                (0..self.n)
133                    .map(|j| config.get(b_size + i * self.n + j).copied().unwrap_or(0) == 1)
134                    .collect()
135            })
136            .collect();
137
138        (b, c)
139    }
140
141    /// Compute the boolean product B * C.
142    ///
143    /// `(B * C)[i,j] = OR_k (B[i,k] AND C[k,j])`
144    pub fn boolean_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
145        let m = b.len();
146        let n = if !c.is_empty() { c[0].len() } else { 0 };
147        let k = if !b.is_empty() { b[0].len() } else { 0 };
148
149        (0..m)
150            .map(|i| {
151                (0..n)
152                    .map(|j| (0..k).any(|kk| b[i][kk] && c[kk][j]))
153                    .collect()
154            })
155            .collect()
156    }
157
158    /// Compute the Hamming distance between the target and the product.
159    pub fn hamming_distance(&self, config: &[usize]) -> usize {
160        let (b, c) = self.extract_factors(config);
161        let product = Self::boolean_product(&b, &c);
162
163        self.matrix
164            .iter()
165            .zip(product.iter())
166            .map(|(a_row, p_row)| {
167                a_row
168                    .iter()
169                    .zip(p_row.iter())
170                    .filter(|(a, p)| a != p)
171                    .count()
172            })
173            .sum()
174    }
175
176    /// Check if the factorization is exact (Hamming distance = 0).
177    pub fn is_exact(&self, config: &[usize]) -> bool {
178        self.hamming_distance(config) == 0
179    }
180}
181
182/// Compute the boolean matrix product.
183#[cfg(test)]
184pub(crate) fn boolean_matrix_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
185    BMF::boolean_product(b, c)
186}
187
188/// Compute the Hamming distance between two boolean matrices.
189#[cfg(test)]
190pub(crate) fn matrix_hamming_distance(a: &[Vec<bool>], b: &[Vec<bool>]) -> usize {
191    a.iter()
192        .zip(b.iter())
193        .map(|(a_row, b_row)| {
194            a_row
195                .iter()
196                .zip(b_row.iter())
197                .filter(|(x, y)| x != y)
198                .count()
199        })
200        .sum()
201}
202
203impl Problem for BMF {
204    const NAME: &'static str = "BMF";
205    type Metric = SolutionSize<i32>;
206
207    fn dims(&self) -> Vec<usize> {
208        // B: m*k + C: k*n binary variables
209        vec![2; self.m * self.k + self.k * self.n]
210    }
211
212    fn evaluate(&self, config: &[usize]) -> SolutionSize<i32> {
213        // Minimize Hamming distance between A and B*C.
214        // All configurations are valid -- the distance is the objective.
215        SolutionSize::Valid(self.hamming_distance(config) as i32)
216    }
217
218    fn variant() -> Vec<(&'static str, &'static str)> {
219        crate::variant_params![]
220    }
221}
222
223impl OptimizationProblem for BMF {
224    type Value = i32;
225
226    fn direction(&self) -> Direction {
227        Direction::Minimize
228    }
229}
230
231crate::declare_variants! {
232    BMF => "2^(rows * rank + rank * cols)",
233}
234
235#[cfg(test)]
236#[path = "../../unit_tests/models/algebraic/bmf.rs"]
237mod tests;
problemreductions/models/algebraic/bmf.rs

problemreductions/models/algebraic/
bmf.rs
