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        category: crate::registry::ProblemCategory::Algebraic,
21        module_path: module_path!(),
22        description: "Boolean matrix factorization",
23        fields: &[
24            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "Target boolean matrix A" },
25            FieldInfo { name: "k", type_name: "usize", description: "Factorization rank" },
26        ],
27    }
28}
29
30/// The Boolean Matrix Factorization problem.
31///
32/// Given an m x n boolean matrix A and rank k, find:
33/// - B: m x k boolean matrix
34/// - C: k x n boolean matrix
35///
36/// Such that `B * C = A` exactly, minimizing the total number of 1s in B and C.
37/// Configurations that do not yield an exact factorization are infeasible.
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::algebraic::BMF;
43/// use problemreductions::{Problem, BruteForce};
44///
45/// // 2x2 identity matrix — boolean rank 2
46/// let a = vec![
47///     vec![true, false],
48///     vec![false, true],
49/// ];
50/// let problem = BMF::new(a, 2);
51///
52/// let solver = BruteForce::new();
53/// let witness = solver.solve(&problem).unwrap().unwrap();
54/// assert!(problem.is_exact(&witness).unwrap());
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57#[serde(try_from = "BMFData")]
58pub struct BMF {
59    /// The target matrix A (m x n).
60    matrix: Vec<Vec<bool>>,
61    /// Number of rows (m).
62    m: usize,
63    /// Number of columns (n).
64    n: usize,
65    /// Factorization rank.
66    k: usize,
67}
68
69#[derive(Deserialize)]
70struct BMFData {
71    matrix: Vec<Vec<bool>>,
72    k: usize,
73}
74
75impl TryFrom<BMFData> for BMF {
76    type Error = crate::registry::ConstructionError;
77
78    fn try_from(data: BMFData) -> Result<Self, Self::Error> {
79        Self::try_new(data.matrix, data.k)
80    }
81}
82
83impl BMF {
84    /// Create a new BMF problem.
85    ///
86    /// # Arguments
87    /// * `matrix` - The target m x n boolean matrix
88    /// * `k` - The factorization rank
89    pub fn new(matrix: Vec<Vec<bool>>, k: usize) -> Self {
90        Self::try_new(matrix, k).unwrap_or_else(|error| panic!("{error}"))
91    }
92
93    fn try_new(
94        matrix: Vec<Vec<bool>>,
95        k: usize,
96    ) -> Result<Self, crate::registry::ConstructionError> {
97        let m = matrix.len();
98        let n = matrix.first().map_or(0, Vec::len);
99        if matrix.iter().any(|row| row.len() != n) {
100            return Err("all matrix rows must have the same length".into());
101        }
102        Ok(Self { matrix, m, n, k })
103    }
104
105    /// Get the number of rows.
106    pub fn rows(&self) -> usize {
107        self.m
108    }
109
110    /// Get the number of columns.
111    pub fn cols(&self) -> usize {
112        self.n
113    }
114
115    /// Get the factorization rank.
116    pub fn rank(&self) -> usize {
117        self.k
118    }
119
120    /// Get the number of rows (alias for `rows()`).
121    pub fn m(&self) -> usize {
122        self.rows()
123    }
124
125    /// Get the number of columns (alias for `cols()`).
126    pub fn n(&self) -> usize {
127        self.cols()
128    }
129
130    /// Get the target matrix.
131    pub fn matrix(&self) -> &[Vec<bool>] {
132        &self.matrix
133    }
134
135    /// Return the two factor matrices represented by a solution.
136    pub fn extract_factors(
137        &self,
138        solution: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
139    ) -> (Vec<Vec<bool>>, Vec<Vec<bool>>) {
140        solution.clone()
141    }
142
143    /// Compute the boolean product B * C.
144    ///
145    /// `(B * C)[i,j] = OR_k (B[i,k] AND C[k,j])`
146    pub fn boolean_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
147        let m = b.len();
148        let n = if !c.is_empty() { c[0].len() } else { 0 };
149        let k = if !b.is_empty() { b[0].len() } else { 0 };
150
151        (0..m)
152            .map(|i| {
153                (0..n)
154                    .map(|j| (0..k).any(|kk| b[i][kk] && c[kk][j]))
155                    .collect()
156            })
157            .collect()
158    }
159
160    /// Compute the Hamming distance between the target and the product.
161    pub fn hamming_distance(
162        &self,
163        solution: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
164    ) -> Result<i64, crate::traits::EvaluationError> {
165        let (b, c) = solution;
166
167        let distance = (0..self.m)
168            .map(|i| {
169                (0..self.n)
170                    .filter(|&j| {
171                        let product_entry = (0..self.k).any(|r| b[i][r] && c[r][j]);
172                        self.matrix[i][j] != product_entry
173                    })
174                    .count()
175            })
176            .sum::<usize>();
177        i64::try_from(distance).map_err(|_| {
178            crate::traits::EvaluationError::IntegerOverflow(
179                "converting Boolean-matrix Hamming distance to i64".into(),
180            )
181        })
182    }
183
184    /// Check if the factorization is exact (Hamming distance = 0).
185    pub fn is_exact(
186        &self,
187        solution: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
188    ) -> Result<bool, crate::traits::EvaluationError> {
189        Ok(self.hamming_distance(solution)? == 0)
190    }
191
192    /// Total number of 1s in B and C (the factor size to be minimized when exact).
193    pub fn total_factor_size(
194        &self,
195        solution: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
196    ) -> Result<i64, crate::traits::EvaluationError> {
197        let (left, right) = solution;
198        let size = left
199            .iter()
200            .chain(right)
201            .flatten()
202            .filter(|&&value| value)
203            .count();
204        i64::try_from(size).map_err(|_| {
205            crate::traits::EvaluationError::IntegerOverflow(
206                "converting Boolean factor size to i64".into(),
207            )
208        })
209    }
210}
211
212/// Compute the boolean matrix product.
213#[cfg(test)]
214pub(crate) fn boolean_matrix_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
215    BMF::boolean_product(b, c)
216}
217
218/// Compute the Hamming distance between two boolean matrices.
219#[cfg(test)]
220pub(crate) fn matrix_hamming_distance(a: &[Vec<bool>], b: &[Vec<bool>]) -> usize {
221    a.iter()
222        .zip(b.iter())
223        .map(|(a_row, b_row)| {
224            a_row
225                .iter()
226                .zip(b_row.iter())
227                .filter(|(x, y)| x != y)
228                .count()
229        })
230        .sum()
231}
232
233impl Problem for BMF {
234    const NAME: &'static str = "BMF";
235    type Solution = (Vec<Vec<bool>>, Vec<Vec<bool>>);
236    type Value = Min<i64>;
237
238    crate::problem_parameters![("cols", cols), ("rank", rank), ("rows", rows),];
239
240    fn evaluate(
241        &self,
242        solution: &Self::Solution,
243    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
244        let (left, right) = solution;
245        if left.len() != self.m
246            || left.iter().any(|row| row.len() != self.k)
247            || right.len() != self.k
248            || right.iter().any(|row| row.len() != self.n)
249        {
250            return Err(crate::traits::EvaluationError::InvalidConfiguration(
251                "BMF factor dimensions do not match the instance".into(),
252            ));
253        }
254        Ok({
255            // Feasible iff B*C = A exactly; objective is total factor size (|B| + |C| in 1s).
256            if self.hamming_distance(solution)? != 0 {
257                return Ok(Min(None));
258            }
259            Min(Some(self.total_factor_size(solution)?))
260        })
261    }
262
263    fn variant() -> Vec<(&'static str, &'static str)> {
264        crate::variant_params![]
265    }
266}
267
268impl crate::solvers::BruteForceProblem for BMF {
269    fn dimensions(&self) -> Vec<usize> {
270        // B: m*k + C: k*n binary variables
271        vec![2; self.m * self.k + self.k * self.n]
272    }
273}
274
275crate::declare_variants! {
276    default BMF => "2^(rows * rank + rank * cols)",
277}
278
279crate::register_brute_force! {
280    BMF decode |problem: &BMF, indices: Vec<usize>| {
281        let split = problem.rows() * problem.rank();
282        (
283            indices[..split].chunks(problem.rank()).map(crate::config::config_to_bits).collect(),
284            indices[split..].chunks(problem.cols()).map(crate::config::config_to_bits).collect(),
285        )
286    },
287}
288
289#[cfg(feature = "example-db")]
290pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
291    vec![crate::example_db::specs::ModelExampleSpec {
292        id: "bmf",
293        instance: Box::new(BMF::new(
294            vec![
295                vec![true, true, false],
296                vec![true, true, true],
297                vec![false, true, true],
298            ],
299            2,
300        )),
301        // B = [[1,0],[1,1],[0,1]], C = [[1,1,0],[0,1,1]].
302        // Total 1s: 4 in B + 4 in C = 8, and B * C = A exactly.
303        optimal_config: serde_json::json!((
304            vec![vec![true, false], vec![true, true], vec![false, true]],
305            vec![vec![true, true, false], vec![false, true, true]]
306        )),
307        optimal_value: serde_json::json!(8),
308    }]
309}
310
311#[cfg(test)]
312#[path = "../../unit_tests/models/algebraic/bmf.rs"]
313mod tests;
problemreductions/models/algebraic/bmf.rs

problemreductions/models/algebraic/
bmf.rs
