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(
37        &self,
38        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
39    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
40        crate::rules::traits::validate_target_witness(
41            self.target_problem(),
42            target_solution,
43            |value| value.0,
44            "target witness is not satisfying",
45        )?;
46
47        Ok(target_solution.iter().map(|&count| count > 0).collect())
48    }
49}
50
51#[crate::aggregate_reduction(identity)]
52impl crate::rules::AggregateReductionResult for ReductionXC3SToStaffScheduling {}
53
54#[reduction(
55    transform = exact {
56        num_periods = "universe_size",
57        num_schedules = "num_subsets",
58        num_workers = "universe_size / 3",
59    }
60)]
61impl ReduceTo<StaffScheduling> for ExactCoverBy3Sets {
62    type Result = ReductionXC3SToStaffScheduling;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let universe_size = self.universe_size();
66        let q = universe_size / 3;
67
68        // Build schedule patterns: one per subset
69        let schedules: Vec<Vec<bool>> = self
70            .subsets()
71            .iter()
72            .map(|subset| {
73                let mut schedule = vec![false; universe_size];
74                for &elem in subset {
75                    schedule[elem] = true;
76                }
77                schedule
78            })
79            .collect();
80
81        // Each period requires exactly 1 worker
82        let requirements = vec![1i64; universe_size];
83        let num_workers = i64::try_from(q).map_err(|_| {
84            crate::rules::ReductionError::integer_overflow::<ExactCoverBy3Sets, StaffScheduling>(
85                "converting the exact-cover set count to an i64 worker count",
86            )
87        })?;
88
89        let target = StaffScheduling::new(
90            3, // shifts_per_schedule
91            schedules,
92            requirements,
93            num_workers,
94        );
95
96        Ok(ReductionXC3SToStaffScheduling { target })
97    }
98}
99
100#[cfg(feature = "example-db")]
101pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
102    use crate::export::SolutionPair;
103
104    vec![crate::example_db::specs::RuleExampleSpec {
105        id: "exactcoverby3sets_to_staffscheduling",
106        build: || {
107            // Universe {0,1,2,3,4,5}, subsets [{0,1,2}, {3,4,5}, {0,3,4}, {1,2,5}]
108            // Exact cover: S0 + S1
109            let source =
110                ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4], [1, 2, 5]]);
111            // In StaffScheduling, assigning 1 worker to schedule 0 and 1 worker to schedule 1
112            crate::example_db::specs::rule_example_with_witness::<_, StaffScheduling>(
113                source,
114                SolutionPair {
115                    source_config: serde_json::json!(vec![true, true, false, false]),
116                    target_config: serde_json::json!(vec![1, 1, 0, 0]),
117                },
118            )
119        },
120    }]
121}
122
123#[cfg(test)]
124#[path = "../unit_tests/rules/exactcoverby3sets_staffscheduling.rs"]
125mod tests;
problemreductions/rules/exactcoverby3sets_staffscheduling.rs

problemreductions/rules/
exactcoverby3sets_staffscheduling.rs
