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})]
40impl ReduceTo<QUBO<i64>> for GraphPartitioning<SimpleGraph> {
41    type Result = ReductionGraphPartitioningToQUBO;
42
43    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
44        let n = self.num_vertices();
45        let overflow = |operation| {
46            crate::rules::ReductionError::integer_overflow::<Self, QUBO<i64>>(operation)
47        };
48        let n_i64 = i64::try_from(n)
49            .map_err(|_| overflow("converting the vertex count to a QUBO coefficient"))?;
50        let edge_count = i64::try_from(self.num_edges())
51            .map_err(|_| overflow("converting the edge count to a QUBO coefficient"))?;
52        let penalty = edge_count
53            .checked_add(1)
54            .ok_or_else(|| overflow("computing the balance penalty"))?;
55        let mut matrix = vec![vec![0i64; n]; n];
56        let mut degrees = vec![0usize; n];
57        let edges = self.graph().edges();
58
59        for &(u, v) in &edges {
60            degrees[u] += 1;
61            degrees[v] += 1;
62        }
63
64        for (i, row) in matrix.iter_mut().enumerate() {
65            let degree = i64::try_from(degrees[i])
66                .map_err(|_| overflow("converting a vertex degree to a QUBO coefficient"))?;
67            let balance_linear = penalty
68                .checked_mul(
69                    1i64.checked_sub(n_i64)
70                        .ok_or_else(|| overflow("computing a balance coefficient"))?,
71                )
72                .ok_or_else(|| overflow("computing a balance coefficient"))?;
73            row[i] = degree
74                .checked_add(balance_linear)
75                .ok_or_else(|| overflow("combining QUBO diagonal coefficients"))?;
76            for value in row.iter_mut().skip(i + 1) {
77                *value = penalty
78                    .checked_mul(2)
79                    .ok_or_else(|| overflow("computing a balance interaction coefficient"))?;
80            }
81        }
82
83        for (u, v) in edges {
84            let (lo, hi) = if u < v { (u, v) } else { (v, u) };
85            matrix[lo][hi] = matrix[lo][hi]
86                .checked_sub(2)
87                .ok_or_else(|| overflow("adding a cut interaction coefficient"))?;
88        }
89
90        Ok(ReductionGraphPartitioningToQUBO {
91            target: QUBO::from_matrix(matrix).map_err(|message| {
92                crate::rules::ReductionError::construction::<
93                    GraphPartitioning<SimpleGraph>,
94                    QUBO<i64>,
95                >(message)
96            })?,
97        })
98    }
99}
100
101#[cfg(feature = "example-db")]
102pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
103    use crate::export::SolutionPair;
104
105    vec![crate::example_db::specs::RuleExampleSpec {
106        id: "graphpartitioning_to_qubo",
107        build: || {
108            crate::example_db::specs::rule_example_with_witness::<_, QUBO<i64>>(
109                GraphPartitioning::new(SimpleGraph::new(
110                    6,
111                    vec![
112                        (0, 1),
113                        (0, 2),
114                        (1, 2),
115                        (1, 3),
116                        (2, 3),
117                        (2, 4),
118                        (3, 4),
119                        (3, 5),
120                        (4, 5),
121                    ],
122                )),
123                SolutionPair {
124                    source_config: serde_json::json!(vec![false, false, false, true, true, true]),
125                    target_config: serde_json::json!(vec![false, false, false, true, true, true]),
126                },
127            )
128        },
129    }]
130}
131
132#[cfg(test)]
133#[path = "../unit_tests/rules/graphpartitioning_qubo.rs"]
134mod tests;
problemreductions/rules/graphpartitioning_qubo.rs

problemreductions/rules/
graphpartitioning_qubo.rs
