problemreductions/rules/
partition_multiprocessorscheduling.rs

1//! Reduction from Partition to MultiprocessorScheduling.
2//!
3//! Given a Partition instance with sizes A = {a_1, ..., a_n}, construct a
4//! MultiprocessorScheduling instance with:
5//! - Tasks: one per element, with length equal to the element's size
6//! - m = 2 processors
7//! - Deadline D = floor(total_sum / 2)
8//!
9//! A valid partition (two subsets of equal sum) exists iff the tasks can be
10//! scheduled on 2 processors with makespan at most D.
11//!
12//! Solution extraction is the identity: the binary subset assignment in Partition
13//! directly corresponds to the processor assignment in MultiprocessorScheduling.
14
15use crate::models::misc::{MultiprocessorScheduling, Partition};
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18
19/// Result of reducing Partition to MultiprocessorScheduling.
20#[derive(Debug, Clone)]
21pub struct ReductionPartitionToMPS {
22    target: MultiprocessorScheduling,
23}
24
25impl ReductionResult for ReductionPartitionToMPS {
26    type Source = Partition;
27    type Target = MultiprocessorScheduling;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    /// Solution extraction: identity mapping.
34    /// Partition config (0/1 for subset) maps directly to processor assignment (0/1).
35    fn extract_solution(
36        &self,
37        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
38    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
39        crate::rules::traits::validate_target_witness(
40            self.target_problem(),
41            target_solution,
42            |value| value.0,
43            "target witness does not satisfy the target problem",
44        )?;
45
46        Ok(target_solution
47            .iter()
48            .map(|&processor| processor == 1)
49            .collect())
50    }
51}
52
53#[crate::aggregate_reduction(identity)]
54impl crate::rules::AggregateReductionResult for ReductionPartitionToMPS {}
55
56#[reduction(
57    transform = {
58        exact {
59            num_tasks = "num_elements",
60            num_processors = "2",
61        },
62        upper_bound {
63            max_numeric_magnitude_bits = "max_numeric_magnitude_bits + num_elements",
64        },
65    }
66)]
67impl ReduceTo<MultiprocessorScheduling> for Partition {
68    type Result = ReductionPartitionToMPS;
69
70    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
71        let lengths: Vec<i64> = self.sizes().to_vec();
72        let deadline = self.total_sum() / 2;
73
74        Ok(ReductionPartitionToMPS {
75            target: MultiprocessorScheduling::new(lengths, 2, deadline),
76        })
77    }
78}
79
80#[cfg(feature = "example-db")]
81pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
82    use crate::export::SolutionPair;
83
84    vec![crate::example_db::specs::RuleExampleSpec {
85        id: "partition_to_multiprocessorscheduling",
86        build: || {
87            // sizes [1, 2, 3, 4], sum=10, target=5
88            // partition: {1,4} on proc 0 and {2,3} on proc 1
89            crate::example_db::specs::rule_example_with_witness::<_, MultiprocessorScheduling>(
90                Partition::new(vec![1, 2, 3, 4]).unwrap(),
91                SolutionPair {
92                    source_config: serde_json::json!(vec![false, true, true, false]),
93                    target_config: serde_json::json!(vec![0, 1, 1, 0]),
94                },
95            )
96        },
97    }]
98}
99
100#[cfg(test)]
101#[path = "../unit_tests/rules/partition_multiprocessorscheduling.rs"]
102mod tests;
problemreductions/rules/partition_multiprocessorscheduling.rs

problemreductions/rules/
partition_multiprocessorscheduling.rs
