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(&self, target_solution: &[usize]) -> Vec<usize> {
28        // Decode the column permutation from x_{c,p}
29        one_hot_decode(target_solution, self.num_cols, self.num_cols, 0)
30    }
31}
32
33#[reduction(
34    overhead = {
35        num_vars = "num_cols * num_cols + num_rows * num_cols + num_rows * num_cols",
36        num_constraints = "num_cols + num_cols + num_rows * num_cols + num_rows + num_rows * num_cols + 1",
37    }
38)]
39impl ReduceTo<ILP<bool>> for ConsecutiveBlockMinimization {
40    type Result = ReductionCBMToILP;
41
42    fn reduce_to(&self) -> Self::Result {
43        let m = self.num_rows();
44        let n = self.num_cols();
45
46        // Variable layout:
47        // x_{c,p}: n*n variables at indices [0, n*n)
48        //   x_{c*n + p} = 1 iff column c goes to position p
49        // a_{r,p}: m*n variables at indices [n*n, n*n + m*n)
50        //   value seen by row r at position p
51        // b_{r,p}: m*n variables at indices [n*n + m*n, n*n + 2*m*n)
52        //   block-start indicator
53        let x_offset = 0;
54        let a_offset = n * n;
55        let b_offset = n * n + m * n;
56        let num_vars = n * n + 2 * m * n;
57
58        let mut constraints = Vec::new();
59
60        // One-hot assignment: each column to exactly one position, each position to exactly one column
61        constraints.extend(one_hot_assignment_constraints(n, n, x_offset));
62
63        // a_{r,p} = sum_c A_{r,c} * x_{c,p} for all r, p
64        for r in 0..m {
65            for p in 0..n {
66                let a_idx = a_offset + r * n + p;
67                // a_{r,p} - sum_c A_{r,c} * x_{c,p} = 0
68                let mut terms = vec![(a_idx, 1.0)];
69                for c in 0..n {
70                    if self.matrix()[r][c] {
71                        terms.push((x_offset + c * n + p, -1.0));
72                    }
73                }
74                constraints.push(LinearConstraint::eq(terms, 0.0));
75            }
76        }
77
78        // Block-start indicators
79        for r in 0..m {
80            // b_{r,0} = a_{r,0}
81            let b_idx = b_offset + r * n;
82            let a_idx = a_offset + r * n;
83            constraints.push(LinearConstraint::eq(vec![(b_idx, 1.0), (a_idx, -1.0)], 0.0));
84
85            // b_{r,p} >= a_{r,p} - a_{r,p-1} for p > 0
86            for p in 1..n {
87                let b_idx = b_offset + r * n + p;
88                let a_cur = a_offset + r * n + p;
89                let a_prev = a_offset + r * n + (p - 1);
90                constraints.push(LinearConstraint::ge(
91                    vec![(b_idx, 1.0), (a_cur, -1.0), (a_prev, 1.0)],
92                    0.0,
93                ));
94            }
95        }
96
97        // sum_{r,p} b_{r,p} <= K
98        let mut bound_terms = Vec::new();
99        for r in 0..m {
100            for p in 0..n {
101                bound_terms.push((b_offset + r * n + p, 1.0));
102            }
103        }
104        constraints.push(LinearConstraint::le(bound_terms, self.bound() as f64));
105
106        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
107        ReductionCBMToILP {
108            target,
109            num_cols: n,
110        }
111    }
112}
113
114#[cfg(feature = "example-db")]
115pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
116    vec![crate::example_db::specs::RuleExampleSpec {
117        id: "consecutiveblockminimization_to_ilp",
118        build: || {
119            // 2x3 matrix, bound=2
120            let source = ConsecutiveBlockMinimization::new(
121                vec![vec![true, false, true], vec![false, true, true]],
122                2,
123            );
124            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
125        },
126    }]
127}
128
129#[cfg(test)]
130#[path = "../unit_tests/rules/consecutiveblockminimization_ilp.rs"]
131mod tests;
problemreductions/rules/consecutiveblockminimization_ilp.rs

problemreductions/rules/
consecutiveblockminimization_ilp.rs
