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(
42        &self,
43        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
44    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
45        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
46
47        Ok(target_solution.to_vec())
48    }
49}
50
51#[reduction(
52    transform = exact {
53        num_tasks = "num_elements",
54    },
55    unavailable = {
56        deadline = "the exact target parameter is not represented by this reduction's symbolic transform",
57        num_resources = "the exact target parameter is not represented by this reduction's symbolic transform",
58    }
59)]
60impl ReduceTo<ResourceConstrainedScheduling> for ThreePartition {
61    type Result = ReductionThreePartitionToRCS;
62
63    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
64        let m = self.num_groups();
65        let bound = self.bound();
66        let deadline = i64::try_from(m).map_err(|_| {
67            crate::rules::ReductionError::integer_overflow::<
68                ThreePartition,
69                ResourceConstrainedScheduling,
70            >("converting the number of groups to a scheduling deadline")
71        })?;
72
73        // Each element becomes a task with resource requirement = element size
74        let resource_requirements: Vec<Vec<i64>> = self.sizes().iter().map(|&s| vec![s]).collect();
75
76        Ok(ReductionThreePartitionToRCS {
77            target: ResourceConstrainedScheduling::new(
78                3,           // 3 processors
79                vec![bound], // 1 resource with bound B
80                resource_requirements,
81                deadline,
82            )
83            .map_err(|error| {
84                crate::rules::ReductionError::construction::<
85                    ThreePartition,
86                    ResourceConstrainedScheduling,
87                >(error)
88            })?,
89        })
90    }
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    use crate::export::SolutionPair;
96
97    vec![crate::example_db::specs::RuleExampleSpec {
98        id: "threepartition_to_resourceconstrainedscheduling",
99        build: || {
100            // sizes [4, 5, 6, 4, 6, 5], B=15, m=2
101            // partition: {4,5,6} and {4,6,5} — both sum to 15
102            // config: elements 0,1,2 in group 0; elements 3,4,5 in group 1
103            crate::example_db::specs::rule_example_with_witness::<_, ResourceConstrainedScheduling>(
104                ThreePartition::new(vec![4, 5, 6, 4, 6, 5], 15),
105                SolutionPair {
106                    source_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
107                    target_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
108                },
109            )
110        },
111    }]
112}
113
114#[cfg(test)]
115#[path = "../unit_tests/rules/threepartition_resourceconstrainedscheduling.rs"]
116mod tests;
problemreductions/rules/threepartition_resourceconstrainedscheduling.rs

problemreductions/rules/
threepartition_resourceconstrainedscheduling.rs
