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
18fn overflow(operation: &'static str) -> crate::rules::ReductionError {
19    crate::rules::ReductionError::integer_overflow::<Knapsack, QUBO<i64>>(operation)
20}
21
22/// Result of reducing Knapsack to QUBO.
23#[derive(Debug, Clone)]
24pub struct ReductionKnapsackToQUBO {
25    target: QUBO<i64>,
26    num_items: usize,
27}
28
29impl ReductionResult for ReductionKnapsackToQUBO {
30    type Source = Knapsack;
31    type Target = QUBO<i64>;
32
33    fn target_problem(&self) -> &Self::Target {
34        &self.target
35    }
36
37    fn extract_solution(
38        &self,
39        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
40    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
41        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
42
43        Ok(target_solution[..self.num_items].to_vec())
44    }
45}
46
47#[reduction(transform = {
48    exact {
49        num_vars = "num_items + capacity_bits",
50    },
51    upper_bound {
52        num_quadratic_terms = "(num_items + capacity_bits)^2",
53    },
54})]
55impl ReduceTo<QUBO<i64>> for Knapsack {
56    type Result = ReductionKnapsackToQUBO;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        let n = self.num_items();
60        let c = self.capacity();
61        let b = self.num_slack_bits();
62        let total = n + b;
63
64        // Penalty must exceed sum of all values
65        let sum_values = self
66            .values()
67            .iter()
68            .try_fold(0_i64, |total, &value| total.checked_add(value))
69            .ok_or_else(|| {
70                crate::rules::ReductionError::integer_overflow::<Knapsack, QUBO<i64>>(
71                    "summing item values for the QUBO penalty",
72                )
73            })?;
74        let penalty_i64 = sum_values.checked_add(1).ok_or_else(|| {
75            crate::rules::ReductionError::integer_overflow::<Knapsack, QUBO<i64>>(
76                "incrementing the QUBO penalty",
77            )
78        })?;
79        let penalty = penalty_i64;
80        let values = self.values();
81
82        // Build QUBO matrix
83        // H = -sum(v_i * x_i) + P * (sum(w_i * x_i) + sum(2^j * s_j) - C)^2
84        //
85        // Let a_k be the coefficient of variable k in the constraint:
86        //   a_k = w_k for k < n (item variables)
87        //   a_{n+j} = 2^j for j < B (slack variables)
88        //
89        // Expanding the penalty:
90        //   P * (sum(a_k * z_k) - C)^2 = P * sum_i sum_j a_i * a_j * z_i * z_j
91        //                                 - 2P * C * sum(a_k * z_k) + P * C^2
92        // Since z_k is binary, z_k^2 = z_k, so diagonal terms become:
93        //   Q[k][k] = P * a_k^2 - 2P * C * a_k  (from penalty)
94        //   Q[k][k] -= v_k                       (from objective, item vars only)
95        // Off-diagonal terms (i < j):
96        //   Q[i][j] = 2P * a_i * a_j
97
98        let mut coeffs = vec![0_i64; total];
99        for (i, coeff) in coeffs.iter_mut().enumerate().take(n) {
100            *coeff = self.weights()[i];
101        }
102        for j in 0..b {
103            let bit = u32::try_from(j).map_err(|_| {
104                crate::rules::ReductionError::invalid_target::<Knapsack, QUBO<i64>>(
105                    "slack-bit index does not fit u32",
106                )
107            })?;
108            let weight = 1_i64.checked_shl(bit).ok_or_else(|| {
109                crate::rules::ReductionError::integer_overflow::<Knapsack, QUBO<i64>>(
110                    "constructing a slack-bit weight",
111                )
112            })?;
113            coeffs[n + j] = weight;
114        }
115
116        let mut matrix = vec![vec![0_i64; total]; total];
117
118        // Diagonal: P * a_k^2 - 2P * C * a_k - v_k (for items)
119        for k in 0..total {
120            let square = penalty
121                .checked_mul(coeffs[k])
122                .and_then(|value| value.checked_mul(coeffs[k]))
123                .ok_or_else(|| overflow("computing a knapsack QUBO square penalty"))?;
124            let linear = penalty
125                .checked_mul(c)
126                .and_then(|value| value.checked_mul(coeffs[k]))
127                .and_then(|value| value.checked_mul(2))
128                .ok_or_else(|| overflow("computing a knapsack QUBO linear penalty"))?;
129            matrix[k][k] = square
130                .checked_sub(linear)
131                .ok_or_else(|| overflow("combining knapsack QUBO diagonal penalties"))?;
132            if k < n {
133                matrix[k][k] = matrix[k][k]
134                    .checked_sub(values[k])
135                    .ok_or_else(|| overflow("adding a knapsack value to the QUBO objective"))?;
136            }
137        }
138
139        // Off-diagonal (upper triangular): 2P * a_i * a_j
140        for i in 0..total {
141            for j in (i + 1)..total {
142                matrix[i][j] = penalty
143                    .checked_mul(coeffs[i])
144                    .and_then(|value| value.checked_mul(coeffs[j]))
145                    .and_then(|value| value.checked_mul(2))
146                    .ok_or_else(|| overflow("computing a knapsack QUBO interaction"))?;
147            }
148        }
149
150        Ok(ReductionKnapsackToQUBO {
151            target: QUBO::from_matrix(matrix).map_err(|message| {
152                crate::rules::ReductionError::construction::<Knapsack, QUBO<i64>>(message)
153            })?,
154            num_items: n,
155        })
156    }
157}
158
159#[cfg(feature = "example-db")]
160pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
161    use crate::export::SolutionPair;
162
163    vec![crate::example_db::specs::RuleExampleSpec {
164        id: "knapsack_to_qubo",
165        build: || {
166            crate::example_db::specs::rule_example_with_witness::<_, QUBO<i64>>(
167                Knapsack::new(vec![2, 3, 4, 5], vec![3, 4, 5, 7], 7),
168                SolutionPair {
169                    source_config: serde_json::json!(vec![true, false, false, true]),
170                    target_config: serde_json::json!(vec![
171                        true, false, false, true, false, false, false
172                    ]),
173                },
174            )
175        },
176    }]
177}
178
179#[cfg(test)]
180#[path = "../unit_tests/rules/knapsack_qubo.rs"]
181mod tests;
problemreductions/rules/knapsack_qubo.rs

problemreductions/rules/
knapsack_qubo.rs
