problemreductions/models/algebraic/
consecutive_ones_matrix_augmentation.rs

1//! Consecutive Ones Matrix Augmentation problem implementation.
2//!
3//! Given an m x n binary matrix A and a nonnegative integer K, determine
4//! whether there exists a permutation of the columns and at most K zero-to-one
5//! augmentations such that every row has consecutive 1s.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "ConsecutiveOnesMatrixAugmentation",
14        display_name: "Consecutive Ones Matrix Augmentation",
15        aliases: &[],
16        dimensions: &[],
17        module_path: module_path!(),
18        description: "Augment a binary matrix with at most K zero-to-one flips so some column permutation has the consecutive ones property",
19        fields: &[
20            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "m x n binary matrix A" },
21            FieldInfo { name: "bound", type_name: "i64", description: "Upper bound K on zero-to-one augmentations" },
22        ],
23    }
24}
25
26#[derive(Debug, Clone, Serialize, Deserialize)]
27pub struct ConsecutiveOnesMatrixAugmentation {
28    matrix: Vec<Vec<bool>>,
29    bound: i64,
30}
31
32impl ConsecutiveOnesMatrixAugmentation {
33    pub fn new(matrix: Vec<Vec<bool>>, bound: i64) -> Self {
34        Self::try_new(matrix, bound).unwrap_or_else(|err| panic!("{err}"))
35    }
36
37    pub fn try_new(matrix: Vec<Vec<bool>>, bound: i64) -> Result<Self, String> {
38        let num_cols = matrix.first().map_or(0, Vec::len);
39        if matrix.iter().any(|row| row.len() != num_cols) {
40            return Err("all matrix rows must have the same length".to_string());
41        }
42        if bound < 0 {
43            return Err("bound must be nonnegative".to_string());
44        }
45        Ok(Self { matrix, bound })
46    }
47
48    pub fn matrix(&self) -> &[Vec<bool>] {
49        &self.matrix
50    }
51
52    pub fn bound(&self) -> i64 {
53        self.bound
54    }
55
56    pub fn num_rows(&self) -> usize {
57        self.matrix.len()
58    }
59
60    pub fn num_cols(&self) -> usize {
61        self.matrix.first().map_or(0, Vec::len)
62    }
63
64    fn validate_permutation(&self, config: &[usize]) -> bool {
65        if config.len() != self.num_cols() {
66            return false;
67        }
68
69        let mut seen = vec![false; self.num_cols()];
70        for &col in config {
71            if col >= self.num_cols() || seen[col] {
72                return false;
73            }
74            seen[col] = true;
75        }
76        true
77    }
78
79    fn row_augmentation_cost(row: &[bool], config: &[usize]) -> usize {
80        let mut first_one = None;
81        let mut last_one = None;
82        let mut one_count = 0usize;
83
84        for (position, &col) in config.iter().enumerate() {
85            if row[col] {
86                first_one.get_or_insert(position);
87                last_one = Some(position);
88                one_count += 1;
89            }
90        }
91
92        match (first_one, last_one) {
93            (Some(first), Some(last)) => last - first + 1 - one_count,
94            _ => 0,
95        }
96    }
97
98    fn total_augmentation_cost(&self, config: &[usize]) -> Option<usize> {
99        if !self.validate_permutation(config) {
100            return None;
101        }
102
103        let mut total = 0usize;
104        for row in &self.matrix {
105            total += Self::row_augmentation_cost(row, config);
106            if total > self.bound as usize {
107                return Some(total);
108            }
109        }
110
111        Some(total)
112    }
113}
114
115impl Problem for ConsecutiveOnesMatrixAugmentation {
116    const NAME: &'static str = "ConsecutiveOnesMatrixAugmentation";
117    type Value = crate::types::Or;
118
119    fn dims(&self) -> Vec<usize> {
120        vec![self.num_cols(); self.num_cols()]
121    }
122
123    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
124        crate::types::Or({
125            self.total_augmentation_cost(config)
126                .is_some_and(|cost| cost <= self.bound as usize)
127        })
128    }
129
130    fn variant() -> Vec<(&'static str, &'static str)> {
131        crate::variant_params![]
132    }
133
134    fn num_variables(&self) -> usize {
135        self.num_cols()
136    }
137}
138
139crate::declare_variants! {
140    default ConsecutiveOnesMatrixAugmentation => "factorial(num_cols) * num_rows * num_cols",
141}
142
143#[cfg(feature = "example-db")]
144pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
145    vec![crate::example_db::specs::ModelExampleSpec {
146        id: "consecutive_ones_matrix_augmentation",
147        instance: Box::new(ConsecutiveOnesMatrixAugmentation::new(
148            vec![
149                vec![true, false, false, true, true],
150                vec![true, true, false, false, false],
151                vec![false, true, true, false, true],
152                vec![false, false, true, true, false],
153            ],
154            2,
155        )),
156        optimal_config: vec![0, 1, 4, 2, 3],
157        optimal_value: serde_json::json!(true),
158    }]
159}
160
161#[cfg(test)]
162#[path = "../../unit_tests/models/algebraic/consecutive_ones_matrix_augmentation.rs"]
163mod tests;
problemreductions/models/algebraic/consecutive_ones_matrix_augmentation.rs

problemreductions/models/algebraic/
consecutive_ones_matrix_augmentation.rs
