problemreductions/rules/
exactcoverby3sets_staffscheduling.rs

1//! Reduction from ExactCoverBy3Sets to StaffScheduling.
2//!
3//! Given an X3C instance with universe X (|X| = 3q) and collection C of
4//! 3-element subsets, construct a StaffScheduling instance where:
5//! - Each universe element becomes a period (m = 3q periods)
6//! - Each subset S_j = {a, b, c} becomes a schedule with shifts at positions a, b, c
7//! - All requirements are 1 (each period needs exactly 1 worker)
8//! - The worker budget is q (an exact cover uses exactly q subsets)
9//! - shifts_per_schedule = 3 (each schedule has exactly 3 active periods)
10//!
11//! An exact cover in X3C corresponds to a feasible staff assignment.
12
13use crate::models::misc::StaffScheduling;
14use crate::models::set::ExactCoverBy3Sets;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17
18/// Result of reducing ExactCoverBy3Sets to StaffScheduling.
19#[derive(Debug, Clone)]
20pub struct ReductionXC3SToStaffScheduling {
21    target: StaffScheduling,
22}
23
24impl ReductionResult for ReductionXC3SToStaffScheduling {
25    type Source = ExactCoverBy3Sets;
26    type Target = StaffScheduling;
27
28    fn target_problem(&self) -> &StaffScheduling {
29        &self.target
30    }
31
32    /// Extract XC3S solution from StaffScheduling solution.
33    ///
34    /// StaffScheduling config[j] = number of workers assigned to schedule j.
35    /// XC3S config[j] = 1 if subset j is selected, 0 otherwise.
36    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
37        target_solution
38            .iter()
39            .map(|&count| if count > 0 { 1 } else { 0 })
40            .collect()
41    }
42}
43
44#[reduction(
45    overhead = {
46        num_periods = "universe_size",
47        num_schedules = "num_subsets",
48        num_workers = "universe_size / 3",
49    }
50)]
51impl ReduceTo<StaffScheduling> for ExactCoverBy3Sets {
52    type Result = ReductionXC3SToStaffScheduling;
53
54    fn reduce_to(&self) -> Self::Result {
55        let universe_size = self.universe_size();
56        let q = universe_size / 3;
57
58        // Build schedule patterns: one per subset
59        let schedules: Vec<Vec<bool>> = self
60            .subsets()
61            .iter()
62            .map(|subset| {
63                let mut schedule = vec![false; universe_size];
64                for &elem in subset {
65                    schedule[elem] = true;
66                }
67                schedule
68            })
69            .collect();
70
71        // Each period requires exactly 1 worker
72        let requirements = vec![1u64; universe_size];
73
74        let target = StaffScheduling::new(
75            3, // shifts_per_schedule
76            schedules,
77            requirements,
78            q as u64, // num_workers = q
79        );
80
81        ReductionXC3SToStaffScheduling { target }
82    }
83}
84
85#[cfg(feature = "example-db")]
86pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
87    use crate::export::SolutionPair;
88
89    vec![crate::example_db::specs::RuleExampleSpec {
90        id: "exactcoverby3sets_to_staffscheduling",
91        build: || {
92            // Universe {0,1,2,3,4,5}, subsets [{0,1,2}, {3,4,5}, {0,3,4}, {1,2,5}]
93            // Exact cover: S0 + S1
94            let source =
95                ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4], [1, 2, 5]]);
96            // In StaffScheduling, assigning 1 worker to schedule 0 and 1 worker to schedule 1
97            crate::example_db::specs::rule_example_with_witness::<_, StaffScheduling>(
98                source,
99                SolutionPair {
100                    source_config: vec![1, 1, 0, 0],
101                    target_config: vec![1, 1, 0, 0],
102                },
103            )
104        },
105    }]
106}
107
108#[cfg(test)]
109#[path = "../unit_tests/rules/exactcoverby3sets_staffscheduling.rs"]
110mod tests;
problemreductions/rules/exactcoverby3sets_staffscheduling.rs

problemreductions/rules/
exactcoverby3sets_staffscheduling.rs
