problemreductions/models/algebraic/
consecutive_block_minimization.rs

1//! Consecutive Block Minimization (CBM) problem implementation.
2//!
3//! Given an m x n binary matrix A and a positive integer K,
4//! determine whether there exists a permutation of the columns of A
5//! such that the resulting matrix has at most K maximal blocks of
6//! consecutive 1-entries (summed over all rows).
7//!
8//! A "block" is a maximal contiguous run of 1-entries in a row.
9//! This is problem SR17 in Garey & Johnson.
10
11use crate::registry::{CreateSpec, ProblemSchemaEntry};
12use crate::traits::Problem;
13use serde::{Deserialize, Serialize};
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "ConsecutiveBlockMinimization",
18        display_name: "Consecutive Block Minimization",
19        aliases: &["CBM"],
20        dimensions: &[],
21        category: crate::registry::ProblemCategory::Algebraic,
22        module_path: module_path!(),
23        description: "Permute columns of a binary matrix to have at most K consecutive blocks of 1s",
24        fields: ConsecutiveBlockMinimizationCreateSpec::FIELDS,
25    }
26}
27
28/// Consecutive Block Minimization (CBM) problem.
29///
30/// Given an m x n binary matrix A and a positive integer K,
31/// determine whether there exists a permutation of the columns of A
32/// such that the resulting matrix has at most K maximal blocks of
33/// consecutive 1-entries (summed over all rows).
34///
35/// # Example
36///
37/// ```
38/// use problemreductions::models::algebraic::ConsecutiveBlockMinimization;
39/// use problemreductions::{Problem, BruteForce};
40///
41/// // 2x3 binary matrix
42/// let problem = ConsecutiveBlockMinimization::new(
43///     vec![
44///         vec![true, false, true],
45///         vec![false, true, true],
46///     ],
47///     2,
48/// );
49///
50/// let solver = BruteForce::new();
51/// let solutions = solver.find_all_witnesses(&problem).unwrap();
52///
53/// // Verify solutions satisfy the block bound
54/// for sol in solutions {
55///     assert!(problem.evaluate(&sol).unwrap());
56/// }
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59#[serde(
60    try_from = "ConsecutiveBlockMinimizationDef",
61    into = "ConsecutiveBlockMinimizationDef"
62)]
63pub struct ConsecutiveBlockMinimization {
64    /// The binary matrix A (m x n).
65    matrix: Vec<Vec<bool>>,
66    /// Number of rows (m).
67    num_rows: usize,
68    /// Number of columns (n).
69    num_cols: usize,
70    /// Upper bound K on total consecutive blocks.
71    bound: i64,
72}
73
74#[derive(Debug, Deserialize, crate::CreateSpec)]
75struct ConsecutiveBlockMinimizationCreateSpec {
76    /// Binary matrix A (m x n).
77    matrix: Vec<Vec<bool>>,
78    /// Upper bound K on total consecutive blocks.
79    bound_k: i64,
80}
81
82impl TryFrom<ConsecutiveBlockMinimizationCreateSpec> for ConsecutiveBlockMinimization {
83    type Error = crate::registry::ConstructionError;
84
85    fn try_from(spec: ConsecutiveBlockMinimizationCreateSpec) -> Result<Self, Self::Error> {
86        Self::try_new(spec.matrix, spec.bound_k)
87    }
88}
89
90impl ConsecutiveBlockMinimization {
91    /// Create a new ConsecutiveBlockMinimization problem.
92    ///
93    /// # Arguments
94    /// * `matrix` - The m x n binary matrix
95    /// * `bound` - Upper bound on total consecutive blocks
96    ///
97    /// # Panics
98    /// Panics if rows have inconsistent lengths.
99    pub fn new(matrix: Vec<Vec<bool>>, bound: i64) -> Self {
100        Self::try_new(matrix, bound).unwrap_or_else(|err| panic!("{err}"))
101    }
102
103    /// Create a new ConsecutiveBlockMinimization problem, returning an error
104    /// instead of panicking when the matrix is ragged.
105    pub fn try_new(
106        matrix: Vec<Vec<bool>>,
107        bound: i64,
108    ) -> Result<Self, crate::registry::ConstructionError> {
109        let (num_rows, num_cols) = validate_matrix_dimensions(&matrix)?;
110        Ok(Self {
111            matrix,
112            num_rows,
113            num_cols,
114            bound,
115        })
116    }
117
118    /// Get the binary matrix.
119    pub fn matrix(&self) -> &[Vec<bool>] {
120        &self.matrix
121    }
122
123    /// Get the number of rows.
124    pub fn num_rows(&self) -> usize {
125        self.num_rows
126    }
127
128    /// Get the number of columns.
129    pub fn num_cols(&self) -> usize {
130        self.num_cols
131    }
132
133    /// Get the upper bound K.
134    pub fn bound(&self) -> i64 {
135        self.bound
136    }
137
138    /// Count the total number of maximal consecutive blocks of 1s
139    /// when columns are permuted according to `config`.
140    ///
141    /// `config[position] = column_index` defines the column permutation.
142    /// Returns `Some(total_blocks)` if the config is a valid permutation,
143    /// or `None` if it is not (wrong length, duplicate columns, or out-of-range).
144    pub fn count_consecutive_blocks(
145        &self,
146        config: &[usize],
147    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
148        if config.len() != self.num_cols {
149            return Ok(None);
150        }
151
152        // Validate permutation: all values distinct and in 0..num_cols.
153        let mut seen = vec![false; self.num_cols];
154        for &col in config {
155            if col >= self.num_cols || seen[col] {
156                return Ok(None);
157            }
158            seen[col] = true;
159        }
160
161        let mut total_blocks = 0usize;
162        for row in &self.matrix {
163            let mut in_block = false;
164            for &pos in config {
165                if row[pos] {
166                    if !in_block {
167                        total_blocks = total_blocks.checked_add(1).ok_or_else(|| {
168                            crate::traits::EvaluationError::IntegerOverflow(
169                                "counting consecutive blocks".into(),
170                            )
171                        })?;
172                        in_block = true;
173                    }
174                } else {
175                    in_block = false;
176                }
177            }
178        }
179
180        Ok(Some(i64::try_from(total_blocks).map_err(|_| {
181            crate::traits::EvaluationError::IntegerOverflow(
182                "converting consecutive-block count to i64".into(),
183            )
184        })?))
185    }
186}
187
188impl Problem for ConsecutiveBlockMinimization {
189    const NAME: &'static str = "ConsecutiveBlockMinimization";
190    type Solution = Vec<usize>;
191    type Value = crate::types::Or;
192
193    crate::problem_parameters![("num_cols", num_cols), ("num_rows", num_rows),];
194
195    fn evaluate(
196        &self,
197        config: &Self::Solution,
198    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
199        if config.len() != self.num_cols {
200            return Err(crate::traits::EvaluationError::InvalidConfiguration(
201                "column ordering length does not match the matrix".into(),
202            ));
203        }
204        if config.iter().any(|&column| column >= self.num_cols) {
205            return Err(crate::traits::EvaluationError::InvalidConfiguration(
206                "column ordering contains an out-of-range column".into(),
207            ));
208        }
209        Ok({
210            crate::types::Or({
211                match self.count_consecutive_blocks(config)? {
212                    Some(total) => total <= self.bound,
213                    None => false,
214                }
215            })
216        })
217    }
218
219    fn variant() -> Vec<(&'static str, &'static str)> {
220        crate::variant_params![]
221    }
222}
223
224impl crate::solvers::BruteForceProblem for ConsecutiveBlockMinimization {
225    fn dimensions(&self) -> Vec<usize> {
226        vec![self.num_cols; self.num_cols]
227    }
228}
229
230crate::declare_variants! {
231    default ConsecutiveBlockMinimization => "factorial(num_cols) * num_rows * num_cols" create ConsecutiveBlockMinimizationCreateSpec,
232}
233
234crate::register_brute_force! {
235    ConsecutiveBlockMinimization,
236}
237
238#[derive(Debug, Clone, Serialize, Deserialize)]
239struct ConsecutiveBlockMinimizationDef {
240    matrix: Vec<Vec<bool>>,
241    bound: i64,
242}
243
244impl TryFrom<ConsecutiveBlockMinimizationDef> for ConsecutiveBlockMinimization {
245    type Error = crate::registry::ConstructionError;
246
247    fn try_from(value: ConsecutiveBlockMinimizationDef) -> Result<Self, Self::Error> {
248        Self::try_new(value.matrix, value.bound)
249    }
250}
251
252impl From<ConsecutiveBlockMinimization> for ConsecutiveBlockMinimizationDef {
253    fn from(value: ConsecutiveBlockMinimization) -> Self {
254        Self {
255            matrix: value.matrix,
256            bound: value.bound,
257        }
258    }
259}
260
261fn validate_matrix_dimensions(
262    matrix: &[Vec<bool>],
263) -> Result<(usize, usize), crate::registry::ConstructionError> {
264    let num_rows = matrix.len();
265    let num_cols = matrix.first().map_or(0, Vec::len);
266
267    if matrix.iter().any(|row| row.len() != num_cols) {
268        return Err("all matrix rows must have the same length"
269            .to_string()
270            .into());
271    }
272
273    Ok((num_rows, num_cols))
274}
275
276#[cfg(feature = "example-db")]
277pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
278    // Adjacency matrix of path graph P_6, K=6 (one block per row).
279    // Issue #420 Instance 2.
280    vec![crate::example_db::specs::ModelExampleSpec {
281        id: "consecutive_block_minimization",
282        instance: Box::new(ConsecutiveBlockMinimization::new(
283            vec![
284                vec![false, true, false, false, false, false],
285                vec![true, false, true, false, false, false],
286                vec![false, true, false, true, false, false],
287                vec![false, false, true, false, true, false],
288                vec![false, false, false, true, false, true],
289                vec![false, false, false, false, true, false],
290            ],
291            6,
292        )),
293        optimal_config: serde_json::json!(vec![0, 2, 4, 1, 3, 5]),
294        optimal_value: serde_json::json!(true),
295    }]
296}
297
298#[cfg(test)]
299#[path = "../../unit_tests/models/algebraic/consecutive_block_minimization.rs"]
300mod tests;
problemreductions/models/algebraic/consecutive_block_minimization.rs

problemreductions/models/algebraic/
consecutive_block_minimization.rs
