bmf.rs

//! Boolean Matrix Factorization (BMF) problem implementation.
//!
//! Given a boolean matrix A and rank k, find boolean matrices B (m x k)
//! and C (k x n) such that the boolean product B * C equals A exactly,
//! minimizing the total number of 1s in B and C. Configs that do not
//! produce an exact factorization evaluate to `Min(None)` (infeasible).
//! The boolean product `(B * C)[i,j] = OR_r (B[i,r] AND C[r,j])`.

use crate::registry::{FieldInfo, ProblemSchemaEntry};
use crate::traits::Problem;
use crate::types::Min;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "BMF",
        display_name: "BMF",
        aliases: &[],
        dimensions: &[],
        module_path: module_path!(),
        description: "Boolean matrix factorization",
        fields: &[
            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "Target boolean matrix A" },
            FieldInfo { name: "k", type_name: "usize", description: "Factorization rank" },
        ],
    }
}

/// The Boolean Matrix Factorization problem.
///
/// Given an m x n boolean matrix A and rank k, find:
/// - B: m x k boolean matrix
/// - C: k x n boolean matrix
///
/// Such that `B * C = A` exactly, minimizing the total number of 1s in B and C.
/// Configurations that do not yield an exact factorization are infeasible.
///
/// # Example
///
/// ```
/// use problemreductions::models::algebraic::BMF;
/// use problemreductions::{Problem, Solver, BruteForce};
///
/// // 2x2 identity matrix — boolean rank 2
/// let a = vec![
///     vec![true, false],
///     vec![false, true],
/// ];
/// let problem = BMF::new(a, 2);
///
/// let solver = BruteForce::new();
/// let witness = solver.find_witness(&problem).unwrap();
/// assert!(problem.is_exact(&witness));
/// ```
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct BMF {
    /// The target matrix A (m x n).
    matrix: Vec<Vec<bool>>,
    /// Number of rows (m).
    m: usize,
    /// Number of columns (n).
    n: usize,
    /// Factorization rank.
    k: usize,
}

impl BMF {
    /// Create a new BMF problem.
    ///
    /// # Arguments
    /// * `matrix` - The target m x n boolean matrix
    /// * `k` - The factorization rank
    pub fn new(matrix: Vec<Vec<bool>>, k: usize) -> Self {
        let m = matrix.len();
        let n = if m > 0 { matrix[0].len() } else { 0 };

        // Validate matrix dimensions
        for row in &matrix {
            assert_eq!(row.len(), n, "All rows must have the same length");
        }

        Self { matrix, m, n, k }
    }

    /// Get the number of rows.
    pub fn rows(&self) -> usize {
        self.m
    }

    /// Get the number of columns.
    pub fn cols(&self) -> usize {
        self.n
    }

    /// Get the factorization rank.
    pub fn rank(&self) -> usize {
        self.k
    }

    /// Get the number of rows (alias for `rows()`).
    pub fn m(&self) -> usize {
        self.rows()
    }

    /// Get the number of columns (alias for `cols()`).
    pub fn n(&self) -> usize {
        self.cols()
    }

    /// Get the target matrix.
    pub fn matrix(&self) -> &[Vec<bool>] {
        &self.matrix
    }

    /// Extract matrices B and C from a configuration.
    ///
    /// Config layout: first m*k bits are B (row-major), next k*n bits are C (row-major).
    pub fn extract_factors(&self, config: &[usize]) -> (Vec<Vec<bool>>, Vec<Vec<bool>>) {
        let b_size = self.m * self.k;

        // Extract B (m x k)
        let b: Vec<Vec<bool>> = (0..self.m)
            .map(|i| {
                (0..self.k)
                    .map(|j| config.get(i * self.k + j).copied().unwrap_or(0) == 1)
                    .collect()
            })
            .collect();

        // Extract C (k x n)
        let c: Vec<Vec<bool>> = (0..self.k)
            .map(|i| {
                (0..self.n)
                    .map(|j| config.get(b_size + i * self.n + j).copied().unwrap_or(0) == 1)
                    .collect()
            })
            .collect();

        (b, c)
    }

    /// Compute the boolean product B * C.
    ///
    /// `(B * C)[i,j] = OR_k (B[i,k] AND C[k,j])`
    pub fn boolean_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
        let m = b.len();
        let n = if !c.is_empty() { c[0].len() } else { 0 };
        let k = if !b.is_empty() { b[0].len() } else { 0 };

        (0..m)
            .map(|i| {
                (0..n)
                    .map(|j| (0..k).any(|kk| b[i][kk] && c[kk][j]))
                    .collect()
            })
            .collect()
    }

    /// Compute the Hamming distance between the target and the product.
    pub fn hamming_distance(&self, config: &[usize]) -> usize {
        let (b, c) = self.extract_factors(config);

        (0..self.m)
            .map(|i| {
                (0..self.n)
                    .filter(|&j| {
                        let product_entry = (0..self.k).any(|r| b[i][r] && c[r][j]);
                        self.matrix[i][j] != product_entry
                    })
                    .count()
            })
            .sum()
    }

    /// Check if the factorization is exact (Hamming distance = 0).
    pub fn is_exact(&self, config: &[usize]) -> bool {
        self.hamming_distance(config) == 0
    }

    /// Total number of 1s in B and C (the factor size to be minimized when exact).
    pub fn total_factor_size(&self, config: &[usize]) -> usize {
        config.iter().filter(|&&x| x == 1).count()
    }
}

/// Compute the boolean matrix product.
#[cfg(test)]
pub(crate) fn boolean_matrix_product(b: &[Vec<bool>], c: &[Vec<bool>]) -> Vec<Vec<bool>> {
    BMF::boolean_product(b, c)
}

/// Compute the Hamming distance between two boolean matrices.
#[cfg(test)]
pub(crate) fn matrix_hamming_distance(a: &[Vec<bool>], b: &[Vec<bool>]) -> usize {
    a.iter()
        .zip(b.iter())
        .map(|(a_row, b_row)| {
            a_row
                .iter()
                .zip(b_row.iter())
                .filter(|(x, y)| x != y)
                .count()
        })
        .sum()
}

impl Problem for BMF {
    const NAME: &'static str = "BMF";
    type Value = Min<i32>;

    fn dims(&self) -> Vec<usize> {
        // B: m*k + C: k*n binary variables
        vec![2; self.m * self.k + self.k * self.n]
    }

    fn evaluate(&self, config: &[usize]) -> Min<i32> {
        // Feasible iff B*C = A exactly; objective is total factor size (|B| + |C| in 1s).
        if self.hamming_distance(config) != 0 {
            return Min(None);
        }
        Min(Some(self.total_factor_size(config) as i32))
    }

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![]
    }
}

crate::declare_variants! {
    default BMF => "2^(rows * rank + rank * cols)",
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "bmf",
        instance: Box::new(BMF::new(
            vec![
                vec![true, true, false],
                vec![true, true, true],
                vec![false, true, true],
            ],
            2,
        )),
        // 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).
        // Total 1s: 4 in B + 4 in C = 8, and B * C = A exactly.
        optimal_config: vec![1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1],
        optimal_value: serde_json::json!(8),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/algebraic/bmf.rs"]
mod tests;