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(feature = "example-db")]
65pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
66    use crate::export::SolutionPair;
67    use crate::models::set::MaximumSetPacking;
68
69    vec![crate::example_db::specs::RuleExampleSpec {
70        id: "maximumsetpacking_to_qubo",
71        build: || {
72            let source = MaximumSetPacking::<f64>::new(vec![
73                vec![0, 1, 2],
74                vec![2, 3, 4],
75                vec![4, 5, 6],
76                vec![6, 7, 0],
77                vec![1, 3, 5],
78                vec![0, 4, 7],
79            ]);
80            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
81                source,
82                SolutionPair {
83                    source_config: vec![0, 0, 0, 1, 1, 0],
84                    target_config: vec![0, 0, 0, 1, 1, 0],
85                },
86            )
87        },
88    }]
89}
90
91#[cfg(test)]
92#[path = "../unit_tests/rules/maximumsetpacking_qubo.rs"]
93mod tests;
problemreductions/rules/maximumsetpacking_qubo.rs

problemreductions/rules/
maximumsetpacking_qubo.rs
