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(&self, target_solution: &[usize]) -> Vec<usize> {
25        target_solution.to_vec()
26    }
27}
28
29#[reduction(
30    overhead = {
31        num_vars = "num_rows * num_cols",
32        num_constraints = "num_rows * num_cols + 1",
33    }
34)]
35impl ReduceTo<ILP<bool>> for RectilinearPictureCompression {
36    type Result = ReductionRPCToILP;
37
38    fn reduce_to(&self) -> Self::Result {
39        let rects = self.maximal_rectangles();
40        let num_vars = rects.len();
41        let mut constraints = Vec::new();
42
43        // For each 1-cell, require at least one covering rectangle selected
44        for i in 0..self.num_rows() {
45            for j in 0..self.num_cols() {
46                if self.matrix()[i][j] {
47                    let terms: Vec<(usize, f64)> = rects
48                        .iter()
49                        .enumerate()
50                        .filter(|(_, &(r1, c1, r2, c2))| i >= r1 && i <= r2 && j >= c1 && j <= c2)
51                        .map(|(idx, _)| (idx, 1.0))
52                        .collect();
53                    constraints.push(LinearConstraint::ge(terms, 1.0));
54                }
55            }
56        }
57
58        // Bound constraint: Σ x_r ≤ bound
59        let bound_terms: Vec<(usize, f64)> = (0..num_vars).map(|i| (i, 1.0)).collect();
60        constraints.push(LinearConstraint::le(bound_terms, self.bound() as f64));
61
62        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
63        ReductionRPCToILP { target }
64    }
65}
66
67#[cfg(feature = "example-db")]
68pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
69    vec![crate::example_db::specs::RuleExampleSpec {
70        id: "rectilinearpicturecompression_to_ilp",
71        build: || {
72            let source =
73                RectilinearPictureCompression::new(vec![vec![true, true], vec![true, true]], 1);
74            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
75        },
76    }]
77}
78
79#[cfg(test)]
80#[path = "../unit_tests/rules/rectilinearpicturecompression_ilp.rs"]
81mod tests;
problemreductions/rules/rectilinearpicturecompression_ilp.rs

problemreductions/rules/
rectilinearpicturecompression_ilp.rs
