problemreductions/rules/
graphpartitioning_qubo.rs

1//! Reduction from GraphPartitioning to QUBO.
2//!
3//! Uses the penalty-method QUBO
4//! H = sum_(u,v in E) (x_u + x_v - 2 x_u x_v) + P (sum_i x_i - n/2)^2
5//! with P = |E| + 1 so any imbalanced partition is dominated by a balanced one.
6
7use crate::models::algebraic::QUBO;
8use crate::models::graph::GraphPartitioning;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12
13/// Result of reducing GraphPartitioning to QUBO.
14#[derive(Debug, Clone)]
15pub struct ReductionGraphPartitioningToQUBO {
16    target: QUBO<i64>,
17}
18
19impl ReductionResult for ReductionGraphPartitioningToQUBO {
20    type Source = GraphPartitioning<SimpleGraph>;
21    type Target = QUBO<i64>;
22
23    fn target_problem(&self) -> &Self::Target {
24        &self.target
25    }
26
27    fn extract_solution(
28        &self,
29        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
30    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
31        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
32
33        Ok(target_solution.to_vec())
34    }
35}
36
37#[reduction(transform = exact {
38    num_vars = "num_vertices",
39    num_quadratic_terms = "num_vertices * (num_vertices - 1) / 2",
40})]
41impl ReduceTo<QUBO<i64>> for GraphPartitioning<SimpleGraph> {
42    type Result = ReductionGraphPartitioningToQUBO;
43
44    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
45        let n = self.num_vertices();
46        let overflow = |operation| {
47            crate::rules::ReductionError::integer_overflow::<Self, QUBO<i64>>(operation)
48        };
49        let n_i64 = i64::try_from(n)
50            .map_err(|_| overflow("converting the vertex count to a QUBO coefficient"))?;
51        let edge_count = i64::try_from(self.num_edges())
52            .map_err(|_| overflow("converting the edge count to a QUBO coefficient"))?;
53        let penalty = edge_count
54            .checked_add(1)
55            .ok_or_else(|| overflow("computing the balance penalty"))?;
56        let mut matrix = vec![vec![0i64; n]; n];
57        let mut degrees = vec![0usize; n];
58        let edges = self.graph().edges();
59
60        for &(u, v) in &edges {
61            degrees[u] += 1;
62            degrees[v] += 1;
63        }
64
65        for (i, row) in matrix.iter_mut().enumerate() {
66            let degree = i64::try_from(degrees[i])
67                .map_err(|_| overflow("converting a vertex degree to a QUBO coefficient"))?;
68            let balance_linear = penalty
69                .checked_mul(
70                    1i64.checked_sub(n_i64)
71                        .ok_or_else(|| overflow("computing a balance coefficient"))?,
72                )
73                .ok_or_else(|| overflow("computing a balance coefficient"))?;
74            row[i] = degree
75                .checked_add(balance_linear)
76                .ok_or_else(|| overflow("combining QUBO diagonal coefficients"))?;
77            for value in row.iter_mut().skip(i + 1) {
78                *value = penalty
79                    .checked_mul(2)
80                    .ok_or_else(|| overflow("computing a balance interaction coefficient"))?;
81            }
82        }
83
84        for (u, v) in edges {
85            let (lo, hi) = if u < v { (u, v) } else { (v, u) };
86            matrix[lo][hi] = matrix[lo][hi]
87                .checked_sub(2)
88                .ok_or_else(|| overflow("adding a cut interaction coefficient"))?;
89        }
90
91        Ok(ReductionGraphPartitioningToQUBO {
92            target: QUBO::from_matrix(matrix).map_err(|message| {
93                crate::rules::ReductionError::construction::<
94                    GraphPartitioning<SimpleGraph>,
95                    QUBO<i64>,
96                >(message)
97            })?,
98        })
99    }
100}
101
102#[cfg(feature = "example-db")]
103pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
104    use crate::export::SolutionPair;
105
106    vec![crate::example_db::specs::RuleExampleSpec {
107        id: "graphpartitioning_to_qubo",
108        build: || {
109            crate::example_db::specs::rule_example_with_witness::<_, QUBO<i64>>(
110                GraphPartitioning::new(SimpleGraph::new(
111                    6,
112                    vec![
113                        (0, 1),
114                        (0, 2),
115                        (1, 2),
116                        (1, 3),
117                        (2, 3),
118                        (2, 4),
119                        (3, 4),
120                        (3, 5),
121                        (4, 5),
122                    ],
123                )),
124                SolutionPair {
125                    source_config: serde_json::json!(vec![false, false, false, true, true, true]),
126                    target_config: serde_json::json!(vec![false, false, false, true, true, true]),
127                },
128            )
129        },
130    }]
131}
132
133#[cfg(test)]
134#[path = "../unit_tests/rules/graphpartitioning_qubo.rs"]
135mod tests;
problemreductions/rules/graphpartitioning_qubo.rs

problemreductions/rules/
graphpartitioning_qubo.rs
