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#[reduction(
41    transform = upper_bound {
42        num_vars = "num_cars + 2 * num_sequence",
43        num_constraints = "num_sequence + 2 * num_sequence",
44    },
45    unavailable = {
46        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
47    }
48)]
49impl ReduceTo<ILP<bool>> for PaintShop {
50    type Result = ReductionPaintShopToILP;
51
52    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
53        let nc = self.num_cars();
54        let seq_len = self.sequence_len();
55
56        // Variable layout:
57        //   x_i: car first-occurrence color, index i for i in 0..nc
58        //   k_p: actual color at position p, index nc + p for p in 0..seq_len
59        //   c_p: switch indicator at position p, index nc + seq_len + p
60        let k_offset = nc;
61        let c_offset = nc + seq_len;
62        let num_vars = nc + 2 * seq_len;
63
64        let mut constraints = Vec::new();
65
66        for (position, (&car, &is_first)) in self
67            .sequence_indices()
68            .iter()
69            .zip(self.is_first())
70            .enumerate()
71        {
72            if is_first {
73                // First occurrence: k_p = x_i
74                constraints.push(LinearConstraint::eq(
75                    vec![(k_offset + position, 1), (car, -1)],
76                    0,
77                ));
78            } else {
79                // Second occurrence: k_p = 1 - x_i  =>  k_p + x_i = 1
80                constraints.push(LinearConstraint::eq(
81                    vec![(k_offset + position, 1), (car, 1)],
82                    1,
83                ));
84            }
85        }
86
87        // Switch constraints: c_p >= |k_p - k_{p-1}| for p > 0
88        for p in 1..seq_len {
89            // c_p >= k_p - k_{p-1}
90            constraints.push(LinearConstraint::ge(
91                vec![(c_offset + p, 1), (k_offset + p, -1), (k_offset + p - 1, 1)],
92                0,
93            ));
94            // c_p >= k_{p-1} - k_p
95            constraints.push(LinearConstraint::ge(
96                vec![(c_offset + p, 1), (k_offset + p - 1, -1), (k_offset + p, 1)],
97                0,
98            ));
99        }
100
101        // Objective: minimize Σ c_p for p in 1..seq_len
102        let objective: Vec<(usize, i64)> = (1..seq_len).map(|p| (c_offset + p, 1)).collect();
103
104        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
105            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
106        Ok(ReductionPaintShopToILP {
107            target,
108            num_cars: nc,
109        })
110    }
111}
112
113#[cfg(feature = "example-db")]
114pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
115    use crate::export::SolutionPair;
116    vec![crate::example_db::specs::RuleExampleSpec {
117        id: "paintshop_to_ilp",
118        build: || {
119            // Sequence: A, B, A, C, B, C => 3 cars
120            let source = PaintShop::new(vec!["A", "B", "A", "C", "B", "C"]);
121            let reduction: ReductionPaintShopToILP =
122                ReduceTo::<ILP<bool>>::reduce_to(&source).expect("reduction should succeed");
123            let target_config = {
124                let ilp_solver = crate::solvers::ILPSolver::new();
125                ilp_solver
126                    .solve(reduction.target_problem())
127                    .expect("ILP should be solvable")
128            };
129            let source_config = reduction.extract_solution(&target_config).unwrap();
130            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
131                source,
132                SolutionPair {
133                    source_config: serde_json::to_value(source_config)
134                        .expect("solution serialization must succeed"),
135                    target_config: serde_json::to_value(target_config)
136                        .expect("solution serialization must succeed"),
137                },
138            )
139        },
140    }]
141}
142
143#[cfg(test)]
144#[path = "../unit_tests/rules/paintshop_ilp.rs"]
145mod tests;
problemreductions/rules/paintshop_ilp.rs

problemreductions/rules/
paintshop_ilp.rs
