problemreductions/rules/
minimummultiwaycut_qubo.rs

1//! Reduction from MinimumMultiwayCut to QUBO.
2//!
3//! Variable mapping: k*n binary variables x_{u,t} for each vertex u and
4//! terminal position t. x_{u,t} = 1 means vertex u is assigned to terminal t's
5//! component. Variable index: u * k + t.
6//!
7//! QUBO Hamiltonian: H = H_A + H_B
8//!
9//! H_A enforces valid partition (one-hot per vertex) and terminal pinning.
10//! H_B encodes the cut cost objective.
11//!
12//! Reference: Heidari, Dinneen & Delmas (2022).
13
14use crate::models::algebraic::QUBO;
15use crate::models::graph::MinimumMultiwayCut;
16use crate::reduction;
17use crate::rules::traits::{ReduceTo, ReductionResult};
18use crate::topology::{Graph, SimpleGraph};
19
20/// Result of reducing MinimumMultiwayCut to QUBO.
21#[derive(Debug, Clone)]
22pub struct ReductionMinimumMultiwayCutToQUBO {
23    target: QUBO<f64>,
24    num_vertices: usize,
25    num_terminals: usize,
26    edges: Vec<(usize, usize)>,
27}
28
29impl ReductionResult for ReductionMinimumMultiwayCutToQUBO {
30    type Source = MinimumMultiwayCut<SimpleGraph, i32>;
31    type Target = QUBO<f64>;
32
33    fn target_problem(&self) -> &Self::Target {
34        &self.target
35    }
36
37    /// Decode one-hot assignment: for each vertex find its terminal, then
38    /// for each edge check if endpoints are in different terminals.
39    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
40        let k = self.num_terminals;
41        let n = self.num_vertices;
42
43        // For each vertex, find which terminal position it is assigned to
44        let assignments: Vec<usize> = (0..n)
45            .map(|u| {
46                (0..k)
47                    .find(|&t| target_solution[u * k + t] == 1)
48                    .unwrap_or(0)
49            })
50            .collect();
51
52        // For each edge, output 1 (cut) if endpoints differ, 0 (keep) otherwise
53        self.edges
54            .iter()
55            .map(|&(u, v)| {
56                if assignments[u] != assignments[v] {
57                    1
58                } else {
59                    0
60                }
61            })
62            .collect()
63    }
64}
65
66#[reduction(overhead = { num_vars = "num_terminals * num_vertices" })]
67impl ReduceTo<QUBO<f64>> for MinimumMultiwayCut<SimpleGraph, i32> {
68    type Result = ReductionMinimumMultiwayCutToQUBO;
69
70    fn reduce_to(&self) -> Self::Result {
71        let n = self.num_vertices();
72        let k = self.num_terminals();
73        let edges = self.graph().edges();
74        let edge_weights = self.edge_weights();
75        let terminals = self.terminals();
76        let nq = n * k;
77
78        // Penalty: sum of all edge weights + 1
79        let alpha: f64 = edge_weights.iter().map(|&w| (w as f64).abs()).sum::<f64>() + 1.0;
80
81        let mut matrix = vec![vec![0.0f64; nq]; nq];
82
83        // Helper: add value to upper-triangular position
84        let mut add_upper = |i: usize, j: usize, val: f64| {
85            let (lo, hi) = if i <= j { (i, j) } else { (j, i) };
86            matrix[lo][hi] += val;
87        };
88
89        // H_A: one-hot constraint per vertex
90        // (1 - sum_t x_{u,t})^2 = 1 - sum_t x_{u,t} + 2 * sum_{s<t} x_{u,s} * x_{u,t}
91        // (using x^2 = x for binary variables)
92        for u in 0..n {
93            // Diagonal: -alpha for each terminal position
94            for s in 0..k {
95                add_upper(u * k + s, u * k + s, -alpha);
96            }
97            // Off-diagonal within same vertex: +2*alpha for each pair
98            for s in 0..k {
99                for t in (s + 1)..k {
100                    add_upper(u * k + s, u * k + t, 2.0 * alpha);
101                }
102            }
103        }
104
105        // H_A: terminal pinning
106        // For each terminal vertex, penalize assignment to wrong position
107        for (t_pos, &t_vertex) in terminals.iter().enumerate() {
108            for s in 0..k {
109                if s != t_pos {
110                    add_upper(t_vertex * k + s, t_vertex * k + s, alpha);
111                }
112            }
113        }
114
115        // H_B: cut cost
116        // For each edge (u,v) with weight w, for each pair of distinct
117        // terminal positions s != t: add w to Q[u*k+s, v*k+t]
118        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
119            let w = edge_weights[edge_idx] as f64;
120            for s in 0..k {
121                for t in 0..k {
122                    if s != t {
123                        add_upper(u * k + s, v * k + t, w);
124                    }
125                }
126            }
127        }
128
129        ReductionMinimumMultiwayCutToQUBO {
130            target: QUBO::from_matrix(matrix),
131            num_vertices: n,
132            num_terminals: k,
133            edges,
134        }
135    }
136}
137
138#[cfg(feature = "example-db")]
139pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
140    use crate::export::SolutionPair;
141
142    vec![crate::example_db::specs::RuleExampleSpec {
143        id: "minimummultiwaycut_to_qubo",
144        build: || {
145            use crate::models::algebraic::QUBO;
146            use crate::models::graph::MinimumMultiwayCut;
147            use crate::topology::SimpleGraph;
148            let graph = SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (0, 4), (1, 3)]);
149            let source = MinimumMultiwayCut::new(graph, vec![0, 2, 4], vec![2, 3, 1, 2, 4, 5]);
150            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
151                source,
152                SolutionPair {
153                    source_config: vec![1, 0, 0, 1, 1, 0],
154                    target_config: vec![1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1],
155                },
156            )
157        },
158    }]
159}
160
161#[cfg(test)]
162#[path = "../unit_tests/rules/minimummultiwaycut_qubo.rs"]
163mod tests;
problemreductions/rules/minimummultiwaycut_qubo.rs

problemreductions/rules/
minimummultiwaycut_qubo.rs
