problemreductions/rules/
knapsack_qubo.rs

1//! Reduction from Knapsack to QUBO.
2//!
3//! Converts a nonnegative 0-1 Knapsack instance into QUBO by turning the
4//! capacity inequality sum(w_i * x_i) <= C into equality using binary slack
5//! variables, then constructing a QUBO that combines the objective
6//! -sum(v_i * x_i) with a quadratic penalty
7//! P * (sum(w_i * x_i) + sum(2^j * s_j) - C)^2.
8//! For nonnegative values, penalty P > sum(v_i) ensures any infeasible solution
9//! costs more than any feasible one.
10//!
11//! Reference: Lucas, 2014, "Ising formulations of many NP problems".
12
13use crate::models::algebraic::QUBO;
14use crate::models::misc::Knapsack;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17
18/// Result of reducing Knapsack to QUBO.
19#[derive(Debug, Clone)]
20pub struct ReductionKnapsackToQUBO {
21    target: QUBO<f64>,
22    num_items: usize,
23}
24
25impl ReductionResult for ReductionKnapsackToQUBO {
26    type Source = Knapsack;
27    type Target = QUBO<f64>;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
34        target_solution[..self.num_items].to_vec()
35    }
36}
37
38#[reduction(overhead = { num_vars = "num_items + num_slack_bits" })]
39impl ReduceTo<QUBO<f64>> for Knapsack {
40    type Result = ReductionKnapsackToQUBO;
41
42    fn reduce_to(&self) -> Self::Result {
43        let n = self.num_items();
44        let c = self.capacity();
45        let b = self.num_slack_bits();
46        let total = n + b;
47
48        // Penalty must exceed sum of all values
49        let sum_values: i64 = self.values().iter().sum();
50        let penalty = (sum_values + 1) as f64;
51
52        // Build QUBO matrix
53        // H = -sum(v_i * x_i) + P * (sum(w_i * x_i) + sum(2^j * s_j) - C)^2
54        //
55        // Let a_k be the coefficient of variable k in the constraint:
56        //   a_k = w_k for k < n (item variables)
57        //   a_{n+j} = 2^j for j < B (slack variables)
58        //
59        // Expanding the penalty:
60        //   P * (sum(a_k * z_k) - C)^2 = P * sum_i sum_j a_i * a_j * z_i * z_j
61        //                                 - 2P * C * sum(a_k * z_k) + P * C^2
62        // Since z_k is binary, z_k^2 = z_k, so diagonal terms become:
63        //   Q[k][k] = P * a_k^2 - 2P * C * a_k  (from penalty)
64        //   Q[k][k] -= v_k                       (from objective, item vars only)
65        // Off-diagonal terms (i < j):
66        //   Q[i][j] = 2P * a_i * a_j
67
68        let mut coeffs = vec![0.0f64; total];
69        for (i, coeff) in coeffs.iter_mut().enumerate().take(n) {
70            *coeff = self.weights()[i] as f64;
71        }
72        for j in 0..b {
73            coeffs[n + j] = (1u64 << j) as f64;
74        }
75
76        let c_f = c as f64;
77        let mut matrix = vec![vec![0.0f64; total]; total];
78
79        // Diagonal: P * a_k^2 - 2P * C * a_k - v_k (for items)
80        for k in 0..total {
81            matrix[k][k] = penalty * coeffs[k] * coeffs[k] - 2.0 * penalty * c_f * coeffs[k];
82            if k < n {
83                matrix[k][k] -= self.values()[k] as f64;
84            }
85        }
86
87        // Off-diagonal (upper triangular): 2P * a_i * a_j
88        for i in 0..total {
89            for j in (i + 1)..total {
90                matrix[i][j] = 2.0 * penalty * coeffs[i] * coeffs[j];
91            }
92        }
93
94        ReductionKnapsackToQUBO {
95            target: QUBO::from_matrix(matrix),
96            num_items: n,
97        }
98    }
99}
100
101#[cfg(feature = "example-db")]
102pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
103    use crate::export::SolutionPair;
104
105    vec![crate::example_db::specs::RuleExampleSpec {
106        id: "knapsack_to_qubo",
107        build: || {
108            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
109                Knapsack::new(vec![2, 3, 4, 5], vec![3, 4, 5, 7], 7),
110                SolutionPair {
111                    source_config: vec![1, 0, 0, 1],
112                    target_config: vec![1, 0, 0, 1, 0, 0, 0],
113                },
114            )
115        },
116    }]
117}
118
119#[cfg(test)]
120#[path = "../unit_tests/rules/knapsack_qubo.rs"]
121mod tests;
problemreductions/rules/knapsack_qubo.rs

problemreductions/rules/
knapsack_qubo.rs
