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

problemreductions/rules/
minimumcutintoboundedsets_ilp.rs
