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::{CreateSpec, 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        category: crate::registry::ProblemCategory::Algebraic,
18        module_path: module_path!(),
19        description: "Augment a binary matrix with at most K zero-to-one flips so some column permutation has the consecutive ones property",
20        fields: ConsecutiveOnesMatrixAugmentationCreateSpec::FIELDS,
21    }
22}
23
24#[derive(Debug, Clone, Serialize, Deserialize)]
25pub struct ConsecutiveOnesMatrixAugmentation {
26    matrix: Vec<Vec<bool>>,
27    bound: i64,
28}
29
30#[derive(Debug, Deserialize, crate::CreateSpec)]
31struct ConsecutiveOnesMatrixAugmentationCreateSpec {
32    /// m x n binary matrix A.
33    matrix: Vec<Vec<bool>>,
34    /// Upper bound K on zero-to-one augmentations.
35    bound: i64,
36}
37impl TryFrom<ConsecutiveOnesMatrixAugmentationCreateSpec> for ConsecutiveOnesMatrixAugmentation {
38    type Error = crate::registry::ConstructionError;
39    fn try_from(spec: ConsecutiveOnesMatrixAugmentationCreateSpec) -> Result<Self, Self::Error> {
40        Self::try_new(spec.matrix, spec.bound)
41    }
42}
43
44impl ConsecutiveOnesMatrixAugmentation {
45    pub fn new(matrix: Vec<Vec<bool>>, bound: i64) -> Self {
46        Self::try_new(matrix, bound).unwrap_or_else(|err| panic!("{err}"))
47    }
48
49    pub fn try_new(
50        matrix: Vec<Vec<bool>>,
51        bound: i64,
52    ) -> Result<Self, crate::registry::ConstructionError> {
53        let num_cols = matrix.first().map_or(0, Vec::len);
54        if matrix.iter().any(|row| row.len() != num_cols) {
55            return Err("all matrix rows must have the same length"
56                .to_string()
57                .into());
58        }
59        if bound < 0 {
60            return Err("bound must be nonnegative".to_string().into());
61        }
62        Ok(Self { matrix, bound })
63    }
64
65    pub fn matrix(&self) -> &[Vec<bool>] {
66        &self.matrix
67    }
68
69    pub fn bound(&self) -> i64 {
70        self.bound
71    }
72
73    pub fn num_rows(&self) -> usize {
74        self.matrix.len()
75    }
76
77    pub fn num_cols(&self) -> usize {
78        self.matrix.first().map_or(0, Vec::len)
79    }
80
81    fn validate_permutation(&self, config: &[usize]) -> bool {
82        if config.len() != self.num_cols() {
83            return false;
84        }
85
86        let mut seen = vec![false; self.num_cols()];
87        for &col in config {
88            if col >= self.num_cols() || seen[col] {
89                return false;
90            }
91            seen[col] = true;
92        }
93        true
94    }
95
96    fn row_augmentation_cost(row: &[bool], config: &[usize]) -> usize {
97        let mut first_one = None;
98        let mut last_one = None;
99        let mut one_count = 0usize;
100
101        for (position, &col) in config.iter().enumerate() {
102            if row[col] {
103                first_one.get_or_insert(position);
104                last_one = Some(position);
105                one_count += 1;
106            }
107        }
108
109        match (first_one, last_one) {
110            (Some(first), Some(last)) => last - first + 1 - one_count,
111            _ => 0,
112        }
113    }
114
115    fn total_augmentation_cost(
116        &self,
117        config: &[usize],
118    ) -> Result<Option<usize>, crate::traits::EvaluationError> {
119        if !self.validate_permutation(config) {
120            return Ok(None);
121        }
122
123        let mut total = 0usize;
124        for row in &self.matrix {
125            total = total
126                .checked_add(Self::row_augmentation_cost(row, config))
127                .ok_or_else(|| {
128                    crate::traits::EvaluationError::IntegerOverflow(
129                        "summing consecutive-ones matrix augmentation costs".to_string(),
130                    )
131                })?;
132            if total > self.bound as usize {
133                return Ok(Some(total));
134            }
135        }
136
137        Ok(Some(total))
138    }
139}
140
141impl Problem for ConsecutiveOnesMatrixAugmentation {
142    const NAME: &'static str = "ConsecutiveOnesMatrixAugmentation";
143    type Solution = Vec<usize>;
144    type Value = crate::types::Or;
145
146    crate::problem_parameters![("num_cols", num_cols), ("num_rows", num_rows),];
147
148    fn evaluate(
149        &self,
150        config: &Self::Solution,
151    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
152        if config.len() != self.num_cols() {
153            return Err(crate::traits::EvaluationError::InvalidConfiguration(
154                "column ordering length does not match the matrix".into(),
155            ));
156        }
157        if config.iter().any(|&column| column >= self.num_cols()) {
158            return Err(crate::traits::EvaluationError::InvalidConfiguration(
159                "column ordering contains an out-of-range column".into(),
160            ));
161        }
162        Ok({
163            crate::types::Or({
164                self.total_augmentation_cost(config)?
165                    .is_some_and(|cost| cost <= self.bound as usize)
166            })
167        })
168    }
169
170    fn variant() -> Vec<(&'static str, &'static str)> {
171        crate::variant_params![]
172    }
173}
174
175impl crate::solvers::BruteForceProblem for ConsecutiveOnesMatrixAugmentation {
176    fn dimensions(&self) -> Vec<usize> {
177        vec![self.num_cols(); self.num_cols()]
178    }
179}
180
181crate::declare_variants! {
182    default ConsecutiveOnesMatrixAugmentation => "factorial(num_cols) * num_rows * num_cols" create ConsecutiveOnesMatrixAugmentationCreateSpec,
183}
184
185crate::register_brute_force! {
186    ConsecutiveOnesMatrixAugmentation,
187}
188
189#[cfg(feature = "example-db")]
190pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
191    vec![crate::example_db::specs::ModelExampleSpec {
192        id: "consecutive_ones_matrix_augmentation",
193        instance: Box::new(ConsecutiveOnesMatrixAugmentation::new(
194            vec![
195                vec![true, false, false, true, true],
196                vec![true, true, false, false, false],
197                vec![false, true, true, false, true],
198                vec![false, false, true, true, false],
199            ],
200            2,
201        )),
202        optimal_config: serde_json::json!(vec![0, 1, 4, 2, 3]),
203        optimal_value: serde_json::json!(true),
204    }]
205}
206
207#[cfg(test)]
208#[path = "../../unit_tests/models/algebraic/consecutive_ones_matrix_augmentation.rs"]
209mod tests;
problemreductions/models/algebraic/consecutive_ones_matrix_augmentation.rs

problemreductions/models/algebraic/
consecutive_ones_matrix_augmentation.rs
