problemreductions/rules/
graphpartitioning_ilp.rs

1//! Reduction from GraphPartitioning to ILP (Integer Linear Programming).
2//!
3//! Uses the standard balanced-cut ILP formulation:
4//! - Variables: `x_v` for vertex-side assignment and `y_e` for edge-crossing indicators
5//! - Constraints: one balance equality plus two linking inequalities per edge
6//! - Objective: minimize the number of crossing edges
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::graph::GraphPartitioning;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::{Graph, SimpleGraph};
13
14/// Result of reducing GraphPartitioning to ILP.
15///
16/// Variable layout (all binary):
17/// - `x_v` for `v = 0..n-1`: vertex `v` belongs to side `B`
18/// - `y_e` for `e = 0..m-1`: edge `e` crosses the partition
19#[derive(Debug, Clone)]
20pub struct ReductionGraphPartitioningToILP {
21    target: ILP<bool>,
22    num_vertices: usize,
23}
24
25impl ReductionResult for ReductionGraphPartitioningToILP {
26    type Source = GraphPartitioning<SimpleGraph>;
27    type Target = ILP<bool>;
28
29    fn target_problem(&self) -> &ILP<bool> {
30        &self.target
31    }
32
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
38
39        Ok(target_solution[..self.num_vertices]
40            .iter()
41            .map(|&value| value == 1)
42            .collect())
43    }
44}
45
46#[reduction(transform = {
47    exact {
48        num_vars = "num_vertices + num_edges",
49        num_constraints = "2 * num_edges + 1",
50    },
51    upper_bound {
52        max_constraint_magnitude_bits = "num_vertices + 2",
53        num_nonzeros = "(num_vertices + num_edges) * (2 * num_edges + 1)",
54    },
55})]
56impl ReduceTo<ILP<bool>> for GraphPartitioning<SimpleGraph> {
57    type Result = ReductionGraphPartitioningToILP;
58
59    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
60        let n = self.num_vertices();
61        let edges = self.graph().edges();
62        let m = edges.len();
63        let num_vars = n + m;
64
65        let mut constraints = Vec::with_capacity(2 * m + 1);
66
67        let balance_terms: Vec<(usize, i64)> = (0..n).map(|v| (v, 2)).collect();
68        constraints.push(LinearConstraint::eq(
69            balance_terms,
70            <Self as ReduceTo<ILP<bool>>>::exact_i64(n, "encoding the partition cardinality")?,
71        ));
72
73        for (edge_idx, (u, v)) in edges.iter().enumerate() {
74            let y_var = n + edge_idx;
75            constraints.push(LinearConstraint::ge(vec![(y_var, 1), (*u, -1), (*v, 1)], 0));
76            constraints.push(LinearConstraint::ge(vec![(y_var, 1), (*u, 1), (*v, -1)], 0));
77        }
78
79        let objective: Vec<(usize, i64)> = (0..m).map(|edge_idx| (n + edge_idx, 1)).collect();
80        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
81            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
82
83        Ok(ReductionGraphPartitioningToILP {
84            target,
85            num_vertices: n,
86        })
87    }
88}
89
90#[cfg(feature = "example-db")]
91pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
92    use crate::export::SolutionPair;
93
94    vec![crate::example_db::specs::RuleExampleSpec {
95        id: "graphpartitioning_to_ilp",
96        build: || {
97            let source = GraphPartitioning::new(SimpleGraph::new(
98                6,
99                vec![
100                    (0, 1),
101                    (0, 2),
102                    (1, 2),
103                    (1, 3),
104                    (2, 3),
105                    (2, 4),
106                    (3, 4),
107                    (3, 5),
108                    (4, 5),
109                ],
110            ));
111            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
112                source,
113                SolutionPair {
114                    source_config: serde_json::json!(vec![false, false, false, true, true, true]),
115                    target_config: serde_json::json!(vec![
116                        0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0
117                    ]),
118                },
119            )
120        },
121    }]
122}
123
124#[cfg(test)]
125#[path = "../unit_tests/rules/graphpartitioning_ilp.rs"]
126mod tests;
problemreductions/rules/graphpartitioning_ilp.rs

problemreductions/rules/
graphpartitioning_ilp.rs
