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_witness(
46            self.target_problem(),
47            target_solution,
48            |value| value.0,
49            "target witness does not satisfy the target problem",
50        )?;
51
52        Ok(target_solution.to_vec())
53    }
54}
55
56#[crate::aggregate_reduction(identity)]
57impl crate::rules::AggregateReductionResult for ReductionThreePartitionToRCS {}
58
59#[reduction(
60    transform = exact {
61        max_resource_bits = "max_numeric_magnitude_bits",
62        num_tasks = "num_elements",
63        deadline = "num_groups",
64        num_resources = "1",
65    }
66)]
67impl ReduceTo<ResourceConstrainedScheduling> for ThreePartition {
68    type Result = ReductionThreePartitionToRCS;
69
70    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
71        let m = self.num_groups();
72        let bound = self.bound();
73        let deadline = i64::try_from(m).map_err(|_| {
74            crate::rules::ReductionError::integer_overflow::<
75                ThreePartition,
76                ResourceConstrainedScheduling,
77            >("converting the number of groups to a scheduling deadline")
78        })?;
79
80        // Each element becomes a task with resource requirement = element size
81        let resource_requirements: Vec<Vec<i64>> = self.sizes().iter().map(|&s| vec![s]).collect();
82
83        Ok(ReductionThreePartitionToRCS {
84            target: ResourceConstrainedScheduling::new(
85                3,           // 3 processors
86                vec![bound], // 1 resource with bound B
87                resource_requirements,
88                deadline,
89            )
90            .map_err(|error| {
91                crate::rules::ReductionError::construction::<
92                    ThreePartition,
93                    ResourceConstrainedScheduling,
94                >(error)
95            })?,
96        })
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: "threepartition_to_resourceconstrainedscheduling",
106        build: || {
107            // sizes [4, 5, 6, 4, 6, 5], B=15, m=2
108            // partition: {4,5,6} and {4,6,5} — both sum to 15
109            // config: elements 0,1,2 in group 0; elements 3,4,5 in group 1
110            crate::example_db::specs::rule_example_with_witness::<_, ResourceConstrainedScheduling>(
111                ThreePartition::new(vec![4, 5, 6, 4, 6, 5], 15),
112                SolutionPair {
113                    source_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
114                    target_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
115                },
116            )
117        },
118    }]
119}
120
121#[cfg(test)]
122#[path = "../unit_tests/rules/threepartition_resourceconstrainedscheduling.rs"]
123mod tests;
problemreductions/rules/threepartition_resourceconstrainedscheduling.rs

problemreductions/rules/
threepartition_resourceconstrainedscheduling.rs
