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, i32>;
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(&self, target_solution: &[usize]) -> Vec<usize> {
46        let offset = self.k * self.n;
47        (0..self.m).map(|e| target_solution[offset + e]).collect()
48    }
49}
50
51#[reduction(
52    overhead = {
53        num_vars = "num_terminals * num_vertices + num_edges",
54        num_constraints = "num_vertices + 2 * num_terminals * num_edges + num_terminals * num_terminals",
55    }
56)]
57impl ReduceTo<ILP<bool>> for MinimumMultiwayCut<SimpleGraph, i32> {
58    type Result = ReductionMMCToILP;
59
60    fn reduce_to(&self) -> Self::Result {
61        let n = self.num_vertices();
62        let m = self.num_edges();
63        let k = self.num_terminals();
64        let terminals = self.terminals();
65        let edges = self.graph().edges();
66        let weights = self.edge_weights();
67        let num_vars = k * n + m;
68
69        // Terminal fixing constraints: k constraints for y_{i,t_i} = 1,
70        // and k*(k-1) constraints for y_{j,t_i} = 0 where j != i.
71        // Total terminal fixes: k + k*(k-1) = k^2.
72        let num_terminal_fixes = k * k;
73        let num_constraints = n + 2 * k * m + num_terminal_fixes;
74        let mut constraints = Vec::with_capacity(num_constraints);
75
76        // Terminal fixing: y_{i, t_i} = 1 for each terminal i
77        for (i, &t) in terminals.iter().enumerate() {
78            constraints.push(LinearConstraint::eq(vec![(i * n + t, 1.0)], 1.0));
79        }
80
81        // Terminal fixing: y_{j, t_i} = 0 for j != i
82        for (i, &t) in terminals.iter().enumerate() {
83            for j in 0..k {
84                if j != i {
85                    constraints.push(LinearConstraint::eq(vec![(j * n + t, 1.0)], 0.0));
86                }
87            }
88        }
89
90        // Partition constraints: sum_i y_{iv} = 1 for each vertex v
91        for v in 0..n {
92            let terms: Vec<(usize, f64)> = (0..k).map(|i| (i * n + v, 1.0)).collect();
93            constraints.push(LinearConstraint::eq(terms, 1.0));
94        }
95
96        // Edge-cut linking constraints: for each edge e=(u,v) and each terminal i:
97        //   x_e >= y_{iu} - y_{iv}  =>  x_e - y_{iu} + y_{iv} >= 0
98        //   x_e >= y_{iv} - y_{iu}  =>  x_e + y_{iu} - y_{iv} >= 0
99        for (e_idx, (u, v)) in edges.iter().enumerate() {
100            let x_var = k * n + e_idx;
101            for i in 0..k {
102                let y_iu = i * n + u;
103                let y_iv = i * n + v;
104                // x_e - y_{iu} + y_{iv} >= 0
105                constraints.push(LinearConstraint::ge(
106                    vec![(x_var, 1.0), (y_iu, -1.0), (y_iv, 1.0)],
107                    0.0,
108                ));
109                // x_e + y_{iu} - y_{iv} >= 0
110                constraints.push(LinearConstraint::ge(
111                    vec![(x_var, 1.0), (y_iu, 1.0), (y_iv, -1.0)],
112                    0.0,
113                ));
114            }
115        }
116
117        // Objective: minimize sum_e w_e * x_e
118        let objective: Vec<(usize, f64)> = weights
119            .iter()
120            .enumerate()
121            .map(|(e_idx, w)| (k * n + e_idx, *w as f64))
122            .collect();
123
124        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
125
126        ReductionMMCToILP { target, n, m, k }
127    }
128}
129
130#[cfg(feature = "example-db")]
131pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
132    vec![crate::example_db::specs::RuleExampleSpec {
133        id: "minimummultiwaycut_to_ilp",
134        build: || {
135            let graph = SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (0, 4), (1, 3)]);
136            let problem = MinimumMultiwayCut::new(graph, vec![0, 2, 4], vec![2, 3, 1, 2, 4, 5]);
137            crate::example_db::specs::rule_example_via_ilp::<_, bool>(problem)
138        },
139    }]
140}
141
142#[cfg(test)]
143#[path = "../unit_tests/rules/minimummultiwaycut_ilp.rs"]
144mod tests;
problemreductions/rules/minimummultiwaycut_ilp.rs

problemreductions/rules/
minimummultiwaycut_ilp.rs
