problemreductions/rules/
consecutiveblockminimization_ilp.rs

1//! Reduction from ConsecutiveBlockMinimization to ILP.
2//!
3//! Permute columns with a one-hot assignment and count row-wise block starts
4//! by detecting each 0-to-1 transition after permutation.
5
6use crate::models::algebraic::{
7    ConsecutiveBlockMinimization, LinearConstraint, ObjectiveSense, ILP,
8};
9use crate::reduction;
10use crate::rules::ilp_helpers::{one_hot_assignment_constraints, one_hot_decode};
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13#[derive(Debug, Clone)]
14pub struct ReductionCBMToILP {
15    target: ILP<bool>,
16    num_cols: usize,
17}
18
19impl ReductionResult for ReductionCBMToILP {
20    type Source = ConsecutiveBlockMinimization;
21    type Target = ILP<bool>;
22
23    fn target_problem(&self) -> &ILP<bool> {
24        &self.target
25    }
26
27    fn extract_solution(
28        &self,
29        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
30    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
31        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
32
33        one_hot_decode(target_solution, self.num_cols, self.num_cols, 0)
34    }
35}
36
37#[reduction(
38    transform = upper_bound {
39        num_vars = "num_cols * num_cols + num_rows * num_cols + num_rows * num_cols",
40        num_constraints = "num_cols + num_cols + num_rows * num_cols + num_rows + num_rows * num_cols + 1",
41    },
42    unavailable = {
43        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
44    }
45)]
46impl ReduceTo<ILP<bool>> for ConsecutiveBlockMinimization {
47    type Result = ReductionCBMToILP;
48
49    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
50        let m = self.num_rows();
51        let n = self.num_cols();
52
53        // Variable layout:
54        // x_{c,p}: n*n variables at indices [0, n*n)
55        //   x_{c*n + p} = 1 iff column c goes to position p
56        // a_{r,p}: m*n variables at indices [n*n, n*n + m*n)
57        //   value seen by row r at position p
58        // b_{r,p}: m*n variables at indices [n*n + m*n, n*n + 2*m*n)
59        //   block-start indicator
60        let x_offset = 0;
61        let a_offset = n * n;
62        let b_offset = n * n + m * n;
63        let num_vars = n * n + 2 * m * n;
64
65        let mut constraints = Vec::new();
66
67        // One-hot assignment: each column to exactly one position, each position to exactly one column
68        constraints.extend(one_hot_assignment_constraints(n, n, x_offset));
69
70        // a_{r,p} = sum_c A_{r,c} * x_{c,p} for all r, p
71        for r in 0..m {
72            for p in 0..n {
73                let a_idx = a_offset + r * n + p;
74                // a_{r,p} - sum_c A_{r,c} * x_{c,p} = 0
75                let mut terms = vec![(a_idx, 1)];
76                for c in 0..n {
77                    if self.matrix()[r][c] {
78                        terms.push((x_offset + c * n + p, -1));
79                    }
80                }
81                constraints.push(LinearConstraint::eq(terms, 0));
82            }
83        }
84
85        // Block-start indicators
86        for r in 0..m {
87            // b_{r,0} = a_{r,0}
88            let b_idx = b_offset + r * n;
89            let a_idx = a_offset + r * n;
90            constraints.push(LinearConstraint::eq(vec![(b_idx, 1), (a_idx, -1)], 0));
91
92            // b_{r,p} >= a_{r,p} - a_{r,p-1} for p > 0
93            for p in 1..n {
94                let b_idx = b_offset + r * n + p;
95                let a_cur = a_offset + r * n + p;
96                let a_prev = a_offset + r * n + (p - 1);
97                constraints.push(LinearConstraint::ge(
98                    vec![(b_idx, 1), (a_cur, -1), (a_prev, 1)],
99                    0,
100                ));
101            }
102        }
103
104        // sum_{r,p} b_{r,p} <= K
105        let mut bound_terms = Vec::new();
106        for r in 0..m {
107            for p in 0..n {
108                bound_terms.push((b_offset + r * n + p, 1));
109            }
110        }
111        constraints.push(LinearConstraint::le(bound_terms, self.bound()));
112
113        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
114            .map_err(Self::target_construction)?;
115        Ok(ReductionCBMToILP {
116            target,
117            num_cols: n,
118        })
119    }
120}
121
122#[cfg(feature = "example-db")]
123pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
124    vec![crate::example_db::specs::RuleExampleSpec {
125        id: "consecutiveblockminimization_to_ilp",
126        build: || {
127            // 2x3 matrix, bound=2
128            let source = ConsecutiveBlockMinimization::new(
129                vec![vec![true, false, true], vec![false, true, true]],
130                2,
131            );
132            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
133        },
134    }]
135}
136
137#[cfg(test)]
138#[path = "../unit_tests/rules/consecutiveblockminimization_ilp.rs"]
139mod tests;
problemreductions/rules/consecutiveblockminimization_ilp.rs

problemreductions/rules/
consecutiveblockminimization_ilp.rs
