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(&self, target_solution: &[usize]) -> Vec<usize> {
34        target_solution[..self.num_vertices].to_vec()
35    }
36}
37
38#[reduction(
39    overhead = {
40        num_vars = "num_vertices + num_edges",
41        num_constraints = "2 * num_edges + 1",
42    }
43)]
44impl ReduceTo<ILP<bool>> for GraphPartitioning<SimpleGraph> {
45    type Result = ReductionGraphPartitioningToILP;
46
47    fn reduce_to(&self) -> Self::Result {
48        let n = self.num_vertices();
49        let edges = self.graph().edges();
50        let m = edges.len();
51        let num_vars = n + m;
52
53        let mut constraints = Vec::with_capacity(2 * m + 1);
54
55        let balance_terms: Vec<(usize, f64)> = (0..n).map(|v| (v, 1.0)).collect();
56        constraints.push(LinearConstraint::eq(balance_terms, n as f64 / 2.0));
57
58        for (edge_idx, (u, v)) in edges.iter().enumerate() {
59            let y_var = n + edge_idx;
60            constraints.push(LinearConstraint::ge(
61                vec![(y_var, 1.0), (*u, -1.0), (*v, 1.0)],
62                0.0,
63            ));
64            constraints.push(LinearConstraint::ge(
65                vec![(y_var, 1.0), (*u, 1.0), (*v, -1.0)],
66                0.0,
67            ));
68        }
69
70        let objective: Vec<(usize, f64)> = (0..m).map(|edge_idx| (n + edge_idx, 1.0)).collect();
71        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
72
73        ReductionGraphPartitioningToILP {
74            target,
75            num_vertices: n,
76        }
77    }
78}
79
80#[cfg(feature = "example-db")]
81pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
82    use crate::export::SolutionPair;
83
84    vec![crate::example_db::specs::RuleExampleSpec {
85        id: "graphpartitioning_to_ilp",
86        build: || {
87            let source = GraphPartitioning::new(SimpleGraph::new(
88                6,
89                vec![
90                    (0, 1),
91                    (0, 2),
92                    (1, 2),
93                    (1, 3),
94                    (2, 3),
95                    (2, 4),
96                    (3, 4),
97                    (3, 5),
98                    (4, 5),
99                ],
100            ));
101            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
102                source,
103                SolutionPair {
104                    source_config: vec![0, 0, 0, 1, 1, 1],
105                    target_config: vec![0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0],
106                },
107            )
108        },
109    }]
110}
111
112#[cfg(test)]
113#[path = "../unit_tests/rules/graphpartitioning_ilp.rs"]
114mod tests;
problemreductions/rules/graphpartitioning_ilp.rs

problemreductions/rules/
graphpartitioning_ilp.rs
