problemreductions/rules/
paintshop_ilp.rs

1//! Reduction from PaintShop to ILP (Integer Linear Programming).
2//!
3//! Binary variable x_i per car (first-occurrence color), binary k_p per
4//! sequence position (actual color), binary c_p per adjacent pair (switch
5//! indicator). Minimize Σ c_p.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::PaintShop;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12#[derive(Debug, Clone)]
13pub struct ReductionPaintShopToILP {
14    target: ILP<bool>,
15    num_cars: usize,
16}
17
18impl ReductionResult for ReductionPaintShopToILP {
19    type Source = PaintShop;
20    type Target = ILP<bool>;
21
22    fn target_problem(&self) -> &ILP<bool> {
23        &self.target
24    }
25
26    /// Extract first-occurrence color bits (x_i) from ILP solution.
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        Ok(target_solution[..self.num_cars]
34            .iter()
35            .map(|&value| value == 1)
36            .collect())
37    }
38}
39
40// Position rows have two coefficients; each consecutive pair adds two rows
41// of three coefficients, for at most 8 * sequence_len coefficients overall.
42#[reduction(transform = {
43    exact {
44        num_vars = "num_cars + 2 * num_sequence",
45    },
46    upper_bound {
47        max_constraint_magnitude_bits = "1",
48        num_constraints = "3 * num_sequence",
49        num_nonzeros = "8 * num_sequence",
50    },
51})]
52impl ReduceTo<ILP<bool>> for PaintShop {
53    type Result = ReductionPaintShopToILP;
54
55    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
56        let nc = self.num_cars();
57        let seq_len = self.sequence_len();
58
59        // Variable layout:
60        //   x_i: car first-occurrence color, index i for i in 0..nc
61        //   k_p: actual color at position p, index nc + p for p in 0..seq_len
62        //   c_p: switch indicator at position p, index nc + seq_len + p
63        let k_offset = nc;
64        let c_offset = nc + seq_len;
65        let num_vars = nc + 2 * seq_len;
66
67        let mut constraints = Vec::new();
68
69        for (position, (&car, &is_first)) in self
70            .sequence_indices()
71            .iter()
72            .zip(self.is_first())
73            .enumerate()
74        {
75            if is_first {
76                // First occurrence: k_p = x_i
77                constraints.push(LinearConstraint::eq(
78                    vec![(k_offset + position, 1), (car, -1)],
79                    0,
80                ));
81            } else {
82                // Second occurrence: k_p = 1 - x_i  =>  k_p + x_i = 1
83                constraints.push(LinearConstraint::eq(
84                    vec![(k_offset + position, 1), (car, 1)],
85                    1,
86                ));
87            }
88        }
89
90        // Switch constraints: c_p >= |k_p - k_{p-1}| for p > 0
91        for p in 1..seq_len {
92            // c_p >= k_p - k_{p-1}
93            constraints.push(LinearConstraint::ge(
94                vec![(c_offset + p, 1), (k_offset + p, -1), (k_offset + p - 1, 1)],
95                0,
96            ));
97            // c_p >= k_{p-1} - k_p
98            constraints.push(LinearConstraint::ge(
99                vec![(c_offset + p, 1), (k_offset + p - 1, -1), (k_offset + p, 1)],
100                0,
101            ));
102        }
103
104        // Objective: minimize Σ c_p for p in 1..seq_len
105        let objective: Vec<(usize, i64)> = (1..seq_len).map(|p| (c_offset + p, 1)).collect();
106
107        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
108            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
109        Ok(ReductionPaintShopToILP {
110            target,
111            num_cars: nc,
112        })
113    }
114}
115
116#[cfg(feature = "example-db")]
117pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
118    use crate::export::SolutionPair;
119    vec![crate::example_db::specs::RuleExampleSpec {
120        id: "paintshop_to_ilp",
121        build: || {
122            // Sequence: A, B, A, C, B, C => 3 cars
123            let source = PaintShop::new(vec!["A", "B", "A", "C", "B", "C"]);
124            let reduction: ReductionPaintShopToILP =
125                ReduceTo::<ILP<bool>>::reduce_to(&source).expect("reduction should succeed");
126            let target_config = {
127                let ilp_solver = crate::solvers::ILPSolver::new();
128                ilp_solver
129                    .solve(reduction.target_problem())
130                    .expect("ILP should be solvable")
131            };
132            let source_config = reduction.extract_solution(&target_config).unwrap();
133            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
134                source,
135                SolutionPair {
136                    source_config: serde_json::to_value(source_config)
137                        .expect("solution serialization must succeed"),
138                    target_config: serde_json::to_value(target_config)
139                        .expect("solution serialization must succeed"),
140                },
141            )
142        },
143    }]
144}
145
146#[cfg(test)]
147#[path = "../unit_tests/rules/paintshop_ilp.rs"]
148mod tests;
problemreductions/rules/paintshop_ilp.rs

problemreductions/rules/
paintshop_ilp.rs
