problemreductions/models/algebraic/
bmf.rs

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

problemreductions/models/algebraic/
bmf.rs
