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<i64>,
24    num_vertices: usize,
25    num_terminals: usize,
26    edges: Vec<(usize, usize)>,
27}
28
29impl ReductionResult for ReductionMinimumMultiwayCutToQUBO {
30    type Source = MinimumMultiwayCut<SimpleGraph, i64>;
31    type Target = QUBO<i64>;
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(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
44
45        Ok({
46            let k = self.num_terminals;
47            let n = self.num_vertices;
48
49            // For each vertex, find which terminal position it is assigned to
50            let assignments: Vec<usize> = (0..n)
51                .map(|vertex| {
52                    let mut selected =
53                        (0..k).filter(|&terminal| target_solution[vertex * k + terminal]);
54                    match (selected.next(), selected.next()) {
55                        (Some(terminal), None) => Ok(terminal),
56                        _ => Err(crate::rules::ExtractionError::invalid(format!(
57                            "vertex {vertex} does not have exactly one terminal assignment"
58                        ))),
59                    }
60                })
61                .collect::<crate::rules::ExtractionResult<_>>()?;
62
63            // For each edge, output 1 (cut) if endpoints differ, 0 (keep) otherwise
64            self.edges
65                .iter()
66                .map(|&(u, v)| assignments[u] != assignments[v])
67                .collect()
68        })
69    }
70}
71
72#[reduction(transform = exact {
73    num_vars = "num_terminals * num_vertices",
74})]
75impl ReduceTo<QUBO<i64>> for MinimumMultiwayCut<SimpleGraph, i64> {
76    type Result = ReductionMinimumMultiwayCutToQUBO;
77
78    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
79        let n = self.num_vertices();
80        let k = self.num_terminals();
81        let edges = self.graph().edges();
82        let edge_weights = self.edge_weights();
83        let terminals = self.terminals();
84        let overflow = |operation| {
85            crate::rules::ReductionError::integer_overflow::<
86                MinimumMultiwayCut<SimpleGraph, i64>,
87                QUBO<i64>,
88            >(operation)
89        };
90        let nq = n
91            .checked_mul(k)
92            .ok_or_else(|| overflow("computing the number of QUBO variables"))?;
93
94        // Penalty: sum of all edge weights + 1
95        let alpha = edge_weights.iter().try_fold(0i64, |total, &weight| {
96            total
97                .checked_add(
98                    weight
99                        .checked_abs()
100                        .ok_or_else(|| overflow("taking the absolute value of a cut weight"))?,
101                )
102                .ok_or_else(|| overflow("summing absolute cut weights"))
103        })?;
104        let alpha = alpha
105            .checked_add(1)
106            .ok_or_else(|| overflow("computing the partition penalty"))?;
107
108        let mut matrix = vec![vec![0i64; nq]; nq];
109
110        // Helper: add value to upper-triangular position
111        let mut add_upper = |i: usize, j: usize, val: i64| {
112            let (lo, hi) = if i <= j { (i, j) } else { (j, i) };
113            matrix[lo][hi] = matrix[lo][hi]
114                .checked_add(val)
115                .ok_or_else(|| overflow("adding a multiway-cut QUBO coefficient"))?;
116            Ok::<(), crate::rules::ReductionError>(())
117        };
118
119        // H_A: one-hot constraint per vertex
120        // (1 - sum_t x_{u,t})^2 = 1 - sum_t x_{u,t} + 2 * sum_{s<t} x_{u,s} * x_{u,t}
121        // (using x^2 = x for binary variables)
122        for u in 0..n {
123            // Diagonal: -alpha for each terminal position
124            for s in 0..k {
125                add_upper(
126                    u * k + s,
127                    u * k + s,
128                    alpha
129                        .checked_neg()
130                        .ok_or_else(|| overflow("negating the partition penalty"))?,
131                )?;
132            }
133            // Off-diagonal within same vertex: +2*alpha for each pair
134            for s in 0..k {
135                for t in (s + 1)..k {
136                    add_upper(
137                        u * k + s,
138                        u * k + t,
139                        alpha
140                            .checked_mul(2)
141                            .ok_or_else(|| overflow("doubling the partition penalty"))?,
142                    )?;
143                }
144            }
145        }
146
147        // H_A: terminal pinning
148        // For each terminal vertex, penalize assignment to wrong position
149        for (t_pos, &t_vertex) in terminals.iter().enumerate() {
150            for s in 0..k {
151                if s != t_pos {
152                    add_upper(t_vertex * k + s, t_vertex * k + s, alpha)?;
153                }
154            }
155        }
156
157        // H_B: cut cost
158        // For each edge (u,v) with weight w, for each pair of distinct
159        // terminal positions s != t: add w to Q[u*k+s, v*k+t]
160        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
161            let w = edge_weights[edge_idx];
162            for s in 0..k {
163                for t in 0..k {
164                    if s != t {
165                        add_upper(u * k + s, v * k + t, w)?;
166                    }
167                }
168            }
169        }
170
171        Ok(ReductionMinimumMultiwayCutToQUBO {
172            target: QUBO::from_matrix(matrix).map_err(|message| {
173                crate::rules::ReductionError::construction::<
174                    MinimumMultiwayCut<SimpleGraph, i64>,
175                    QUBO<i64>,
176                >(message)
177            })?,
178            num_vertices: n,
179            num_terminals: k,
180            edges,
181        })
182    }
183}
184
185#[cfg(feature = "example-db")]
186pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
187    use crate::export::SolutionPair;
188
189    vec![crate::example_db::specs::RuleExampleSpec {
190        id: "minimummultiwaycut_to_qubo",
191        build: || {
192            use crate::models::algebraic::QUBO;
193            use crate::models::graph::MinimumMultiwayCut;
194            use crate::topology::SimpleGraph;
195            let graph = SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (0, 4), (1, 3)]);
196            let source = MinimumMultiwayCut::new(graph, vec![0, 2, 4], vec![2, 3, 1, 2, 4, 5]);
197            crate::example_db::specs::rule_example_with_witness::<_, QUBO<i64>>(
198                source,
199                SolutionPair {
200                    source_config: serde_json::json!(vec![true, false, false, true, true, false]),
201                    target_config: serde_json::json!(vec![
202                        true, false, false, false, true, false, false, true, false, false, true,
203                        false, false, false, true
204                    ]),
205                },
206            )
207        },
208    }]
209}
210
211#[cfg(test)]
212#[path = "../unit_tests/rules/minimummultiwaycut_qubo.rs"]
213mod tests;
problemreductions/rules/minimummultiwaycut_qubo.rs

problemreductions/rules/
minimummultiwaycut_qubo.rs
