problemreductions/rules/
timetabledesign_ilp.rs

1//! Reduction from TimetableDesign to `ILP<bool>`.
2//!
3//! The source witness is a binary craftsman-task-period incidence table,
4//! and all feasibility conditions are already linear: availability forcing,
5//! per-period exclusivity, and exact pairwise work requirements.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::misc::TimetableDesign;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12/// Result of reducing TimetableDesign to `ILP<bool>`.
13///
14/// Variable layout: x_{c,t,h} at index `((c * num_tasks) + t) * num_periods + h`
15/// exactly matching the source configuration layout.
16#[derive(Debug, Clone)]
17pub struct ReductionTDToILP {
18    target: ILP<bool>,
19    num_craftsmen: usize,
20    num_tasks: usize,
21    num_periods: usize,
22}
23
24impl ReductionResult for ReductionTDToILP {
25    type Source = TimetableDesign;
26    type Target = ILP<bool>;
27
28    fn target_problem(&self) -> &ILP<bool> {
29        &self.target
30    }
31
32    /// Extract: direct identity mapping — the ILP variable layout matches the
33    /// source configuration layout exactly.
34    fn extract_solution(
35        &self,
36        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
37    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
38        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
39
40        Ok((0..self.num_craftsmen)
41            .map(|craftsman| {
42                (0..self.num_tasks)
43                    .map(|task| {
44                        (0..self.num_periods)
45                            .map(|period| {
46                                let index = ((craftsman * self.num_tasks) + task)
47                                    * self.num_periods
48                                    + period;
49                                target_solution[index] == 1
50                            })
51                            .collect()
52                    })
53                    .collect()
54            })
55            .collect())
56    }
57}
58
59#[reduction(
60    transform = exact {
61        num_vars = "num_craftsmen * num_tasks * num_periods",
62        num_constraints = "num_craftsmen * num_periods + num_tasks * num_periods + num_craftsmen * num_tasks",
63    },
64    unavailable = {
65        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
66    }
67)]
68impl ReduceTo<ILP<bool>> for TimetableDesign {
69    type Result = ReductionTDToILP;
70
71    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
72        let nc = self.num_craftsmen();
73        let nt = self.num_tasks();
74        let nh = self.num_periods();
75        let requirements = self.requirements();
76        let num_vars = nc * nt * nh;
77
78        let var = |c: usize, t: usize, h: usize| -> usize { ((c * nt) + t) * nh + h };
79
80        let mut constraints = Vec::new();
81
82        // 1. Availability: x_{c,t,h} = 0 whenever craftsman c or task t is unavailable in h
83        for c in 0..nc {
84            for t in 0..nt {
85                for h in 0..nh {
86                    if !self.craftsman_avail()[c][h] || !self.task_avail()[t][h] {
87                        constraints.push(LinearConstraint::eq(vec![(var(c, t, h), 1)], 0));
88                    }
89                }
90            }
91        }
92
93        // 2. Each craftsman works on at most one task per period: Σ_t x_{c,t,h} <= 1 for all c, h
94        for c in 0..nc {
95            for h in 0..nh {
96                let terms: Vec<(usize, i64)> = (0..nt).map(|t| (var(c, t, h), 1)).collect();
97                constraints.push(LinearConstraint::le(terms, 1));
98            }
99        }
100
101        // 3. Each task worked on by at most one craftsman per period: Σ_c x_{c,t,h} <= 1 for all t, h
102        for t in 0..nt {
103            for h in 0..nh {
104                let terms: Vec<(usize, i64)> = (0..nc).map(|c| (var(c, t, h), 1)).collect();
105                constraints.push(LinearConstraint::le(terms, 1));
106            }
107        }
108
109        // 4. Exact requirements: Σ_h x_{c,t,h} = r_{c,t} for all c, t
110        for (c, row) in requirements.iter().enumerate() {
111            for (t, &requirement) in row.iter().enumerate() {
112                let terms: Vec<(usize, i64)> = (0..nh).map(|h| (var(c, t, h), 1)).collect();
113                constraints.push(LinearConstraint::eq(terms, requirement));
114            }
115        }
116
117        Ok(ReductionTDToILP {
118            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
119                .map_err(Self::target_construction)?,
120            num_craftsmen: nc,
121            num_tasks: nt,
122            num_periods: nh,
123        })
124    }
125}
126
127#[cfg(feature = "example-db")]
128pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
129    vec![crate::example_db::specs::RuleExampleSpec {
130        id: "timetabledesign_to_ilp",
131        build: || {
132            // Small 2-craftsman, 2-task, 2-period instance
133            let source = TimetableDesign::new(
134                2,
135                2,
136                2,
137                vec![vec![true, true], vec![true, true]],
138                vec![vec![true, true], vec![true, true]],
139                vec![vec![1, 0], vec![0, 1]],
140            );
141            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
142        },
143    }]
144}
145
146#[cfg(test)]
147#[path = "../unit_tests/rules/timetabledesign_ilp.rs"]
148mod tests;
problemreductions/rules/timetabledesign_ilp.rs

problemreductions/rules/
timetabledesign_ilp.rs
