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(&self, target_solution: &[usize]) -> Vec<usize> {
28        target_solution[..self.num_cars].to_vec()
29    }
30}
31
32#[reduction(
33    overhead = {
34        num_vars = "num_cars + 2 * num_sequence",
35        num_constraints = "num_sequence + 2 * num_sequence",
36    }
37)]
38impl ReduceTo<ILP<bool>> for PaintShop {
39    type Result = ReductionPaintShopToILP;
40
41    fn reduce_to(&self) -> Self::Result {
42        let nc = self.num_cars();
43        let seq_len = self.sequence_len();
44
45        // Variable layout:
46        //   x_i: car first-occurrence color, index i for i in 0..nc
47        //   k_p: actual color at position p, index nc + p for p in 0..seq_len
48        //   c_p: switch indicator at position p, index nc + seq_len + p
49        let k_offset = nc;
50        let c_offset = nc + seq_len;
51        let num_vars = nc + 2 * seq_len;
52
53        let mut constraints = Vec::new();
54
55        // Determine car index and is_first for each position.
56        // With config all-zero: first occ gets color 0, second occ gets color 1.
57        let base = self.get_coloring(&vec![0; nc]);
58
59        // For each car i, find its positions by flipping x_i.
60        for i in 0..nc {
61            let mut config = vec![0; nc];
62            config[i] = 1;
63            let flipped = self.get_coloring(&config);
64
65            for p in 0..seq_len {
66                if flipped[p] != base[p] {
67                    // Position p belongs to car i
68                    if base[p] == 0 {
69                        // First occurrence: k_p = x_i
70                        constraints.push(LinearConstraint::eq(
71                            vec![(k_offset + p, 1.0), (i, -1.0)],
72                            0.0,
73                        ));
74                    } else {
75                        // Second occurrence: k_p = 1 - x_i  =>  k_p + x_i = 1
76                        constraints.push(LinearConstraint::eq(
77                            vec![(k_offset + p, 1.0), (i, 1.0)],
78                            1.0,
79                        ));
80                    }
81                }
82            }
83        }
84
85        // Switch constraints: c_p >= |k_p - k_{p-1}| for p > 0
86        for p in 1..seq_len {
87            // c_p >= k_p - k_{p-1}
88            constraints.push(LinearConstraint::ge(
89                vec![
90                    (c_offset + p, 1.0),
91                    (k_offset + p, -1.0),
92                    (k_offset + p - 1, 1.0),
93                ],
94                0.0,
95            ));
96            // c_p >= k_{p-1} - k_p
97            constraints.push(LinearConstraint::ge(
98                vec![
99                    (c_offset + p, 1.0),
100                    (k_offset + p - 1, -1.0),
101                    (k_offset + p, 1.0),
102                ],
103                0.0,
104            ));
105        }
106
107        // Objective: minimize Σ c_p for p in 1..seq_len
108        let objective: Vec<(usize, f64)> = (1..seq_len).map(|p| (c_offset + p, 1.0)).collect();
109
110        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
111        ReductionPaintShopToILP {
112            target,
113            num_cars: nc,
114        }
115    }
116}
117
118#[cfg(feature = "example-db")]
119pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
120    use crate::export::SolutionPair;
121    vec![crate::example_db::specs::RuleExampleSpec {
122        id: "paintshop_to_ilp",
123        build: || {
124            // Sequence: A, B, A, C, B, C => 3 cars
125            let source = PaintShop::new(vec!["A", "B", "A", "C", "B", "C"]);
126            let reduction: ReductionPaintShopToILP = ReduceTo::<ILP<bool>>::reduce_to(&source);
127            let target_config = {
128                let ilp_solver = crate::solvers::ILPSolver::new();
129                ilp_solver
130                    .solve(reduction.target_problem())
131                    .expect("ILP should be solvable")
132            };
133            let source_config = reduction.extract_solution(&target_config);
134            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
135                source,
136                SolutionPair {
137                    source_config,
138                    target_config,
139                },
140            )
141        },
142    }]
143}
144
145#[cfg(test)]
146#[path = "../unit_tests/rules/paintshop_ilp.rs"]
147mod tests;
problemreductions/rules/paintshop_ilp.rs

problemreductions/rules/
paintshop_ilp.rs
