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

problemreductions/rules/
knapsack_qubo.rs
