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(
28        &self,
29        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
30    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
31        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
32
33        Ok(target_solution[..self.num_vertices]
34            .iter()
35            .map(|&value| value == 1)
36            .collect())
37    }
38}
39
40#[reduction(
41    transform = upper_bound {
42        num_vars = "num_vertices",
43        num_constraints = "num_vertices^2 + 2",
44    },
45    unavailable = {
46        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
47    }
48)]
49impl ReduceTo<ILP<bool>> for BalancedCompleteBipartiteSubgraph {
50    type Result = ReductionBCBSToILP;
51
52    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
53        let left = self.left_size();
54        let right = self.right_size();
55        let n = left + right;
56        let k = Self::exact_i64(self.k(), "encoding the selected partition size")?;
57        let mut constraints = Vec::new();
58
59        // Build edge lookup (bipartite-local coords)
60        let edge_set: HashSet<(usize, usize)> = self.graph().left_edges().iter().copied().collect();
61
62        // Σ x_l = k (for l in 0..left)
63        let left_terms: Vec<(usize, i64)> = (0..left).map(|l| (l, 1)).collect();
64        constraints.push(LinearConstraint::eq(left_terms, k));
65
66        // Σ y_r = k (for r in 0..right, variable index = left + r)
67        let right_terms: Vec<(usize, i64)> = (0..right).map(|r| (left + r, 1)).collect();
68        constraints.push(LinearConstraint::eq(right_terms, k));
69
70        // Non-edge constraints: x_l + y_r ≤ 1 for (l, r) not in E
71        for l in 0..left {
72            for r in 0..right {
73                if !edge_set.contains(&(l, r)) {
74                    constraints.push(LinearConstraint::le(vec![(l, 1), (left + r, 1)], 1));
75                }
76            }
77        }
78
79        let target = ILP::new(n, constraints, vec![], ObjectiveSense::Minimize)
80            .map_err(Self::target_construction)?;
81        Ok(ReductionBCBSToILP {
82            target,
83            num_vertices: n,
84        })
85    }
86}
87
88#[cfg(feature = "example-db")]
89pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
90    use crate::export::SolutionPair;
91    use crate::topology::BipartiteGraph;
92    vec![crate::example_db::specs::RuleExampleSpec {
93        id: "balancedcompletebipartitesubgraph_to_ilp",
94        build: || {
95            let source = BalancedCompleteBipartiteSubgraph::new(
96                BipartiteGraph::new(3, 3, vec![(0, 0), (0, 1), (1, 0), (1, 1), (2, 1), (2, 2)]),
97                2,
98            );
99            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
100                source,
101                SolutionPair {
102                    source_config: serde_json::json!(vec![true, true, false, true, true, false]),
103                    target_config: serde_json::json!(vec![1, 1, 0, 1, 1, 0]),
104                },
105            )
106        },
107    }]
108}
109
110#[cfg(test)]
111#[path = "../unit_tests/rules/balancedcompletebipartitesubgraph_ilp.rs"]
112mod tests;
problemreductions/rules/balancedcompletebipartitesubgraph_ilp.rs

problemreductions/rules/
balancedcompletebipartitesubgraph_ilp.rs
