problemreductions/rules/
rectilinearpicturecompression_ilp.rs

1//! Reduction from RectilinearPictureCompression to ILP (Integer Linear Programming).
2//!
3//! Binary variable x_r per maximal rectangle. For each 1-cell, require at least
4//! one covering rectangle selected. Total selected ≤ bound.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::misc::RectilinearPictureCompression;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10
11#[derive(Debug, Clone)]
12pub struct ReductionRPCToILP {
13    target: ILP<bool>,
14}
15
16impl ReductionResult for ReductionRPCToILP {
17    type Source = RectilinearPictureCompression;
18    type Target = ILP<bool>;
19
20    fn target_problem(&self) -> &ILP<bool> {
21        &self.target
22    }
23
24    fn extract_solution(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_witness(
29            self.target_problem(),
30            target_solution,
31            |value| value.value.is_some(),
32            "target ILP assignment is infeasible",
33        )?;
34
35        Ok(target_solution.iter().map(|&value| value == 1).collect())
36    }
37}
38
39#[crate::aggregate_reduction(ilp_feasibility)]
40impl crate::rules::AggregateReductionResult for ReductionRPCToILP {}
41
42// The source caches maximal rectangles. Each has a distinct variable and
43// contributes one coefficient for each covered cell plus one budget term.
44// No coefficients merge or cancel, so these two declarations are exact.
45// The clamped RHS has magnitude <=max(1,R). Positive dimensions
46// satisfy d(d+1)/2<2^d, hence R<2^(r+c) and its bit count is <=r+c.
47#[reduction(
48    transform = {
49        exact {
50            num_vars = "num_rectangles",
51            num_nonzeros = "total_rectangle_area + num_rectangles",
52        },
53        upper_bound {
54            max_constraint_magnitude_bits = "num_rows + num_cols",
55            num_constraints = "num_rows * num_cols + 1",
56        },
57    },
58)]
59impl ReduceTo<ILP<bool>> for RectilinearPictureCompression {
60    type Result = ReductionRPCToILP;
61
62    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
63        let rects = self.maximal_rectangles();
64        let num_vars = rects.len();
65        let mut constraints = Vec::new();
66
67        // For each 1-cell, require at least one covering rectangle selected
68        for i in 0..self.num_rows() {
69            for j in 0..self.num_cols() {
70                if self.matrix()[i][j] {
71                    let terms: Vec<(usize, i64)> = rects
72                        .iter()
73                        .enumerate()
74                        .filter(|(_, &(r1, c1, r2, c2))| i >= r1 && i <= r2 && j >= c1 && j <= c2)
75                        .map(|(idx, _)| (idx, 1))
76                        .collect();
77                    constraints.push(LinearConstraint::ge(terms, 1));
78                }
79            }
80        }
81
82        // Bound constraint: Σ x_r ≤ bound
83        let bound_terms: Vec<(usize, i64)> = (0..num_vars).map(|i| (i, 1)).collect();
84        let max_rectangles = Self::exact_i64(num_vars, "encoding the rectangle-count bound")?;
85        constraints.push(LinearConstraint::le(
86            bound_terms,
87            self.bound().clamp(-1, max_rectangles),
88        ));
89
90        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
91            .map_err(Self::target_construction)?;
92        Ok(ReductionRPCToILP { target })
93    }
94}
95
96#[cfg(feature = "example-db")]
97pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
98    vec![crate::example_db::specs::RuleExampleSpec {
99        id: "rectilinearpicturecompression_to_ilp",
100        build: || {
101            let source =
102                RectilinearPictureCompression::new(vec![vec![true, true], vec![true, true]], 1);
103            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
104        },
105    }]
106}
107
108#[cfg(test)]
109#[path = "../unit_tests/rules/rectilinearpicturecompression_ilp.rs"]
110mod tests;
problemreductions/rules/rectilinearpicturecompression_ilp.rs

problemreductions/rules/
rectilinearpicturecompression_ilp.rs
