problemreductions/rules/
partition_knapsack.rs

1//! Reduction from Partition to Knapsack.
2
3use crate::models::misc::{Knapsack, Partition};
4use crate::reduction;
5use crate::rules::traits::{ReduceTo, ReductionResult};
6
7/// Result of reducing Partition to Knapsack.
8#[derive(Debug, Clone)]
9pub struct ReductionPartitionToKnapsack {
10    target: Knapsack,
11    source_sum: i64,
12}
13
14impl ReductionResult for ReductionPartitionToKnapsack {
15    type Source = Partition;
16    type Target = Knapsack;
17
18    fn target_problem(&self) -> &Self::Target {
19        &self.target
20    }
21
22    fn extract_solution(
23        &self,
24        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
25    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
26        crate::rules::traits::validate_target_witness(
27            self.target_problem(),
28            target_solution,
29            |value| crate::rules::AggregateReductionResult::extract_value(self, value).0,
30            "target witness does not certify a YES answer for the source",
31        )?;
32
33        Ok(target_solution.to_vec())
34    }
35}
36
37#[crate::aggregate_reduction]
38impl crate::rules::AggregateReductionResult for ReductionPartitionToKnapsack {
39    type Source = Partition;
40    type Target = Knapsack;
41
42    fn target_problem(&self) -> &Self::Target {
43        &self.target
44    }
45
46    fn extract_value(&self, value: crate::types::Max<i64>) -> crate::types::Or {
47        crate::types::Or(self.source_sum % 2 == 0 && value.0 == Some(self.source_sum / 2))
48    }
49}
50
51#[reduction(
52    transform = {
53        exact { num_items = "num_elements" },
54        // The constructor rounds S/2 down; bound evaluation rounds up.
55        upper_bound {
56            capacity = "total_sum / 2",
57            capacity_bits = "max_numeric_magnitude_bits + num_elements",
58        },
59    },
60)]
61impl ReduceTo<Knapsack> for Partition {
62    type Result = ReductionPartitionToKnapsack;
63
64    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
65        let weights = self.sizes().to_vec();
66        let values = weights.clone();
67        let capacity = self.total_sum() / 2;
68
69        Ok(ReductionPartitionToKnapsack {
70            source_sum: self.total_sum(),
71            target: Knapsack::new(weights, values, capacity),
72        })
73    }
74}
75
76#[cfg(feature = "example-db")]
77pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
78    use crate::export::SolutionPair;
79
80    vec![crate::example_db::specs::RuleExampleSpec {
81        id: "partition_to_knapsack",
82        build: || {
83            crate::example_db::specs::rule_example_with_witness::<_, Knapsack>(
84                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
85                SolutionPair {
86                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
87                    target_config: serde_json::json!(vec![true, false, false, true, false, false]),
88                },
89            )
90        },
91    }]
92}
93
94#[cfg(test)]
95#[path = "../unit_tests/rules/partition_knapsack.rs"]
96mod tests;
problemreductions/rules/partition_knapsack.rs

problemreductions/rules/
partition_knapsack.rs
