problemreductions/rules/
maximumsetpacking_qubo.rs

1//! Reduction from MaximumSetPacking to QUBO.
2//!
3//! Same structure as MaximumIndependentSet on the intersection graph:
4//! Maximize Σ w_i·x_i s.t. x_i·x_j = 0 for overlapping pairs (i,j).
5//! = Minimize -Σ w_i·x_i + P·Σ_{overlapping (i,j)} x_i·x_j
6//!
7//! Q[i][i] = -w_i, Q[i][j] = P for overlapping pairs. P = 1 + Σ w_i.
8
9use crate::models::algebraic::QUBO;
10use crate::models::set::MaximumSetPacking;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13
14/// Result of reducing `MaximumSetPacking<f64>` to `QUBO<f64>`.
15#[derive(Debug, Clone)]
16pub struct ReductionSPToQUBO {
17    target: QUBO<f64>,
18}
19
20impl ReductionResult for ReductionSPToQUBO {
21    type Source = MaximumSetPacking<f64>;
22    type Target = QUBO<f64>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
29        target_solution.to_vec()
30    }
31}
32
33#[reduction(
34    overhead = { num_vars = "num_sets" }
35)]
36impl ReduceTo<QUBO<f64>> for MaximumSetPacking<f64> {
37    type Result = ReductionSPToQUBO;
38
39    fn reduce_to(&self) -> Self::Result {
40        let n = self.num_sets();
41        let weights = self.weights_ref();
42        let total_weight: f64 = weights.iter().sum();
43        let penalty = 1.0 + total_weight;
44
45        let mut matrix = vec![vec![0.0; n]; n];
46
47        // Diagonal: -w_i
48        for i in 0..n {
49            matrix[i][i] = -weights[i];
50        }
51
52        // Off-diagonal: P for overlapping pairs
53        for (i, j) in self.overlapping_pairs() {
54            let (a, b) = if i < j { (i, j) } else { (j, i) };
55            matrix[a][b] += penalty;
56        }
57
58        ReductionSPToQUBO {
59            target: QUBO::from_matrix(matrix),
60        }
61    }
62}
63
64#[cfg(test)]
65#[path = "../unit_tests/rules/maximumsetpacking_qubo.rs"]
66mod tests;
problemreductions/rules/maximumsetpacking_qubo.rs

problemreductions/rules/
maximumsetpacking_qubo.rs
