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        module_path: module_path!(),
18        description: "Find sign assignment minimizing quadratic form over nonnegative integer matrix",
19        fields: &[
20            FieldInfo { name: "matrix", type_name: "Vec<Vec<i64>>", description: "n×n nonnegative integer matrix" },
21        ],
22    }
23}
24
25/// Minimum Matrix Cover.
26///
27/// Given an n×n nonnegative integer matrix A, find a function
28/// f: {1,...,n} → {-1,+1} that minimizes the quadratic form:
29///
30/// Σ_{i,j} a_ij · f(i) · f(j)
31///
32/// Each binary variable x_i ∈ {0,1} maps to a sign: f(i) = 2·x_i - 1
33/// (0 → -1, 1 → +1).
34///
35/// # Example
36///
37/// ```
38/// use problemreductions::models::algebraic::MinimumMatrixCover;
39/// use problemreductions::{Problem, Solver, BruteForce};
40///
41/// let problem = MinimumMatrixCover::new(vec![
42///     vec![0, 3, 1, 0],
43///     vec![3, 0, 0, 2],
44///     vec![1, 0, 0, 4],
45///     vec![0, 2, 4, 0],
46/// ]);
47///
48/// let solver = BruteForce::new();
49/// let witness = solver.find_witness(&problem);
50/// assert!(witness.is_some());
51/// ```
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct MinimumMatrixCover {
54    /// The n×n nonnegative integer matrix.
55    matrix: Vec<Vec<i64>>,
56}
57
58impl MinimumMatrixCover {
59    /// Create a new MinimumMatrixCover instance.
60    ///
61    /// # Panics
62    ///
63    /// Panics if the matrix is not square or has inconsistent row lengths.
64    pub fn new(matrix: Vec<Vec<i64>>) -> Self {
65        let n = matrix.len();
66        for (i, row) in matrix.iter().enumerate() {
67            assert_eq!(
68                row.len(),
69                n,
70                "Matrix must be square: row {i} has {} columns, expected {n}",
71                row.len()
72            );
73        }
74        Self { matrix }
75    }
76
77    /// Returns the number of rows (= columns) of the matrix.
78    pub fn num_rows(&self) -> usize {
79        self.matrix.len()
80    }
81
82    /// Returns a reference to the matrix.
83    pub fn matrix(&self) -> &[Vec<i64>] {
84        &self.matrix
85    }
86}
87
88impl Problem for MinimumMatrixCover {
89    const NAME: &'static str = "MinimumMatrixCover";
90    type Value = Min<i64>;
91
92    fn variant() -> Vec<(&'static str, &'static str)> {
93        crate::variant_params![]
94    }
95
96    fn dims(&self) -> Vec<usize> {
97        vec![2; self.num_rows()]
98    }
99
100    fn evaluate(&self, config: &[usize]) -> Min<i64> {
101        let n = self.num_rows();
102        if config.len() != n {
103            return Min(None);
104        }
105        if config.iter().any(|&v| v >= 2) {
106            return Min(None);
107        }
108
109        // Map config to signs: 0 → -1, 1 → +1
110        let signs: Vec<i64> = config.iter().map(|&x| 2 * x as i64 - 1).collect();
111
112        // Compute Σ_{i,j} a_ij * f(i) * f(j)
113        let mut value: i64 = 0;
114        for i in 0..n {
115            for j in 0..n {
116                value += self.matrix[i][j] * signs[i] * signs[j];
117            }
118        }
119
120        Min(Some(value))
121    }
122}
123
124crate::declare_variants! {
125    default MinimumMatrixCover => "2^num_rows",
126}
127
128#[cfg(feature = "example-db")]
129pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
130    // 4×4 symmetric matrix with zero diagonal
131    // Config [0,1,1,0] → f=(-1,+1,+1,-1) → value = -20
132    vec![crate::example_db::specs::ModelExampleSpec {
133        id: "minimum_matrix_cover",
134        instance: Box::new(MinimumMatrixCover::new(vec![
135            vec![0, 3, 1, 0],
136            vec![3, 0, 0, 2],
137            vec![1, 0, 0, 4],
138            vec![0, 2, 4, 0],
139        ])),
140        optimal_config: vec![0, 1, 1, 0],
141        optimal_value: serde_json::json!(-20),
142    }]
143}
144
145#[cfg(test)]
146#[path = "../../unit_tests/models/algebraic/minimum_matrix_cover.rs"]
147mod tests;
problemreductions/models/algebraic/minimum_matrix_cover.rs

problemreductions/models/algebraic/
minimum_matrix_cover.rs
