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 i32)
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<i32>,
23}
24
25impl ReductionResult for ReductionPartitionToBinPacking {
26    type Source = Partition;
27    type Target = BinPacking<i32>;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
34        // BinPacking may use any bin indices (0..n-1). Remap the two distinct
35        // bins used in a 2-bin packing to Partition's {0, 1} assignment.
36        // The first bin encountered maps to 0, the second to 1.
37        let first_bin = target_solution[0];
38        target_solution
39            .iter()
40            .map(|&b| if b == first_bin { 0 } else { 1 })
41            .collect()
42    }
43}
44
45fn partition_size_to_i32(value: u64) -> i32 {
46    i32::try_from(value)
47        .expect("Partition -> BinPacking requires all sizes and total_sum / 2 to fit in i32")
48}
49
50#[reduction(overhead = {
51    num_items = "num_elements",
52})]
53impl ReduceTo<BinPacking<i32>> for Partition {
54    type Result = ReductionPartitionToBinPacking;
55
56    fn reduce_to(&self) -> Self::Result {
57        let sizes: Vec<i32> = self
58            .sizes()
59            .iter()
60            .copied()
61            .map(partition_size_to_i32)
62            .collect();
63        let capacity = partition_size_to_i32(self.total_sum() / 2);
64
65        ReductionPartitionToBinPacking {
66            target: BinPacking::new(sizes, capacity),
67        }
68    }
69}
70
71#[cfg(feature = "example-db")]
72pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
73    use crate::export::SolutionPair;
74
75    vec![crate::example_db::specs::RuleExampleSpec {
76        id: "partition_to_binpacking",
77        build: || {
78            crate::example_db::specs::rule_example_with_witness::<_, BinPacking<i32>>(
79                Partition::new(vec![3, 1, 1, 2, 2, 1]),
80                SolutionPair {
81                    source_config: vec![0, 1, 1, 0, 1, 1],
82                    target_config: vec![0, 1, 1, 0, 1, 1],
83                },
84            )
85        },
86    }]
87}
88
89#[cfg(test)]
90#[path = "../unit_tests/rules/partition_binpacking.rs"]
91mod tests;
problemreductions/rules/partition_binpacking.rs

problemreductions/rules/
partition_binpacking.rs
