problemreductions/rules/
threepartition_resourceconstrainedscheduling.rs

1//! Reduction from ThreePartition to ResourceConstrainedScheduling.
2//!
3//! Given a 3-Partition instance with 3m elements and target sum B (where each
4//! element a_i satisfies B/4 < a_i < B/2), construct a ResourceConstrainedScheduling
5//! instance with:
6//! - 3m unit-length tasks (one per element)
7//! - 3 processors (at most 3 tasks per time slot)
8//! - 1 resource with bound B
9//! - Resource requirement for task i = s(a_i)
10//! - Deadline D = m (number of triples)
11//!
12//! A valid 3-partition exists iff the tasks can be feasibly scheduled:
13//! the B/4 < a_i < B/2 constraint forces exactly 3 tasks per slot, and
14//! the resource bound forces each slot's triple to sum to exactly B.
15//!
16//! Solution extraction is the identity: config[i] = time slot for task i
17//! directly gives the group assignment for element i.
18//!
19//! Reference: Garey & Johnson, *Computers and Intractability*, Appendix A5.2.
20
21use crate::models::misc::{ResourceConstrainedScheduling, ThreePartition};
22use crate::reduction;
23use crate::rules::traits::{ReduceTo, ReductionResult};
24
25/// Result of reducing ThreePartition to ResourceConstrainedScheduling.
26#[derive(Debug, Clone)]
27pub struct ReductionThreePartitionToRCS {
28    target: ResourceConstrainedScheduling,
29}
30
31impl ReductionResult for ReductionThreePartitionToRCS {
32    type Source = ThreePartition;
33    type Target = ResourceConstrainedScheduling;
34
35    fn target_problem(&self) -> &Self::Target {
36        &self.target
37    }
38
39    /// Solution extraction: identity mapping.
40    /// ThreePartition config (group index 0..m-1) maps directly to time slot assignment.
41    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
42        target_solution.to_vec()
43    }
44}
45
46#[reduction(overhead = {
47    num_tasks = "num_elements",
48})]
49impl ReduceTo<ResourceConstrainedScheduling> for ThreePartition {
50    type Result = ReductionThreePartitionToRCS;
51
52    fn reduce_to(&self) -> Self::Result {
53        let m = self.num_groups();
54        let bound = self.bound();
55
56        // Each element becomes a task with resource requirement = element size
57        let resource_requirements: Vec<Vec<u64>> = self.sizes().iter().map(|&s| vec![s]).collect();
58
59        ReductionThreePartitionToRCS {
60            target: ResourceConstrainedScheduling::new(
61                3,           // 3 processors
62                vec![bound], // 1 resource with bound B
63                resource_requirements,
64                m as u64, // deadline = m time slots
65            ),
66        }
67    }
68}
69
70#[cfg(feature = "example-db")]
71pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
72    use crate::export::SolutionPair;
73
74    vec![crate::example_db::specs::RuleExampleSpec {
75        id: "threepartition_to_resourceconstrainedscheduling",
76        build: || {
77            // sizes [4, 5, 6, 4, 6, 5], B=15, m=2
78            // partition: {4,5,6} and {4,6,5} — both sum to 15
79            // config: elements 0,1,2 in group 0; elements 3,4,5 in group 1
80            crate::example_db::specs::rule_example_with_witness::<_, ResourceConstrainedScheduling>(
81                ThreePartition::new(vec![4, 5, 6, 4, 6, 5], 15),
82                SolutionPair {
83                    source_config: vec![0, 0, 0, 1, 1, 1],
84                    target_config: vec![0, 0, 0, 1, 1, 1],
85                },
86            )
87        },
88    }]
89}
90
91#[cfg(test)]
92#[path = "../unit_tests/rules/threepartition_resourceconstrainedscheduling.rs"]
93mod tests;
problemreductions/rules/threepartition_resourceconstrainedscheduling.rs

problemreductions/rules/
threepartition_resourceconstrainedscheduling.rs
