problemreductions/rules/
minimumcutintoboundedsets_ilp.rs

1//! Reduction from MinimumCutIntoBoundedSets to ILP.
2//!
3//! Binary x_v (1 iff v on sink side), binary y_e (cut indicator).
4//! Source pinned to 0, sink pinned to 1.
5//! Size bounds: Σ x_v ≤ B, Σ (1-x_v) ≤ B.
6//! Cut linking: y_e ≥ x_u - x_v, y_e ≥ x_v - x_u for each edge {u,v}.
7//! Cut bound: Σ w_e y_e ≤ K.
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::MinimumCutIntoBoundedSets;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14
15#[derive(Debug, Clone)]
16pub struct ReductionMinCutBSToILP {
17    target: ILP<bool>,
18    num_vertices: usize,
19}
20
21impl ReductionResult for ReductionMinCutBSToILP {
22    type Source = MinimumCutIntoBoundedSets<SimpleGraph, i32>;
23    type Target = ILP<bool>;
24
25    fn target_problem(&self) -> &ILP<bool> {
26        &self.target
27    }
28
29    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
30        target_solution[..self.num_vertices].to_vec()
31    }
32}
33
34#[reduction(
35    overhead = {
36        num_vars = "num_vertices + num_edges",
37        num_constraints = "2 + 2 + 2 * num_edges",
38    }
39)]
40impl ReduceTo<ILP<bool>> for MinimumCutIntoBoundedSets<SimpleGraph, i32> {
41    type Result = ReductionMinCutBSToILP;
42
43    fn reduce_to(&self) -> Self::Result {
44        let n = self.num_vertices();
45        let edges = self.graph().edges();
46        let m = edges.len();
47        let num_vars = n + m;
48        let mut constraints = Vec::new();
49
50        // x_s = 0
51        constraints.push(LinearConstraint::eq(vec![(self.source(), 1.0)], 0.0));
52
53        // x_t = 1
54        constraints.push(LinearConstraint::eq(vec![(self.sink(), 1.0)], 1.0));
55
56        // Σ x_v ≤ B (sink side count)
57        let all_terms: Vec<(usize, f64)> = (0..n).map(|v| (v, 1.0)).collect();
58        constraints.push(LinearConstraint::le(all_terms, self.size_bound() as f64));
59
60        // Σ (1 - x_v) ≤ B  ⟹  n - Σ x_v ≤ B  ⟹  -Σ x_v ≤ B - n  ⟹  Σ x_v ≥ n - B
61        let all_terms2: Vec<(usize, f64)> = (0..n).map(|v| (v, 1.0)).collect();
62        constraints.push(LinearConstraint::ge(
63            all_terms2,
64            (n as f64) - (self.size_bound() as f64),
65        ));
66
67        // Cut linking: for each edge e = {u, v}, y_e ≥ x_u - x_v and y_e ≥ x_v - x_u
68        for (e_idx, &(u, v)) in edges.iter().enumerate() {
69            let y = n + e_idx;
70            // y_e - x_u + x_v ≥ 0  (y_e ≥ x_u - x_v)
71            constraints.push(LinearConstraint::ge(
72                vec![(y, 1.0), (u, -1.0), (v, 1.0)],
73                0.0,
74            ));
75            // y_e + x_u - x_v ≥ 0  (y_e ≥ x_v - x_u)
76            constraints.push(LinearConstraint::ge(
77                vec![(y, 1.0), (u, 1.0), (v, -1.0)],
78                0.0,
79            ));
80        }
81
82        // Objective: minimize cut weight Σ w_e y_e
83        let objective: Vec<(usize, f64)> = self
84            .edge_weights()
85            .iter()
86            .enumerate()
87            .map(|(e_idx, &w)| (n + e_idx, w as f64))
88            .collect();
89
90        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
91        ReductionMinCutBSToILP {
92            target,
93            num_vertices: n,
94        }
95    }
96}
97
98#[cfg(feature = "example-db")]
99pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
100    vec![crate::example_db::specs::RuleExampleSpec {
101        id: "minimumcutintoboundedsets_to_ilp",
102        build: || {
103            let source = MinimumCutIntoBoundedSets::new(
104                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
105                vec![1, 1, 1],
106                0,
107                3,
108                3,
109            );
110            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
111        },
112    }]
113}
114
115#[cfg(test)]
116#[path = "../unit_tests/rules/minimumcutintoboundedsets_ilp.rs"]
117mod tests;
problemreductions/rules/minimumcutintoboundedsets_ilp.rs

problemreductions/rules/
minimumcutintoboundedsets_ilp.rs
