problemreductions/rules/
subsetsum_closestvectorproblem.rs

1//! Reduction from Subset Sum to Closest Vector Problem.
2
3use crate::models::algebraic::{ClosestVectorProblem, VarBounds};
4use crate::models::misc::SubsetSum;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7use num_bigint::BigUint;
8use num_traits::ToPrimitive;
9
10/// Result of reducing SubsetSum to ClosestVectorProblem.
11#[derive(Debug, Clone)]
12pub struct ReductionSubsetSumToClosestVectorProblem {
13    target: ClosestVectorProblem<i32>,
14}
15
16impl ReductionResult for ReductionSubsetSumToClosestVectorProblem {
17    type Source = SubsetSum;
18    type Target = ClosestVectorProblem<i32>;
19
20    fn target_problem(&self) -> &Self::Target {
21        &self.target
22    }
23
24    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
25        target_solution.to_vec()
26    }
27}
28
29fn biguint_to_i32(value: &BigUint) -> i32 {
30    value
31        .to_i32()
32        .expect("SubsetSum -> ClosestVectorProblem requires all sizes and target to fit in i32")
33}
34
35#[reduction(
36    overhead = {
37        ambient_dimension = "num_elements + 1",
38        num_basis_vectors = "num_elements",
39    }
40)]
41impl ReduceTo<ClosestVectorProblem<i32>> for SubsetSum {
42    type Result = ReductionSubsetSumToClosestVectorProblem;
43
44    fn reduce_to(&self) -> Self::Result {
45        let n = self.num_elements();
46        let mut basis = Vec::with_capacity(n);
47        for (i, size) in self.sizes().iter().enumerate() {
48            let mut column = vec![0i32; n + 1];
49            column[i] = 1;
50            column[n] = biguint_to_i32(size);
51            basis.push(column);
52        }
53
54        let mut target = vec![0.5; n];
55        target.push(biguint_to_i32(self.target()) as f64);
56
57        ReductionSubsetSumToClosestVectorProblem {
58            target: ClosestVectorProblem::new(basis, target, vec![VarBounds::binary(); n]),
59        }
60    }
61}
62
63#[cfg(feature = "example-db")]
64pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
65    use crate::export::SolutionPair;
66
67    vec![crate::example_db::specs::RuleExampleSpec {
68        id: "subsetsum_to_closestvectorproblem",
69        build: || {
70            crate::example_db::specs::rule_example_with_witness::<_, ClosestVectorProblem<i32>>(
71                SubsetSum::new(vec![3u32, 7, 1, 8], 11u32),
72                SolutionPair {
73                    source_config: vec![1, 0, 0, 1],
74                    target_config: vec![1, 0, 0, 1],
75                },
76            )
77        },
78    }]
79}
80
81#[cfg(test)]
82#[path = "../unit_tests/rules/subsetsum_closestvectorproblem.rs"]
83mod tests;
problemreductions/rules/subsetsum_closestvectorproblem.rs

problemreductions/rules/
subsetsum_closestvectorproblem.rs
