problemreductions/models/algebraic/
minimum_matrix_cover.rs

1//! Minimum Matrix Cover problem implementation.
2//!
3//! Given an n×n nonnegative integer matrix A, find a sign assignment
4//! f: {1,...,n} → {-1,+1} minimizing Σ a_ij · f(i) · f(j).
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Min;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "MinimumMatrixCover",
14        display_name: "Minimum Matrix Cover",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Algebraic,
18        module_path: module_path!(),
19        description: "Find sign assignment minimizing quadratic form over nonnegative integer matrix",
20        fields: &[
21            FieldInfo { name: "matrix", type_name: "Vec<Vec<i64>>", description: "n×n nonnegative integer matrix" },
22        ],
23    }
24}
25
26/// Minimum Matrix Cover.
27///
28/// Given an n×n nonnegative integer matrix A, find a function
29/// f: {1,...,n} → {-1,+1} that minimizes the quadratic form:
30///
31/// Σ_{i,j} a_ij · f(i) · f(j)
32///
33/// Each binary variable x_i ∈ {0,1} maps to a sign: f(i) = 2·x_i - 1
34/// (0 → -1, 1 → +1).
35///
36/// # Example
37///
38/// ```
39/// use problemreductions::models::algebraic::MinimumMatrixCover;
40/// use problemreductions::{Problem, BruteForce};
41///
42/// let problem = MinimumMatrixCover::new(vec![
43///     vec![0, 3, 1, 0],
44///     vec![3, 0, 0, 2],
45///     vec![1, 0, 0, 4],
46///     vec![0, 2, 4, 0],
47/// ]);
48///
49/// let solver = BruteForce::new();
50/// let witness = solver.solve(&problem).unwrap();
51/// assert!(witness.is_some());
52/// ```
53#[derive(Debug, Clone, Serialize, Deserialize)]
54pub struct MinimumMatrixCover {
55    /// The n×n nonnegative integer matrix.
56    matrix: Vec<Vec<i64>>,
57}
58
59impl MinimumMatrixCover {
60    /// Create a new MinimumMatrixCover instance.
61    ///
62    /// # Panics
63    ///
64    /// Panics if the matrix is not square or has inconsistent row lengths.
65    pub fn new(matrix: Vec<Vec<i64>>) -> Self {
66        let n = matrix.len();
67        for (i, row) in matrix.iter().enumerate() {
68            assert_eq!(
69                row.len(),
70                n,
71                "Matrix must be square: row {i} has {} columns, expected {n}",
72                row.len()
73            );
74        }
75        Self { matrix }
76    }
77
78    /// Returns the number of rows (= columns) of the matrix.
79    pub fn num_rows(&self) -> usize {
80        self.matrix.len()
81    }
82
83    /// Returns a reference to the matrix.
84    pub fn matrix(&self) -> &[Vec<i64>] {
85        &self.matrix
86    }
87}
88
89impl Problem for MinimumMatrixCover {
90    const NAME: &'static str = "MinimumMatrixCover";
91    type Solution = Vec<bool>;
92    type Value = Min<i64>;
93
94    crate::problem_parameters![("num_rows", num_rows),];
95
96    fn variant() -> Vec<(&'static str, &'static str)> {
97        crate::variant_params![]
98    }
99
100    fn evaluate(
101        &self,
102        config: &Self::Solution,
103    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
104        Ok({
105            let n = self.num_rows();
106            if config.len() != n {
107                return Err(crate::traits::EvaluationError::InvalidConfiguration(
108                    "row-sign assignment length does not match the matrix".into(),
109                ));
110            }
111            // Map config to signs: 0 → -1, 1 → +1
112            let signs: Vec<i64> = config
113                .iter()
114                .map(|&value| if value { 1 } else { -1 })
115                .collect();
116
117            // Compute Σ_{i,j} a_ij * f(i) * f(j)
118            let mut value: i64 = 0;
119            for i in 0..n {
120                for j in 0..n {
121                    let term = self.matrix[i][j]
122                        .checked_mul(signs[i])
123                        .and_then(|term| term.checked_mul(signs[j]))
124                        .ok_or_else(|| {
125                            crate::traits::EvaluationError::IntegerOverflow(
126                                "multiplying matrix-cover objective term".into(),
127                            )
128                        })?;
129                    value = value.checked_add(term).ok_or_else(|| {
130                        crate::traits::EvaluationError::IntegerOverflow(
131                            "summing matrix-cover objective".into(),
132                        )
133                    })?;
134                }
135            }
136
137            Min(Some(value))
138        })
139    }
140}
141
142impl crate::solvers::BruteForceProblem for MinimumMatrixCover {
143    fn dimensions(&self) -> Vec<usize> {
144        vec![2; self.num_rows()]
145    }
146}
147
148crate::declare_variants! {
149    default MinimumMatrixCover => "2^num_rows",
150}
151
152crate::register_brute_force! {
153    MinimumMatrixCover decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
154}
155
156#[cfg(feature = "example-db")]
157pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
158    // 4×4 symmetric matrix with zero diagonal
159    // Config [0,1,1,0] → f=(-1,+1,+1,-1) → value = -20
160    vec![crate::example_db::specs::ModelExampleSpec {
161        id: "minimum_matrix_cover",
162        instance: Box::new(MinimumMatrixCover::new(vec![
163            vec![0, 3, 1, 0],
164            vec![3, 0, 0, 2],
165            vec![1, 0, 0, 4],
166            vec![0, 2, 4, 0],
167        ])),
168        optimal_config: serde_json::json!(vec![false, true, true, false]),
169        optimal_value: serde_json::json!(-20),
170    }]
171}
172
173#[cfg(test)]
174#[path = "../../unit_tests/models/algebraic/minimum_matrix_cover.rs"]
175mod tests;
problemreductions/models/algebraic/minimum_matrix_cover.rs

problemreductions/models/algebraic/
minimum_matrix_cover.rs
