problemreductions/rules/
consecutiveonesmatrixaugmentation_ilp.rs

1//! Bound each row’s span in a column permutation using two integer endpoints.
2
3use crate::models::algebraic::{
4    Bounded, ConsecutiveOnesMatrixAugmentation, IntegerVariable, LinearConstraint, ObjectiveSense,
5    ILP,
6};
7use crate::reduction;
8use crate::rules::ilp_helpers::{one_hot_assignment_constraints, one_hot_decode};
9use crate::rules::traits::{ReduceTo, ReductionResult};
10
11#[derive(Debug, Clone)]
12pub struct ReductionCOMAToILP {
13    target: ILP<i64, i64, Bounded>,
14    num_cols: usize,
15}
16
17impl ReductionResult for ReductionCOMAToILP {
18    type Source = ConsecutiveOnesMatrixAugmentation;
19    type Target = ILP<i64, i64, Bounded>;
20
21    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
22        &self.target
23    }
24
25    fn extract_solution(
26        &self,
27        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
28    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
29        crate::rules::traits::validate_target_witness(
30            self.target_problem(),
31            target_solution,
32            |value| value.value.is_some(),
33            "target ILP assignment is infeasible",
34        )?;
35
36        one_hot_decode(target_solution, self.num_cols, self.num_cols, 0)
37    }
38}
39
40#[crate::aggregate_reduction(ilp_feasibility)]
41impl crate::rules::AggregateReductionResult for ReductionCOMAToILP {}
42
43#[reduction(transform = {
44    exact { num_vars = "num_cols^2 + 2 * num_rows", },
45    upper_bound {
46        num_constraints = "2 * num_cols + 2 * num_rows * num_cols + 1",
47        num_nonzeros = "2 * num_cols^2 + 2 * num_rows * num_cols^2 + 2 * num_rows",
48        max_constraint_magnitude_bits = "2 * num_rows * num_cols + num_cols + 1",
49    },
50})]
51impl ReduceTo<ILP<i64, i64, Bounded>> for ConsecutiveOnesMatrixAugmentation {
52    type Result = ReductionCOMAToILP;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let m = self.num_rows();
56        let n = self.num_cols();
57
58        let overflow = || {
59            crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
60                "counting matrix interval variables",
61            )
62        };
63        let square = n.checked_mul(n).ok_or_else(overflow)?;
64        let num_vars = m
65            .checked_mul(2)
66            .and_then(|count| square.checked_add(count))
67            .ok_or_else(overflow)?;
68        Self::exact_i64(square, "bounding permutation row arithmetic")?;
69        let cells = Self::exact_i64(
70            m.checked_mul(n).ok_or_else(overflow)?,
71            "counting matrix cells",
72        )?;
73        let last_position = Self::exact_i64(n.saturating_sub(1), "bounding interval endpoints")?;
74        let mut variables = vec![IntegerVariable::binary(); square];
75        let mut constraints = one_hot_assignment_constraints(n, n, 0);
76        let mut budget = Vec::new();
77        let mut total_ones = 0_i64;
78        let mut active_rows = 0_i64;
79        for (r, row) in self.matrix().iter().enumerate() {
80            let nonempty = row.iter().any(|&value| value);
81            let endpoint =
82                IntegerVariable::new(Some(0), Some(if nonempty { last_position } else { 0 }))
83                    .map_err(Self::target_construction)?;
84            variables.extend([endpoint, endpoint]);
85            let left = square + 2 * r;
86            let right = left + 1;
87            for (c, &one) in row.iter().enumerate() {
88                if !one {
89                    continue;
90                }
91                total_ones += 1;
92                let mut after_left = vec![(left, -1)];
93                let mut before_right = vec![(right, 1)];
94                for p in 1..n {
95                    let coefficient = Self::exact_i64(p, "encoding a column position")?;
96                    after_left.push((c * n + p, coefficient));
97                    before_right.push((c * n + p, -coefficient));
98                }
99                constraints.push(LinearConstraint::ge(after_left, 0));
100                constraints.push(LinearConstraint::ge(before_right, 0));
101            }
102            if nonempty {
103                active_rows += 1;
104                budget.extend([(left, -1), (right, 1)]);
105            }
106        }
107        // No ordering can fill more than the matrix's total number of zeros.
108        // Clipping before addition keeps even i64::MAX budgets representable.
109        let rhs = self.bound().min(cells - total_ones) + total_ones - active_rows;
110        constraints.push(LinearConstraint::le(budget, rhs));
111        debug_assert_eq!(variables.len(), num_vars);
112        let target = ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
113            .map_err(Self::target_construction)?;
114        Ok(ReductionCOMAToILP {
115            target,
116            num_cols: n,
117        })
118    }
119}
120
121#[cfg(feature = "example-db")]
122pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
123    vec![crate::example_db::specs::RuleExampleSpec {
124        id: "consecutiveonesmatrixaugmentation_to_ilp",
125        build: || {
126            crate::example_db::specs::rule_example_via_bounded_ilp(
127                ConsecutiveOnesMatrixAugmentation::new(
128                    vec![vec![true, false, true], vec![false, true, true]],
129                    1,
130                ),
131            )
132        },
133    }]
134}
135
136#[cfg(test)]
137#[path = "../unit_tests/rules/consecutiveonesmatrixaugmentation_ilp.rs"]
138mod tests;
problemreductions/rules/consecutiveonesmatrixaugmentation_ilp.rs

problemreductions/rules/
consecutiveonesmatrixaugmentation_ilp.rs
