problemreductions/rules/
balancedcompletebipartitesubgraph_ilp.rs

1//! Reduction from BalancedCompleteBipartiteSubgraph to ILP.
2//!
3//! Binary variables x_l for left vertices, y_r for right vertices.
4//! Cardinality: Σ x_l = k, Σ y_r = k.
5//! Non-edge forbidding: x_l + y_r ≤ 1 for every non-edge (l, r).
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::BalancedCompleteBipartiteSubgraph;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use std::collections::HashSet;
12
13#[derive(Debug, Clone)]
14pub struct ReductionBCBSToILP {
15    target: ILP<bool>,
16    num_vertices: usize,
17}
18
19impl ReductionResult for ReductionBCBSToILP {
20    type Source = BalancedCompleteBipartiteSubgraph;
21    type Target = ILP<bool>;
22
23    fn target_problem(&self) -> &ILP<bool> {
24        &self.target
25    }
26
27    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
28        target_solution[..self.num_vertices].to_vec()
29    }
30}
31
32#[reduction(
33    overhead = {
34        num_vars = "num_vertices",
35        num_constraints = "num_vertices * num_vertices",
36    }
37)]
38impl ReduceTo<ILP<bool>> for BalancedCompleteBipartiteSubgraph {
39    type Result = ReductionBCBSToILP;
40
41    fn reduce_to(&self) -> Self::Result {
42        let left = self.left_size();
43        let right = self.right_size();
44        let n = left + right;
45        let k = self.k();
46        let mut constraints = Vec::new();
47
48        // Build edge lookup (bipartite-local coords)
49        let edge_set: HashSet<(usize, usize)> = self.graph().left_edges().iter().copied().collect();
50
51        // Σ x_l = k (for l in 0..left)
52        let left_terms: Vec<(usize, f64)> = (0..left).map(|l| (l, 1.0)).collect();
53        constraints.push(LinearConstraint::eq(left_terms, k as f64));
54
55        // Σ y_r = k (for r in 0..right, variable index = left + r)
56        let right_terms: Vec<(usize, f64)> = (0..right).map(|r| (left + r, 1.0)).collect();
57        constraints.push(LinearConstraint::eq(right_terms, k as f64));
58
59        // Non-edge constraints: x_l + y_r ≤ 1 for (l, r) not in E
60        for l in 0..left {
61            for r in 0..right {
62                if !edge_set.contains(&(l, r)) {
63                    constraints.push(LinearConstraint::le(vec![(l, 1.0), (left + r, 1.0)], 1.0));
64                }
65            }
66        }
67
68        let target = ILP::new(n, constraints, vec![], ObjectiveSense::Minimize);
69        ReductionBCBSToILP {
70            target,
71            num_vertices: n,
72        }
73    }
74}
75
76#[cfg(feature = "example-db")]
77pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
78    use crate::export::SolutionPair;
79    use crate::topology::BipartiteGraph;
80    vec![crate::example_db::specs::RuleExampleSpec {
81        id: "balancedcompletebipartitesubgraph_to_ilp",
82        build: || {
83            let source = BalancedCompleteBipartiteSubgraph::new(
84                BipartiteGraph::new(3, 3, vec![(0, 0), (0, 1), (1, 0), (1, 1), (2, 1), (2, 2)]),
85                2,
86            );
87            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
88                source,
89                SolutionPair {
90                    source_config: vec![1, 1, 0, 1, 1, 0],
91                    target_config: vec![1, 1, 0, 1, 1, 0],
92                },
93            )
94        },
95    }]
96}
97
98#[cfg(test)]
99#[path = "../unit_tests/rules/balancedcompletebipartitesubgraph_ilp.rs"]
100mod tests;
problemreductions/rules/balancedcompletebipartitesubgraph_ilp.rs

problemreductions/rules/
balancedcompletebipartitesubgraph_ilp.rs
