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)]
57pub struct BMF {
58    /// The target matrix A (m x n).
59    matrix: Vec<Vec<bool>>,
60    /// Number of rows (m).
61    m: usize,
62    /// Number of columns (n).
63    n: usize,
64    /// Factorization rank.
65    k: usize,
66}
67
68impl BMF {
69    /// Create a new BMF problem.
70    ///
71    /// # Arguments
72    /// * `matrix` - The target m x n boolean matrix
73    /// * `k` - The factorization rank
74    pub fn new(matrix: Vec<Vec<bool>>, k: usize) -> Self {
75        let m = matrix.len();
76        let n = if m > 0 { matrix[0].len() } else { 0 };
77
78        // Validate matrix dimensions
79        for row in &matrix {
80            assert_eq!(row.len(), n, "All rows must have the same length");
81        }
82
83        Self { matrix, m, n, k }
84    }
85
86    /// Get the number of rows.
87    pub fn rows(&self) -> usize {
88        self.m
89    }
90
91    /// Get the number of columns.
92    pub fn cols(&self) -> usize {
93        self.n
94    }
95
96    /// Get the factorization rank.
97    pub fn rank(&self) -> usize {
98        self.k
99    }
100
101    /// Get the number of rows (alias for `rows()`).
102    pub fn m(&self) -> usize {
103        self.rows()
104    }
105
106    /// Get the number of columns (alias for `cols()`).
107    pub fn n(&self) -> usize {
108        self.cols()
109    }
110
111    /// Get the target matrix.
112    pub fn matrix(&self) -> &[Vec<bool>] {
113        &self.matrix
114    }
115
116    /// Return the two factor matrices represented by a solution.
117    pub fn extract_factors(
118        &self,
119        solution: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
120    ) -> (Vec<Vec<bool>>, Vec<Vec<bool>>) {
121        solution.clone()
122    }
123
124    /// Compute the boolean product B * C.
125    ///
126    /// `(B * C)[i,j] = OR_k (B[i,k] AND C[k,j])`
127    pub fn boolean_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
128        let m = b.len();
129        let n = if !c.is_empty() { c[0].len() } else { 0 };
130        let k = if !b.is_empty() { b[0].len() } else { 0 };
131
132        (0..m)
133            .map(|i| {
134                (0..n)
135                    .map(|j| (0..k).any(|kk| b[i][kk] && c[kk][j]))
136                    .collect()
137            })
138            .collect()
139    }
140
141    /// Compute the Hamming distance between the target and the product.
142    pub fn hamming_distance(
143        &self,
144        solution: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
145    ) -> Result<i64, crate::traits::EvaluationError> {
146        let (b, c) = solution;
147
148        let distance = (0..self.m)
149            .map(|i| {
150                (0..self.n)
151                    .filter(|&j| {
152                        let product_entry = (0..self.k).any(|r| b[i][r] && c[r][j]);
153                        self.matrix[i][j] != product_entry
154                    })
155                    .count()
156            })
157            .sum::<usize>();
158        i64::try_from(distance).map_err(|_| {
159            crate::traits::EvaluationError::IntegerOverflow(
160                "converting Boolean-matrix Hamming distance to i64".into(),
161            )
162        })
163    }
164
165    /// Check if the factorization is exact (Hamming distance = 0).
166    pub fn is_exact(
167        &self,
168        solution: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
169    ) -> Result<bool, crate::traits::EvaluationError> {
170        Ok(self.hamming_distance(solution)? == 0)
171    }
172
173    /// Total number of 1s in B and C (the factor size to be minimized when exact).
174    pub fn total_factor_size(
175        &self,
176        solution: &(Vec<Vec<bool>>, Vec<Vec<bool>>),
177    ) -> Result<i64, crate::traits::EvaluationError> {
178        let (left, right) = solution;
179        let size = left
180            .iter()
181            .chain(right)
182            .flatten()
183            .filter(|&&value| value)
184            .count();
185        i64::try_from(size).map_err(|_| {
186            crate::traits::EvaluationError::IntegerOverflow(
187                "converting Boolean factor size to i64".into(),
188            )
189        })
190    }
191}
192
193/// Compute the boolean matrix product.
194#[cfg(test)]
195pub(crate) 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.
200#[cfg(test)]
201pub(crate) fn matrix_hamming_distance(a: &[Vec<bool>], b: &[Vec<bool>]) -> usize {
202    a.iter()
203        .zip(b.iter())
204        .map(|(a_row, b_row)| {
205            a_row
206                .iter()
207                .zip(b_row.iter())
208                .filter(|(x, y)| x != y)
209                .count()
210        })
211        .sum()
212}
213
214impl Problem for BMF {
215    const NAME: &'static str = "BMF";
216    type Solution = (Vec<Vec<bool>>, Vec<Vec<bool>>);
217    type Value = Min<i64>;
218
219    crate::problem_parameters![("cols", cols), ("rank", rank), ("rows", rows),];
220
221    fn evaluate(
222        &self,
223        solution: &Self::Solution,
224    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
225        let (left, right) = solution;
226        if left.len() != self.m
227            || left.iter().any(|row| row.len() != self.k)
228            || right.len() != self.k
229            || right.iter().any(|row| row.len() != self.n)
230        {
231            return Err(crate::traits::EvaluationError::InvalidConfiguration(
232                "BMF factor dimensions do not match the instance".into(),
233            ));
234        }
235        Ok({
236            // Feasible iff B*C = A exactly; objective is total factor size (|B| + |C| in 1s).
237            if self.hamming_distance(solution)? != 0 {
238                return Ok(Min(None));
239            }
240            Min(Some(self.total_factor_size(solution)?))
241        })
242    }
243
244    fn variant() -> Vec<(&'static str, &'static str)> {
245        crate::variant_params![]
246    }
247}
248
249impl crate::solvers::BruteForceProblem for BMF {
250    fn dimensions(&self) -> Vec<usize> {
251        // B: m*k + C: k*n binary variables
252        vec![2; self.m * self.k + self.k * self.n]
253    }
254}
255
256crate::declare_variants! {
257    default BMF => "2^(rows * rank + rank * cols)",
258}
259
260crate::register_brute_force! {
261    BMF decode |problem: &BMF, indices: Vec<usize>| {
262        let split = problem.rows() * problem.rank();
263        (
264            indices[..split].chunks(problem.rank()).map(crate::config::config_to_bits).collect(),
265            indices[split..].chunks(problem.cols()).map(crate::config::config_to_bits).collect(),
266        )
267    },
268}
269
270#[cfg(feature = "example-db")]
271pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
272    vec![crate::example_db::specs::ModelExampleSpec {
273        id: "bmf",
274        instance: Box::new(BMF::new(
275            vec![
276                vec![true, true, false],
277                vec![true, true, true],
278                vec![false, true, true],
279            ],
280            2,
281        )),
282        // B = [[1,0],[1,1],[0,1]], C = [[1,1,0],[0,1,1]].
283        // Total 1s: 4 in B + 4 in C = 8, and B * C = A exactly.
284        optimal_config: serde_json::json!((
285            vec![vec![true, false], vec![true, true], vec![false, true]],
286            vec![vec![true, true, false], vec![false, true, true]]
287        )),
288        optimal_value: serde_json::json!(8),
289    }]
290}
291
292#[cfg(test)]
293#[path = "../../unit_tests/models/algebraic/bmf.rs"]
294mod tests;
problemreductions/models/algebraic/bmf.rs

problemreductions/models/algebraic/
bmf.rs
