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

problemreductions/rules/
minimummultiwaycut_qubo.rs
