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, i64>;
23    type Target = ILP<bool>;
24
25    fn target_problem(&self) -> &ILP<bool> {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
34
35        Ok(target_solution[..self.num_vertices]
36            .iter()
37            .map(|&value| value == 1)
38            .collect())
39    }
40}
41
42#[reduction(
43    transform = exact {
44        num_vars = "num_vertices + num_edges",
45        num_constraints = "2 + 2 + 2 * num_edges",
46    },
47    unavailable = {
48        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
49    }
50)]
51impl ReduceTo<ILP<bool>> for MinimumCutIntoBoundedSets<SimpleGraph, i64> {
52    type Result = ReductionMinCutBSToILP;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let n = self.num_vertices();
56        let edges = self.graph().edges();
57        let m = edges.len();
58        let num_vars = n + m;
59        let n_i64 = Self::exact_i64(n, "encoding the partition size")?;
60        let size_bound = Self::exact_i64(self.size_bound(), "encoding the set-size bound")?;
61        let mut constraints = Vec::new();
62
63        // x_s = 0
64        constraints.push(LinearConstraint::eq(vec![(self.source(), 1)], 0));
65
66        // x_t = 1
67        constraints.push(LinearConstraint::eq(vec![(self.sink(), 1)], 1));
68
69        // Σ x_v ≤ B (sink side count)
70        let all_terms: Vec<(usize, i64)> = (0..n).map(|v| (v, 1)).collect();
71        constraints.push(LinearConstraint::le(all_terms, size_bound));
72
73        // Σ (1 - x_v) ≤ B  ⟹  n - Σ x_v ≤ B  ⟹  -Σ x_v ≤ B - n  ⟹  Σ x_v ≥ n - B
74        let all_terms2: Vec<(usize, i64)> = (0..n).map(|v| (v, 1)).collect();
75        constraints.push(LinearConstraint::ge(all_terms2, n_i64 - size_bound));
76
77        // Cut linking: for each edge e = {u, v}, y_e ≥ x_u - x_v and y_e ≥ x_v - x_u
78        for (e_idx, &(u, v)) in edges.iter().enumerate() {
79            let y = n + e_idx;
80            // y_e - x_u + x_v ≥ 0  (y_e ≥ x_u - x_v)
81            constraints.push(LinearConstraint::ge(vec![(y, 1), (u, -1), (v, 1)], 0));
82            // y_e + x_u - x_v ≥ 0  (y_e ≥ x_v - x_u)
83            constraints.push(LinearConstraint::ge(vec![(y, 1), (u, 1), (v, -1)], 0));
84        }
85
86        // Objective: minimize cut weight Σ w_e y_e
87        let objective: Vec<(usize, i64)> = self
88            .edge_weights()
89            .iter()
90            .enumerate()
91            .map(|(edge, &weight)| (n + edge, weight))
92            .collect();
93
94        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
95            .map_err(Self::target_construction)?;
96        Ok(ReductionMinCutBSToILP {
97            target,
98            num_vertices: n,
99        })
100    }
101}
102
103#[cfg(feature = "example-db")]
104pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
105    vec![crate::example_db::specs::RuleExampleSpec {
106        id: "minimumcutintoboundedsets_to_ilp",
107        build: || {
108            let source = MinimumCutIntoBoundedSets::new(
109                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
110                vec![1, 1, 1],
111                0,
112                3,
113                3,
114            );
115            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
116        },
117    }]
118}
119
120#[cfg(test)]
121#[path = "../unit_tests/rules/minimumcutintoboundedsets_ilp.rs"]
122mod tests;
problemreductions/rules/minimumcutintoboundedsets_ilp.rs

problemreductions/rules/
minimumcutintoboundedsets_ilp.rs
