problemreductions/rules/
partition_binpacking.rs

1//! Reduction from Partition to BinPacking.
2//!
3//! Given a Partition instance with sizes A = {a_1, ..., a_n} and total sum S,
4//! construct a BinPacking instance with:
5//! - Items: same sizes (cast from u64 to i64)
6//! - Bin capacity: floor(S / 2)
7//!
8//! A valid partition (two subsets of equal sum) exists iff all items can be
9//! packed into exactly 2 bins of capacity S/2. If S is odd, 2 bins of capacity
10//! floor(S/2) cannot hold all items, so the answer is NO for both problems.
11//!
12//! Solution extraction is the identity: the binary subset assignment in Partition
13//! directly corresponds to the bin assignment in BinPacking.
14
15use crate::models::misc::{BinPacking, Partition};
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18
19/// Result of reducing Partition to BinPacking.
20#[derive(Debug, Clone)]
21pub struct ReductionPartitionToBinPacking {
22    target: BinPacking<i64>,
23}
24
25impl ReductionResult for ReductionPartitionToBinPacking {
26    type Source = Partition;
27    type Target = BinPacking<i64>;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
38
39        Ok({
40            // BinPacking may use any bin indices (0..n-1). Remap the two distinct
41            // bins used in a 2-bin packing to Partition's {0, 1} assignment.
42            // The first bin encountered maps to 0, the second to 1.
43            let first_bin = target_solution[0];
44            target_solution.iter().map(|&b| b != first_bin).collect()
45        })
46    }
47}
48
49#[reduction(
50    transform = exact {
51        num_items = "num_elements",
52    })]
53impl ReduceTo<BinPacking<i64>> for Partition {
54    type Result = ReductionPartitionToBinPacking;
55
56    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
57        let sizes = self.sizes().to_vec();
58        let capacity = self.total_sum() / 2;
59
60        Ok(ReductionPartitionToBinPacking {
61            target: BinPacking::new(sizes, capacity).map_err(|cause| {
62                crate::rules::ReductionError::construction::<Partition, BinPacking<i64>>(cause)
63            })?,
64        })
65    }
66}
67
68#[cfg(feature = "example-db")]
69pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
70    use crate::export::SolutionPair;
71
72    vec![crate::example_db::specs::RuleExampleSpec {
73        id: "partition_to_binpacking",
74        build: || {
75            crate::example_db::specs::rule_example_with_witness::<_, BinPacking<i64>>(
76                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
77                SolutionPair {
78                    source_config: serde_json::json!(vec![false, true, true, false, true, true]),
79                    target_config: serde_json::json!(vec![0, 1, 1, 0, 1, 1]),
80                },
81            )
82        },
83    }]
84}
85
86#[cfg(test)]
87#[path = "../unit_tests/rules/partition_binpacking.rs"]
88mod tests;
problemreductions/rules/partition_binpacking.rs

problemreductions/rules/
partition_binpacking.rs
