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(
47    transform = exact {
48        num_vars = "num_vertices + num_edges",
49        num_constraints = "2 * num_edges + 1",
50    },
51    unavailable = {
52        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
53    }
54)]
55impl ReduceTo<ILP<bool>> for GraphPartitioning<SimpleGraph> {
56    type Result = ReductionGraphPartitioningToILP;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        let n = self.num_vertices();
60        let edges = self.graph().edges();
61        let m = edges.len();
62        let num_vars = n + m;
63
64        let mut constraints = Vec::with_capacity(2 * m + 1);
65
66        let balance_terms: Vec<(usize, i64)> = (0..n).map(|v| (v, 2)).collect();
67        constraints.push(LinearConstraint::eq(
68            balance_terms,
69            <Self as ReduceTo<ILP<bool>>>::exact_i64(n, "encoding the partition cardinality")?,
70        ));
71
72        for (edge_idx, (u, v)) in edges.iter().enumerate() {
73            let y_var = n + edge_idx;
74            constraints.push(LinearConstraint::ge(vec![(y_var, 1), (*u, -1), (*v, 1)], 0));
75            constraints.push(LinearConstraint::ge(vec![(y_var, 1), (*u, 1), (*v, -1)], 0));
76        }
77
78        let objective: Vec<(usize, i64)> = (0..m).map(|edge_idx| (n + edge_idx, 1)).collect();
79        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
80            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
81
82        Ok(ReductionGraphPartitioningToILP {
83            target,
84            num_vertices: n,
85        })
86    }
87}
88
89#[cfg(feature = "example-db")]
90pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
91    use crate::export::SolutionPair;
92
93    vec![crate::example_db::specs::RuleExampleSpec {
94        id: "graphpartitioning_to_ilp",
95        build: || {
96            let source = GraphPartitioning::new(SimpleGraph::new(
97                6,
98                vec![
99                    (0, 1),
100                    (0, 2),
101                    (1, 2),
102                    (1, 3),
103                    (2, 3),
104                    (2, 4),
105                    (3, 4),
106                    (3, 5),
107                    (4, 5),
108                ],
109            ));
110            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
111                source,
112                SolutionPair {
113                    source_config: serde_json::json!(vec![false, false, false, true, true, true]),
114                    target_config: serde_json::json!(vec![
115                        0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0
116                    ]),
117                },
118            )
119        },
120    }]
121}
122
123#[cfg(test)]
124#[path = "../unit_tests/rules/graphpartitioning_ilp.rs"]
125mod tests;
problemreductions/rules/graphpartitioning_ilp.rs

problemreductions/rules/
graphpartitioning_ilp.rs
