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(
44    transform = exact {
45        num_vars = "num_sets",
46    }
47)]
48impl ReduceTo<QUBO<f64>> for MaximumSetPacking<f64> {
49    type Result = ReductionSPToQUBO;
50
51    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
52        let n = self.num_sets();
53        let weights = self.weights_ref();
54        // Doubling gives a strict margin even where adding 1.0 would round
55        // back to the original weight. Do not let negative weights cancel it.
56        let max_weight = weights.iter().copied().fold(1.0_f64, f64::max);
57        let penalty = 2.0 * max_weight;
58        if !penalty.is_finite() {
59            return Err(crate::rules::ReductionError::non_finite_result::<
60                MaximumSetPacking<f64>,
61                QUBO<f64>,
62            >("computing the set-packing conflict penalty"));
63        }
64
65        let mut matrix = vec![vec![0.0; n]; n];
66
67        // Diagonal: -w_i
68        for i in 0..n {
69            matrix[i][i] = -weights[i];
70        }
71
72        // Off-diagonal: P for overlapping pairs
73        for (i, j) in self.overlapping_pairs() {
74            let (a, b) = if i < j { (i, j) } else { (j, i) };
75            matrix[a][b] += penalty;
76        }
77
78        Ok(ReductionSPToQUBO {
79            target: QUBO::from_matrix(matrix).map_err(|message| {
80                crate::rules::ReductionError::construction::<MaximumSetPacking<f64>, QUBO<f64>>(
81                    message,
82                )
83            })?,
84        })
85    }
86}
87
88#[cfg(feature = "example-db")]
89pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
90    use crate::export::SolutionPair;
91    use crate::models::set::MaximumSetPacking;
92
93    vec![crate::example_db::specs::RuleExampleSpec {
94        id: "maximumsetpacking_to_qubo",
95        build: || {
96            let source = MaximumSetPacking::<f64>::new(vec![
97                vec![0, 1, 2],
98                vec![2, 3, 4],
99                vec![4, 5, 6],
100                vec![6, 7, 0],
101                vec![1, 3, 5],
102                vec![0, 4, 7],
103            ]);
104            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
105                source,
106                SolutionPair {
107                    source_config: serde_json::json!(vec![false, false, false, true, true, false]),
108                    target_config: serde_json::json!(vec![false, false, false, true, true, false]),
109                },
110            )
111        },
112    }]
113}
114
115#[cfg(test)]
116#[path = "../unit_tests/rules/maximumsetpacking_qubo.rs"]
117mod tests;
problemreductions/rules/maximumsetpacking_qubo.rs

problemreductions/rules/
maximumsetpacking_qubo.rs
