problemreductions/models/specialized/
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::graph_types::SimpleGraph;
8use crate::traits::Problem;
9use crate::types::{EnergyMode, ProblemSize, SolutionSize};
10use serde::{Deserialize, Serialize};
11
12/// The Boolean Matrix Factorization problem.
13///
14/// Given an m×n boolean matrix A and rank k, find:
15/// - B: m×k boolean matrix
16/// - C: k×n boolean matrix
17///
18/// Such that the Hamming distance between A and B⊙C is minimized.
19///
20/// # Example
21///
22/// ```
23/// use problemreductions::models::specialized::BMF;
24/// use problemreductions::{Problem, Solver, BruteForce};
25///
26/// // 2x2 identity matrix
27/// let a = vec![
28///     vec![true, false],
29///     vec![false, true],
30/// ];
31/// let problem = BMF::new(a, 1);
32///
33/// let solver = BruteForce::new();
34/// let solutions = solver.find_best(&problem);
35///
36/// // Check the error
37/// for sol in &solutions {
38///     let error = problem.solution_size(sol).size;
39///     println!("Hamming error: {}", error);
40/// }
41/// ```
42#[derive(Debug, Clone, Serialize, Deserialize)]
43pub struct BMF {
44    /// The target matrix A (m×n).
45    matrix: Vec<Vec<bool>>,
46    /// Number of rows (m).
47    m: usize,
48    /// Number of columns (n).
49    n: usize,
50    /// Factorization rank.
51    k: usize,
52}
53
54impl BMF {
55    /// Create a new BMF problem.
56    ///
57    /// # Arguments
58    /// * `matrix` - The target m×n boolean matrix
59    /// * `k` - The factorization rank
60    pub fn new(matrix: Vec<Vec<bool>>, k: usize) -> Self {
61        let m = matrix.len();
62        let n = if m > 0 { matrix[0].len() } else { 0 };
63
64        // Validate matrix dimensions
65        for row in &matrix {
66            assert_eq!(row.len(), n, "All rows must have the same length");
67        }
68
69        Self { matrix, m, n, k }
70    }
71
72    /// Get the number of rows.
73    pub fn rows(&self) -> usize {
74        self.m
75    }
76
77    /// Get the number of columns.
78    pub fn cols(&self) -> usize {
79        self.n
80    }
81
82    /// Get the factorization rank.
83    pub fn rank(&self) -> usize {
84        self.k
85    }
86
87    /// Get the target matrix.
88    pub fn matrix(&self) -> &[Vec<bool>] {
89        &self.matrix
90    }
91
92    /// Extract matrices B and C from a configuration.
93    ///
94    /// Config layout: first m*k bits are B (row-major), next k*n bits are C (row-major).
95    pub fn extract_factors(&self, config: &[usize]) -> (Vec<Vec<bool>>, Vec<Vec<bool>>) {
96        let b_size = self.m * self.k;
97
98        // Extract B (m×k)
99        let b: Vec<Vec<bool>> = (0..self.m)
100            .map(|i| {
101                (0..self.k)
102                    .map(|j| config.get(i * self.k + j).copied().unwrap_or(0) == 1)
103                    .collect()
104            })
105            .collect();
106
107        // Extract C (k×n)
108        let c: Vec<Vec<bool>> = (0..self.k)
109            .map(|i| {
110                (0..self.n)
111                    .map(|j| config.get(b_size + i * self.n + j).copied().unwrap_or(0) == 1)
112                    .collect()
113            })
114            .collect();
115
116        (b, c)
117    }
118
119    /// Compute the boolean product B ⊙ C.
120    ///
121    /// `(B ⊙ C)[i,j] = OR_k (B[i,k] AND C[k,j])`
122    pub fn boolean_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
123        let m = b.len();
124        let n = if !c.is_empty() { c[0].len() } else { 0 };
125        let k = if !b.is_empty() { b[0].len() } else { 0 };
126
127        (0..m)
128            .map(|i| {
129                (0..n)
130                    .map(|j| (0..k).any(|kk| b[i][kk] && c[kk][j]))
131                    .collect()
132            })
133            .collect()
134    }
135
136    /// Compute the Hamming distance between the target and the product.
137    pub fn hamming_distance(&self, config: &[usize]) -> usize {
138        let (b, c) = self.extract_factors(config);
139        let product = Self::boolean_product(&b, &c);
140
141        self.matrix
142            .iter()
143            .zip(product.iter())
144            .map(|(a_row, p_row)| {
145                a_row
146                    .iter()
147                    .zip(p_row.iter())
148                    .filter(|(a, p)| a != p)
149                    .count()
150            })
151            .sum()
152    }
153
154    /// Check if the factorization is exact (Hamming distance = 0).
155    pub fn is_exact(&self, config: &[usize]) -> bool {
156        self.hamming_distance(config) == 0
157    }
158}
159
160impl Problem for BMF {
161    const NAME: &'static str = "BMF";
162    type GraphType = SimpleGraph;
163    type Weight = i32;
164    type Size = i32;
165
166    fn num_variables(&self) -> usize {
167        // B: m×k + C: k×n
168        self.m * self.k + self.k * self.n
169    }
170
171    fn num_flavors(&self) -> usize {
172        2 // Binary
173    }
174
175    fn problem_size(&self) -> ProblemSize {
176        ProblemSize::new(vec![
177            ("rows", self.m),
178            ("cols", self.n),
179            ("rank", self.k),
180        ])
181    }
182
183    fn energy_mode(&self) -> EnergyMode {
184        EnergyMode::SmallerSizeIsBetter // Minimize Hamming distance
185    }
186
187    fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
188        let distance = self.hamming_distance(config) as i32;
189        let is_valid = distance == 0; // Valid if exact factorization
190        SolutionSize::new(distance, is_valid)
191    }
192}
193
194/// Compute the boolean matrix product.
195pub fn boolean_matrix_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
196    BMF::boolean_product(b, c)
197}
198
199/// Compute the Hamming distance between two boolean matrices.
200pub fn matrix_hamming_distance(a: &[Vec<bool>], b: &[Vec<bool>]) -> usize {
201    a.iter()
202        .zip(b.iter())
203        .map(|(a_row, b_row)| {
204            a_row
205                .iter()
206                .zip(b_row.iter())
207                .filter(|(x, y)| x != y)
208                .count()
209        })
210        .sum()
211}
212
213#[cfg(test)]
214mod tests {
215    use super::*;
216    use crate::solvers::{BruteForce, Solver};
217
218    #[test]
219    fn test_bmf_creation() {
220        let matrix = vec![vec![true, false], vec![false, true]];
221        let problem = BMF::new(matrix, 2);
222        assert_eq!(problem.rows(), 2);
223        assert_eq!(problem.cols(), 2);
224        assert_eq!(problem.rank(), 2);
225        assert_eq!(problem.num_variables(), 8); // 2*2 + 2*2
226    }
227
228    #[test]
229    fn test_extract_factors() {
230        let matrix = vec![vec![true]];
231        let problem = BMF::new(matrix, 1);
232        // Config: [b00, c00] = [1, 1]
233        let (b, c) = problem.extract_factors(&[1, 1]);
234        assert_eq!(b, vec![vec![true]]);
235        assert_eq!(c, vec![vec![true]]);
236    }
237
238    #[test]
239    fn test_extract_factors_larger() {
240        // 2x2 matrix with rank 1
241        let matrix = vec![vec![true, true], vec![true, true]];
242        let problem = BMF::new(matrix, 1);
243        // B: 2x1, C: 1x2
244        // Config: [b00, b10, c00, c01] = [1, 1, 1, 1]
245        let (b, c) = problem.extract_factors(&[1, 1, 1, 1]);
246        assert_eq!(b, vec![vec![true], vec![true]]);
247        assert_eq!(c, vec![vec![true, true]]);
248    }
249
250    #[test]
251    fn test_boolean_product() {
252        // B = [[1], [1]], C = [[1, 1]]
253        // B ⊙ C = [[1,1], [1,1]]
254        let b = vec![vec![true], vec![true]];
255        let c = vec![vec![true, true]];
256        let product = BMF::boolean_product(&b, &c);
257        assert_eq!(
258            product,
259            vec![vec![true, true], vec![true, true]]
260        );
261    }
262
263    #[test]
264    fn test_boolean_product_rank2() {
265        // B = [[1,0], [0,1]], C = [[1,0], [0,1]]
266        // B ⊙ C = [[1,0], [0,1]] (identity)
267        let b = vec![vec![true, false], vec![false, true]];
268        let c = vec![vec![true, false], vec![false, true]];
269        let product = BMF::boolean_product(&b, &c);
270        assert_eq!(
271            product,
272            vec![vec![true, false], vec![false, true]]
273        );
274    }
275
276    #[test]
277    fn test_hamming_distance() {
278        // Target: [[1,0], [0,1]]
279        let matrix = vec![vec![true, false], vec![false, true]];
280        let problem = BMF::new(matrix, 2);
281
282        // B = [[1,0], [0,1]], C = [[1,0], [0,1]] -> exact match
283        // Config: [1,0,0,1, 1,0,0,1]
284        let config = vec![1, 0, 0, 1, 1, 0, 0, 1];
285        assert_eq!(problem.hamming_distance(&config), 0);
286
287        // All zeros -> product is all zeros, distance = 2
288        let config = vec![0, 0, 0, 0, 0, 0, 0, 0];
289        assert_eq!(problem.hamming_distance(&config), 2);
290    }
291
292    #[test]
293    fn test_solution_size() {
294        let matrix = vec![vec![true, false], vec![false, true]];
295        let problem = BMF::new(matrix, 2);
296
297        // Exact factorization
298        let config = vec![1, 0, 0, 1, 1, 0, 0, 1];
299        let sol = problem.solution_size(&config);
300        assert!(sol.is_valid);
301        assert_eq!(sol.size, 0);
302
303        // Non-exact
304        let config = vec![0, 0, 0, 0, 0, 0, 0, 0];
305        let sol = problem.solution_size(&config);
306        assert!(!sol.is_valid);
307        assert_eq!(sol.size, 2);
308    }
309
310    #[test]
311    fn test_brute_force_ones() {
312        // All ones matrix can be factored with rank 1
313        let matrix = vec![vec![true, true], vec![true, true]];
314        let problem = BMF::new(matrix, 1);
315        let solver = BruteForce::new();
316
317        let solutions = solver.find_best(&problem);
318        for sol in &solutions {
319            let sol_size = problem.solution_size(sol);
320            assert_eq!(sol_size.size, 0);
321            assert!(sol_size.is_valid);
322        }
323    }
324
325    #[test]
326    fn test_brute_force_identity() {
327        // Identity matrix needs rank 2
328        let matrix = vec![vec![true, false], vec![false, true]];
329        let problem = BMF::new(matrix, 2);
330        let solver = BruteForce::new();
331
332        let solutions = solver.find_best(&problem);
333        // Should find exact factorization
334        for sol in &solutions {
335            assert!(problem.is_exact(sol));
336        }
337    }
338
339    #[test]
340    fn test_brute_force_insufficient_rank() {
341        // Identity matrix with rank 1 cannot be exact
342        let matrix = vec![vec![true, false], vec![false, true]];
343        let problem = BMF::new(matrix, 1);
344        let solver = BruteForce::new().valid_only(false);
345
346        let solutions = solver.find_best(&problem);
347        // Best approximation has distance > 0
348        let best_distance = problem.hamming_distance(&solutions[0]);
349        // With rank 1, best we can do is distance 1 (all ones or all zeros except one)
350        assert!(best_distance >= 1);
351    }
352
353    #[test]
354    fn test_boolean_matrix_product_function() {
355        let b = vec![vec![true], vec![true]];
356        let c = vec![vec![true, true]];
357        let product = boolean_matrix_product(&b, &c);
358        assert_eq!(product, vec![vec![true, true], vec![true, true]]);
359    }
360
361    #[test]
362    fn test_matrix_hamming_distance_function() {
363        let a = vec![vec![true, false], vec![false, true]];
364        let b = vec![vec![true, true], vec![true, true]];
365        assert_eq!(matrix_hamming_distance(&a, &b), 2);
366
367        let c = vec![vec![true, false], vec![false, true]];
368        assert_eq!(matrix_hamming_distance(&a, &c), 0);
369    }
370
371    #[test]
372    fn test_energy_mode() {
373        let matrix = vec![vec![true]];
374        let problem = BMF::new(matrix, 1);
375        assert!(problem.energy_mode().is_minimization());
376    }
377
378    #[test]
379    fn test_problem_size() {
380        let matrix = vec![vec![true, false, true], vec![false, true, false]];
381        let problem = BMF::new(matrix, 2);
382        let size = problem.problem_size();
383        assert_eq!(size.get("rows"), Some(2));
384        assert_eq!(size.get("cols"), Some(3));
385        assert_eq!(size.get("rank"), Some(2));
386    }
387
388    #[test]
389    fn test_empty_matrix() {
390        let matrix: Vec<Vec<bool>> = vec![];
391        let problem = BMF::new(matrix, 1);
392        assert_eq!(problem.num_variables(), 0);
393        let sol = problem.solution_size(&[]);
394        assert!(sol.is_valid);
395        assert_eq!(sol.size, 0);
396    }
397
398    #[test]
399    fn test_is_exact() {
400        let matrix = vec![vec![true]];
401        let problem = BMF::new(matrix, 1);
402        assert!(problem.is_exact(&[1, 1]));
403        assert!(!problem.is_exact(&[0, 0]));
404    }
405}
problemreductions/models/specialized/bmf.rs

problemreductions/models/specialized/
bmf.rs
