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(
61    transform = 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    unavailable = {
66        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
67    }
68)]
69impl ReduceTo<ILP<bool>> for MinimumMultiwayCut<SimpleGraph, i64> {
70    type Result = ReductionMMCToILP;
71
72    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
73        let n = self.num_vertices();
74        let m = self.num_edges();
75        let k = self.num_terminals();
76        let terminals = self.terminals();
77        let edges = self.graph().edges();
78        let weights = self.edge_weights();
79        let num_vars = k * n + m;
80
81        // Terminal fixing constraints: k constraints for y_{i,t_i} = 1,
82        // and k*(k-1) constraints for y_{j,t_i} = 0 where j != i.
83        // Total terminal fixes: k + k*(k-1) = k^2.
84        let num_terminal_fixes = k * k;
85        let num_constraints = n + 2 * k * m + num_terminal_fixes;
86        let mut constraints = Vec::with_capacity(num_constraints);
87
88        // Terminal fixing: y_{i, t_i} = 1 for each terminal i
89        for (i, &t) in terminals.iter().enumerate() {
90            constraints.push(LinearConstraint::eq(vec![(i * n + t, 1)], 1));
91        }
92
93        // Terminal fixing: y_{j, t_i} = 0 for j != i
94        for (i, &t) in terminals.iter().enumerate() {
95            for j in 0..k {
96                if j != i {
97                    constraints.push(LinearConstraint::eq(vec![(j * n + t, 1)], 0));
98                }
99            }
100        }
101
102        // Partition constraints: sum_i y_{iv} = 1 for each vertex v
103        for v in 0..n {
104            let terms: Vec<(usize, i64)> = (0..k).map(|i| (i * n + v, 1)).collect();
105            constraints.push(LinearConstraint::eq(terms, 1));
106        }
107
108        // Edge-cut linking constraints: for each edge e=(u,v) and each terminal i:
109        //   x_e >= y_{iu} - y_{iv}  =>  x_e - y_{iu} + y_{iv} >= 0
110        //   x_e >= y_{iv} - y_{iu}  =>  x_e + y_{iu} - y_{iv} >= 0
111        for (e_idx, (u, v)) in edges.iter().enumerate() {
112            let x_var = k * n + e_idx;
113            for i in 0..k {
114                let y_iu = i * n + u;
115                let y_iv = i * n + v;
116                // x_e - y_{iu} + y_{iv} >= 0
117                constraints.push(LinearConstraint::ge(
118                    vec![(x_var, 1), (y_iu, -1), (y_iv, 1)],
119                    0,
120                ));
121                // x_e + y_{iu} - y_{iv} >= 0
122                constraints.push(LinearConstraint::ge(
123                    vec![(x_var, 1), (y_iu, 1), (y_iv, -1)],
124                    0,
125                ));
126            }
127        }
128
129        // Objective: minimize sum_e w_e * x_e
130        let objective: Vec<(usize, i64)> = weights
131            .iter()
132            .enumerate()
133            .map(|(e_idx, &weight)| (k * n + e_idx, weight))
134            .collect();
135
136        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
137            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
138
139        Ok(ReductionMMCToILP { target, n, m, k })
140    }
141}
142
143#[cfg(feature = "example-db")]
144pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
145    vec![crate::example_db::specs::RuleExampleSpec {
146        id: "minimummultiwaycut_to_ilp",
147        build: || {
148            let graph = SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (0, 4), (1, 3)]);
149            let problem = MinimumMultiwayCut::new(graph, vec![0, 2, 4], vec![2, 3, 1, 2, 4, 5]);
150            crate::example_db::specs::rule_example_via_ilp::<_, bool>(problem)
151        },
152    }]
153}
154
155#[cfg(test)]
156#[path = "../unit_tests/rules/minimummultiwaycut_ilp.rs"]
157mod tests;
problemreductions/rules/minimummultiwaycut_ilp.rs

problemreductions/rules/
minimummultiwaycut_ilp.rs
