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, with
8//! P = 2 max(1, max_i w_i). Negative and zero weights are allowed.
9//!
10//! If a selected set i conflicts with d >= 1 selected sets, removing it changes
11//! the energy by w_i - P*d < 0. Thus every minimizer is a packing. On packings,
12//! the energy is exactly the negative total weight, preserving every optimum.
13
14use crate::models::algebraic::QUBO;
15use crate::models::set::MaximumSetPacking;
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18
19/// Result of reducing `MaximumSetPacking<f64>` to `QUBO<f64>`.
20#[derive(Debug, Clone)]
21pub struct ReductionSPToQUBO {
22    target: QUBO<f64>,
23}
24
25impl ReductionResult for ReductionSPToQUBO {
26    type Source = MaximumSetPacking<f64>;
27    type Target = QUBO<f64>;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
38
39        Ok(target_solution.to_vec())
40    }
41}
42
43#[reduction(transform = {
44    exact {
45        num_vars = "num_sets",
46    },
47    upper_bound {
48        num_quadratic_terms = "num_sets * (num_sets - 1) / 2",
49    },
50})]
51impl ReduceTo<QUBO<f64>> for MaximumSetPacking<f64> {
52    type Result = ReductionSPToQUBO;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let n = self.num_sets();
56        let weights = self.weights_ref();
57        // Doubling gives a strict margin even where adding 1.0 would round
58        // back to the original weight. Do not let negative weights cancel it.
59        let max_weight = weights.iter().copied().fold(1.0_f64, f64::max);
60        let penalty = 2.0 * max_weight;
61        if !penalty.is_finite() {
62            return Err(crate::rules::ReductionError::non_finite_result::<
63                MaximumSetPacking<f64>,
64                QUBO<f64>,
65            >("computing the set-packing conflict penalty"));
66        }
67
68        let mut matrix = vec![vec![0.0; n]; n];
69
70        // Diagonal: -w_i
71        for i in 0..n {
72            matrix[i][i] = -weights[i];
73        }
74
75        // Off-diagonal: P for overlapping pairs
76        for (i, j) in self.overlapping_pairs() {
77            let (a, b) = if i < j { (i, j) } else { (j, i) };
78            matrix[a][b] += penalty;
79        }
80
81        Ok(ReductionSPToQUBO {
82            target: QUBO::from_matrix(matrix).map_err(|message| {
83                crate::rules::ReductionError::construction::<MaximumSetPacking<f64>, QUBO<f64>>(
84                    message,
85                )
86            })?,
87        })
88    }
89}
90
91#[cfg(feature = "example-db")]
92pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
93    use crate::export::SolutionPair;
94    use crate::models::set::MaximumSetPacking;
95
96    vec![crate::example_db::specs::RuleExampleSpec {
97        id: "maximumsetpacking_to_qubo",
98        build: || {
99            let source = MaximumSetPacking::<f64>::new(vec![
100                vec![0, 1, 2],
101                vec![2, 3, 4],
102                vec![4, 5, 6],
103                vec![6, 7, 0],
104                vec![1, 3, 5],
105                vec![0, 4, 7],
106            ]);
107            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
108                source,
109                SolutionPair {
110                    source_config: serde_json::json!(vec![false, false, false, true, true, false]),
111                    target_config: serde_json::json!(vec![false, false, false, true, true, false]),
112                },
113            )
114        },
115    }]
116}
117
118#[cfg(test)]
119#[path = "../unit_tests/rules/maximumsetpacking_qubo.rs"]
120mod tests;
problemreductions/rules/maximumsetpacking_qubo.rs

problemreductions/rules/
maximumsetpacking_qubo.rs
