problemreductions/rules/
minimummultiwaycut_ilp.rs

1//! Reduction from MinimumMultiwayCut to ILP (Integer Linear Programming).
2//!
3//! Uses the standard vertex-assignment + edge-cut indicator formulation
4//! (Chopra & Owen, 1996):
5//! - Variables: `y_{iv}` (vertex v in component i) + `x_e` (edge e in cut), all binary
6//! - Constraints: partition (each vertex in exactly one component) + edge-cut linking
7//! - Objective: minimize total weight of cut edges
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::MinimumMultiwayCut;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14
15/// Result of reducing MinimumMultiwayCut to ILP.
16///
17/// Variable layout (all binary):
18/// - `y_{iv}` for i=0..k-1, v=0..n-1: vertex v assigned to component of terminal t_i
19///   (index: i*n + v)
20/// - `x_e` for e=0..m-1: edge e is in the cut (index: k*n + e)
21///
22/// Total: kn + m variables.
23#[derive(Debug, Clone)]
24pub struct ReductionMMCToILP {
25    target: ILP<bool>,
26    /// Number of vertices in the source graph.
27    n: usize,
28    /// Number of edges in the source graph.
29    m: usize,
30    /// Number of terminals.
31    k: usize,
32}
33
34impl ReductionResult for ReductionMMCToILP {
35    type Source = MinimumMultiwayCut<SimpleGraph, i64>;
36    type Target = ILP<bool>;
37
38    fn target_problem(&self) -> &ILP<bool> {
39        &self.target
40    }
41
42    /// Extract solution from ILP back to MinimumMultiwayCut.
43    ///
44    /// For each edge e, source config[e] = target_solution[k*n + e] (the x_e variable).
45    fn extract_solution(
46        &self,
47        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
48    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
49        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
50
51        Ok({
52            let offset = self.k * self.n;
53            (0..self.m)
54                .map(|e| target_solution[offset + e] == 1)
55                .collect()
56        })
57    }
58}
59
60#[reduction(transform = {
61    exact {
62        num_vars = "num_terminals * num_vertices + num_edges",
63        num_constraints = "num_vertices + 2 * num_terminals * num_edges + num_terminals * num_terminals",
64    },
65    upper_bound {
66        max_constraint_magnitude_bits = "1",
67        num_nonzeros = "(num_terminals * num_vertices + num_edges) * (num_vertices + 2 * num_terminals * num_edges + num_terminals * num_terminals)",
68    },
69})]
70impl ReduceTo<ILP<bool>> for MinimumMultiwayCut<SimpleGraph, i64> {
71    type Result = ReductionMMCToILP;
72
73    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
74        let n = self.num_vertices();
75        let m = self.num_edges();
76        let k = self.num_terminals();
77        let terminals = self.terminals();
78        let edges = self.graph().edges();
79        let weights = self.edge_weights();
80        let num_vars = k * n + m;
81
82        // Terminal fixing constraints: k constraints for y_{i,t_i} = 1,
83        // and k*(k-1) constraints for y_{j,t_i} = 0 where j != i.
84        // Total terminal fixes: k + k*(k-1) = k^2.
85        let num_terminal_fixes = k * k;
86        let num_constraints = n + 2 * k * m + num_terminal_fixes;
87        let mut constraints = Vec::with_capacity(num_constraints);
88
89        // Terminal fixing: y_{i, t_i} = 1 for each terminal i
90        for (i, &t) in terminals.iter().enumerate() {
91            constraints.push(LinearConstraint::eq(vec![(i * n + t, 1)], 1));
92        }
93
94        // Terminal fixing: y_{j, t_i} = 0 for j != i
95        for (i, &t) in terminals.iter().enumerate() {
96            for j in 0..k {
97                if j != i {
98                    constraints.push(LinearConstraint::eq(vec![(j * n + t, 1)], 0));
99                }
100            }
101        }
102
103        // Partition constraints: sum_i y_{iv} = 1 for each vertex v
104        for v in 0..n {
105            let terms: Vec<(usize, i64)> = (0..k).map(|i| (i * n + v, 1)).collect();
106            constraints.push(LinearConstraint::eq(terms, 1));
107        }
108
109        // Edge-cut linking constraints: for each edge e=(u,v) and each terminal i:
110        //   x_e >= y_{iu} - y_{iv}  =>  x_e - y_{iu} + y_{iv} >= 0
111        //   x_e >= y_{iv} - y_{iu}  =>  x_e + y_{iu} - y_{iv} >= 0
112        for (e_idx, (u, v)) in edges.iter().enumerate() {
113            let x_var = k * n + e_idx;
114            for i in 0..k {
115                let y_iu = i * n + u;
116                let y_iv = i * n + v;
117                // x_e - y_{iu} + y_{iv} >= 0
118                constraints.push(LinearConstraint::ge(
119                    vec![(x_var, 1), (y_iu, -1), (y_iv, 1)],
120                    0,
121                ));
122                // x_e + y_{iu} - y_{iv} >= 0
123                constraints.push(LinearConstraint::ge(
124                    vec![(x_var, 1), (y_iu, 1), (y_iv, -1)],
125                    0,
126                ));
127            }
128        }
129
130        // Objective: minimize sum_e w_e * x_e
131        let objective: Vec<(usize, i64)> = weights
132            .iter()
133            .enumerate()
134            .map(|(e_idx, &weight)| (k * n + e_idx, weight))
135            .collect();
136
137        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
138            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
139
140        Ok(ReductionMMCToILP { target, n, m, k })
141    }
142}
143
144#[cfg(feature = "example-db")]
145pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
146    vec![crate::example_db::specs::RuleExampleSpec {
147        id: "minimummultiwaycut_to_ilp",
148        build: || {
149            let graph = SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (0, 4), (1, 3)]);
150            let problem = MinimumMultiwayCut::new(graph, vec![0, 2, 4], vec![2, 3, 1, 2, 4, 5]);
151            crate::example_db::specs::rule_example_via_ilp::<_, bool>(problem)
152        },
153    }]
154}
155
156#[cfg(test)]
157#[path = "../unit_tests/rules/minimummultiwaycut_ilp.rs"]
158mod tests;
problemreductions/rules/minimummultiwaycut_ilp.rs

problemreductions/rules/
minimummultiwaycut_ilp.rs
