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

problemreductions/models/algebraic/
consecutive_ones_matrix_augmentation.rs
