problemreductions/models/algebraic/
minimum_matrix_domination.rs

1//! Minimum Matrix Domination problem implementation.
2//!
3//! Given an n×n binary matrix M, find a minimum subset C of 1-entries such that
4//! every 1-entry not in C shares a row or column with some entry in C.
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: "MinimumMatrixDomination",
14        display_name: "Minimum Matrix Domination",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Algebraic,
18        module_path: module_path!(),
19        description: "Find minimum subset of 1-entries in a binary matrix that dominates all other 1-entries by shared row or column",
20        fields: &[
21            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "n×n binary matrix M" },
22        ],
23    }
24}
25
26/// Minimum Matrix Domination.
27///
28/// Given an n×n binary matrix M, find a minimum-cardinality subset C of
29/// 1-entries such that every 1-entry not in C shares a row or column with
30/// some entry in C.
31///
32/// # Representation
33///
34/// Each 1-entry in the matrix is a binary variable: `x_k = 1` if the k-th
35/// 1-entry is selected into C. The 1-entries are enumerated in row-major
36/// order.
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::algebraic::MinimumMatrixDomination;
42/// use problemreductions::{Problem, BruteForce};
43///
44/// // 3×3 identity matrix: 3 ones on the diagonal, no shared rows/cols
45/// let matrix = vec![
46///     vec![true, false, false],
47///     vec![false, true, false],
48///     vec![false, false, true],
49/// ];
50/// let problem = MinimumMatrixDomination::new(matrix);
51/// let solver = BruteForce::new();
52/// let witness = solver.solve(&problem).unwrap();
53/// // All 3 diagonal entries must be selected (no domination possible)
54/// assert_eq!(witness, Some(vec![true, true, true]));
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct MinimumMatrixDomination {
58    /// The binary matrix.
59    matrix: Vec<Vec<bool>>,
60    /// Positions of 1-entries in row-major order: (row, col).
61    ones: Vec<(usize, usize)>,
62}
63
64impl MinimumMatrixDomination {
65    /// Create a new MinimumMatrixDomination instance.
66    ///
67    /// # Panics
68    ///
69    /// Panics if the matrix rows have inconsistent lengths.
70    pub fn new(matrix: Vec<Vec<bool>>) -> Self {
71        let num_cols = matrix.first().map_or(0, Vec::len);
72        for row in &matrix {
73            assert_eq!(row.len(), num_cols, "All rows must have the same length");
74        }
75        let ones: Vec<(usize, usize)> = matrix
76            .iter()
77            .enumerate()
78            .flat_map(|(i, row)| {
79                row.iter()
80                    .enumerate()
81                    .filter(|(_, &v)| v)
82                    .map(move |(j, _)| (i, j))
83            })
84            .collect();
85        Self { matrix, ones }
86    }
87
88    /// Returns a reference to the binary matrix.
89    pub fn matrix(&self) -> &[Vec<bool>] {
90        &self.matrix
91    }
92
93    /// Returns the positions of 1-entries in row-major order.
94    pub fn ones(&self) -> &[(usize, usize)] {
95        &self.ones
96    }
97
98    /// Returns the number of rows in the matrix.
99    pub fn num_rows(&self) -> usize {
100        self.matrix.len()
101    }
102
103    /// Returns the number of columns in the matrix.
104    pub fn num_cols(&self) -> usize {
105        self.matrix.first().map_or(0, Vec::len)
106    }
107
108    /// Returns the number of 1-entries in the matrix.
109    pub fn num_ones(&self) -> usize {
110        self.ones.len()
111    }
112}
113
114impl Problem for MinimumMatrixDomination {
115    const NAME: &'static str = "MinimumMatrixDomination";
116    type Solution = Vec<bool>;
117    type Value = Min<i64>;
118
119    crate::problem_parameters![
120        ("num_cols", num_cols),
121        ("num_ones", num_ones),
122        ("num_rows", num_rows),
123    ];
124
125    fn variant() -> Vec<(&'static str, &'static str)> {
126        crate::variant_params![]
127    }
128
129    fn evaluate(
130        &self,
131        config: &Self::Solution,
132    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
133        Ok({
134            if config.len() != self.num_ones() {
135                return Err(crate::traits::EvaluationError::InvalidConfiguration(
136                    "selected-entry vector length does not match the matrix".into(),
137                ));
138            }
139            // Collect the set of selected 1-entry indices
140            let selected: Vec<usize> = config
141                .iter()
142                .enumerate()
143                .filter(|(_, &v)| v)
144                .map(|(i, _)| i)
145                .collect();
146
147            // Build sets of rows and columns covered by selected entries
148            let mut covered_rows = std::collections::HashSet::new();
149            let mut covered_cols = std::collections::HashSet::new();
150            for &idx in &selected {
151                let (r, c) = self.ones[idx];
152                covered_rows.insert(r);
153                covered_cols.insert(c);
154            }
155
156            // Check domination: every unselected 1-entry must share a row or
157            // column with some selected entry
158            for (k, &(r, c)) in self.ones.iter().enumerate() {
159                if config[k] {
160                    continue; // selected entries don't need domination
161                }
162                if !covered_rows.contains(&r) && !covered_cols.contains(&c) {
163                    return Ok(Min(None)); // not dominated
164                }
165            }
166
167            Min(Some(i64::try_from(selected.len()).map_err(|_| {
168                crate::traits::EvaluationError::IntegerOverflow(
169                    "converting matrix-domination cardinality to i64".into(),
170                )
171            })?))
172        })
173    }
174}
175
176impl crate::solvers::BruteForceProblem for MinimumMatrixDomination {
177    fn dimensions(&self) -> Vec<usize> {
178        vec![2; self.num_ones()]
179    }
180}
181
182crate::declare_variants! {
183    default MinimumMatrixDomination => "2^num_ones",
184}
185
186crate::register_brute_force! {
187    MinimumMatrixDomination decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
188}
189
190#[cfg(feature = "example-db")]
191pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
192    // P6 adjacency matrix (6×6, 10 ones)
193    // 1-entries: (0,1),(1,0),(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4)
194    // Optimal: select indices 0,1,7,6 -> C = {(0,1),(1,0),(4,3),(3,4)}, value = 4
195    let matrix = vec![
196        vec![false, true, false, false, false, false],
197        vec![true, false, true, false, false, false],
198        vec![false, true, false, true, false, false],
199        vec![false, false, true, false, true, false],
200        vec![false, false, false, true, false, true],
201        vec![false, false, false, false, true, false],
202    ];
203    vec![crate::example_db::specs::ModelExampleSpec {
204        id: "minimum_matrix_domination",
205        instance: Box::new(MinimumMatrixDomination::new(matrix)),
206        optimal_config: serde_json::json!(vec![
207            true, true, false, false, false, false, true, true, false, false
208        ]),
209        optimal_value: serde_json::json!(4),
210    }]
211}
212
213#[cfg(test)]
214#[path = "../../unit_tests/models/algebraic/minimum_matrix_domination.rs"]
215mod tests;
problemreductions/models/algebraic/minimum_matrix_domination.rs

problemreductions/models/algebraic/
minimum_matrix_domination.rs
