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#[derive(Debug, Clone)]
14pub struct ReductionTDToILP {
15    target: ILP<bool>,
16    num_craftsmen: usize,
17    num_tasks: usize,
18    num_periods: usize,
19    assignments: Vec<(usize, usize, usize)>,
20}
21
22impl ReductionResult for ReductionTDToILP {
23    type Source = TimetableDesign;
24    type Target = ILP<bool>;
25
26    fn target_problem(&self) -> &ILP<bool> {
27        &self.target
28    }
29
30    fn extract_solution(
31        &self,
32        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
33    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
34        crate::rules::traits::validate_target_witness(
35            self.target_problem(),
36            target_solution,
37            |value| value.value.is_some(),
38            "target ILP assignment is infeasible",
39        )?;
40
41        let mut timetable =
42            vec![vec![vec![false; self.num_periods]; self.num_tasks]; self.num_craftsmen];
43        for (variable, &(craftsman, task, period)) in self.assignments.iter().enumerate() {
44            timetable[craftsman][task][period] = target_solution[variable] == 1;
45        }
46        Ok(timetable)
47    }
48}
49
50#[crate::aggregate_reduction(ilp_feasibility)]
51impl crate::rules::AggregateReductionResult for ReductionTDToILP {}
52
53#[reduction(transform = {
54    exact {
55        num_vars = "num_available_assignments",
56        num_nonzeros = "3 * num_available_assignments",
57    },
58    upper_bound {
59        num_constraints = "2 * num_available_assignments + num_nonzero_requirements",
60        max_constraint_magnitude_bits = "period_count_bits + 1",
61    },
62})]
63impl ReduceTo<ILP<bool>> for TimetableDesign {
64    type Result = ReductionTDToILP;
65
66    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
67        let nc = self.num_craftsmen();
68        let nt = self.num_tasks();
69        let nh = self.num_periods();
70        let requirements = self.requirements();
71        // A pair can work at most nh periods. Keep out-of-range requirements infeasible.
72        let max_requirement = Self::exact_i64(nh, "encoding the period count")?.saturating_add(1);
73        let mut assignments = Vec::new();
74        let mut craftsmen = std::collections::BTreeMap::<_, Vec<_>>::new();
75        let mut tasks = std::collections::BTreeMap::<_, Vec<_>>::new();
76        let mut pairs = Vec::new();
77        for (c, row) in requirements.iter().enumerate() {
78            for (t, &requirement) in row.iter().enumerate() {
79                if requirement == 0 {
80                    continue;
81                }
82                let mut terms = Vec::new();
83                if requirement > 0 {
84                    for h in 0..nh {
85                        if self.craftsman_avail()[c][h] && self.task_avail()[t][h] {
86                            let term = (assignments.len(), 1);
87                            assignments.push((c, t, h));
88                            terms.push(term);
89                            craftsmen.entry((c, h)).or_default().push(term);
90                            tasks.entry((t, h)).or_default().push(term);
91                        }
92                    }
93                }
94                pairs.push(LinearConstraint::eq(
95                    terms,
96                    requirement.clamp(-1, max_requirement),
97                ));
98            }
99        }
100        let mut constraints: Vec<_> = craftsmen
101            .into_values()
102            .chain(tasks.into_values())
103            .map(|terms| LinearConstraint::le(terms, 1))
104            .collect();
105        constraints.extend(pairs);
106        Ok(ReductionTDToILP {
107            target: ILP::new(
108                assignments.len(),
109                constraints,
110                vec![],
111                ObjectiveSense::Minimize,
112            )
113            .map_err(Self::target_construction)?,
114            num_craftsmen: nc,
115            num_tasks: nt,
116            num_periods: nh,
117            assignments,
118        })
119    }
120}
121
122#[cfg(feature = "example-db")]
123pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
124    vec![crate::example_db::specs::RuleExampleSpec {
125        id: "timetabledesign_to_ilp",
126        build: || {
127            // Small 2-craftsman, 2-task, 2-period instance
128            let source = TimetableDesign::new(
129                2,
130                2,
131                2,
132                vec![vec![true, true], vec![true, true]],
133                vec![vec![true, true], vec![true, true]],
134                vec![vec![1, 0], vec![0, 1]],
135            );
136            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
137        },
138    }]
139}
140
141#[cfg(test)]
142#[path = "../unit_tests/rules/timetabledesign_ilp.rs"]
143mod tests;
problemreductions/rules/timetabledesign_ilp.rs

problemreductions/rules/
timetabledesign_ilp.rs
