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}
20
21impl ReductionResult for ReductionTDToILP {
22    type Source = TimetableDesign;
23    type Target = ILP<bool>;
24
25    fn target_problem(&self) -> &ILP<bool> {
26        &self.target
27    }
28
29    /// Extract: direct identity mapping — the ILP variable layout matches the
30    /// source configuration layout exactly.
31    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
32        target_solution.to_vec()
33    }
34}
35
36#[reduction(overhead = {
37    num_vars = "num_craftsmen * num_tasks * num_periods",
38    num_constraints = "num_craftsmen * num_periods + num_tasks * num_periods + num_craftsmen * num_tasks",
39})]
40impl ReduceTo<ILP<bool>> for TimetableDesign {
41    type Result = ReductionTDToILP;
42
43    fn reduce_to(&self) -> Self::Result {
44        let nc = self.num_craftsmen();
45        let nt = self.num_tasks();
46        let nh = self.num_periods();
47        let num_vars = nc * nt * nh;
48
49        let var = |c: usize, t: usize, h: usize| -> usize { ((c * nt) + t) * nh + h };
50
51        let mut constraints = Vec::new();
52
53        // 1. Availability: x_{c,t,h} = 0 whenever craftsman c or task t is unavailable in h
54        for c in 0..nc {
55            for t in 0..nt {
56                for h in 0..nh {
57                    if !self.craftsman_avail()[c][h] || !self.task_avail()[t][h] {
58                        constraints.push(LinearConstraint::eq(vec![(var(c, t, h), 1.0)], 0.0));
59                    }
60                }
61            }
62        }
63
64        // 2. Each craftsman works on at most one task per period: Σ_t x_{c,t,h} <= 1 for all c, h
65        for c in 0..nc {
66            for h in 0..nh {
67                let terms: Vec<(usize, f64)> = (0..nt).map(|t| (var(c, t, h), 1.0)).collect();
68                constraints.push(LinearConstraint::le(terms, 1.0));
69            }
70        }
71
72        // 3. Each task worked on by at most one craftsman per period: Σ_c x_{c,t,h} <= 1 for all t, h
73        for t in 0..nt {
74            for h in 0..nh {
75                let terms: Vec<(usize, f64)> = (0..nc).map(|c| (var(c, t, h), 1.0)).collect();
76                constraints.push(LinearConstraint::le(terms, 1.0));
77            }
78        }
79
80        // 4. Exact requirements: Σ_h x_{c,t,h} = r_{c,t} for all c, t
81        for c in 0..nc {
82            for t in 0..nt {
83                let terms: Vec<(usize, f64)> = (0..nh).map(|h| (var(c, t, h), 1.0)).collect();
84                constraints.push(LinearConstraint::eq(
85                    terms,
86                    self.requirements()[c][t] as f64,
87                ));
88            }
89        }
90
91        ReductionTDToILP {
92            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
93        }
94    }
95}
96
97#[cfg(feature = "example-db")]
98pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
99    vec![crate::example_db::specs::RuleExampleSpec {
100        id: "timetabledesign_to_ilp",
101        build: || {
102            // Small 2-craftsman, 2-task, 2-period instance
103            let source = TimetableDesign::new(
104                2,
105                2,
106                2,
107                vec![vec![true, true], vec![true, true]],
108                vec![vec![true, true], vec![true, true]],
109                vec![vec![1, 0], vec![0, 1]],
110            );
111            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
112        },
113    }]
114}
115
116#[cfg(test)]
117#[path = "../unit_tests/rules/timetabledesign_ilp.rs"]
118mod tests;
problemreductions/rules/timetabledesign_ilp.rs

problemreductions/rules/
timetabledesign_ilp.rs
