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    source_sum: i64,
24}
25
26impl ReductionResult for ReductionPartitionToBinPacking {
27    type Source = Partition;
28    type Target = BinPacking<i64>;
29
30    fn target_problem(&self) -> &Self::Target {
31        &self.target
32    }
33
34    fn extract_solution(
35        &self,
36        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
37    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
38        crate::rules::traits::validate_target_witness(
39            self.target_problem(),
40            target_solution,
41            |value| crate::rules::AggregateReductionResult::extract_value(self, value).0,
42            "target witness does not certify a YES answer for the source",
43        )?;
44
45        Ok({
46            // BinPacking may use any bin indices (0..n-1). Remap the two distinct
47            // bins used in a 2-bin packing to Partition's {0, 1} assignment.
48            // The first bin encountered maps to 0, the second to 1.
49            let first_bin = target_solution[0];
50            target_solution.iter().map(|&b| b != first_bin).collect()
51        })
52    }
53}
54
55#[crate::aggregate_reduction]
56impl crate::rules::AggregateReductionResult for ReductionPartitionToBinPacking {
57    type Source = Partition;
58    type Target = BinPacking<i64>;
59
60    fn target_problem(&self) -> &Self::Target {
61        &self.target
62    }
63
64    fn extract_value(&self, value: crate::types::Min<i64>) -> crate::types::Or {
65        crate::types::Or(self.source_sum % 2 == 0 && value.0 == Some(2))
66    }
67}
68
69// Capacity is at most max(1, sum(sizes)/2); summing n entries adds at most n bits.
70#[reduction(transform = {
71    exact {
72        num_items = "num_elements",
73    },
74    upper_bound {
75        max_numeric_magnitude_bits = "max_numeric_magnitude_bits + num_elements",
76    },
77})]
78impl ReduceTo<BinPacking<i64>> for Partition {
79    type Result = ReductionPartitionToBinPacking;
80
81    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
82        let sizes = self.sizes().to_vec();
83        // A singleton of size one is NO, but BinPacking requires positive capacity.
84        let capacity = (self.total_sum() / 2).max(1);
85
86        Ok(ReductionPartitionToBinPacking {
87            source_sum: self.total_sum(),
88            target: BinPacking::new(sizes, capacity).map_err(|cause| {
89                crate::rules::ReductionError::construction::<Partition, BinPacking<i64>>(cause)
90            })?,
91        })
92    }
93}
94
95#[cfg(feature = "example-db")]
96pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
97    use crate::export::SolutionPair;
98
99    vec![crate::example_db::specs::RuleExampleSpec {
100        id: "partition_to_binpacking",
101        build: || {
102            crate::example_db::specs::rule_example_with_witness::<_, BinPacking<i64>>(
103                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
104                SolutionPair {
105                    source_config: serde_json::json!(vec![false, true, true, false, true, true]),
106                    target_config: serde_json::json!(vec![0, 1, 1, 0, 1, 1]),
107                },
108            )
109        },
110    }]
111}
112
113#[cfg(test)]
114#[path = "../unit_tests/rules/partition_binpacking.rs"]
115mod tests;
problemreductions/rules/partition_binpacking.rs

problemreductions/rules/
partition_binpacking.rs
