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_witness(
32            self.target_problem(),
33            target_solution,
34            |value| value.value.is_some(),
35            "target ILP assignment is infeasible",
36        )?;
37
38        Ok(target_solution[..self.num_vertices]
39            .iter()
40            .map(|&value| value == 1)
41            .collect())
42    }
43}
44
45#[crate::aggregate_reduction(ilp_feasibility)]
46impl crate::rules::AggregateReductionResult for ReductionBCBSToILP {}
47
48// The two partition sums contain n terms total; each missing cross-pair
49// contributes one two-term row. Edge lookup deduplicates raw edges.
50// Coefficients/endpoints are 0/1 and the only other magnitude is k.
51#[reduction(transform = upper_bound {
52    max_constraint_magnitude_bits = "k / 2 + 1",
53    num_vars = "num_vertices",
54    num_constraints = "left_size * right_size + 2",
55    num_nonzeros = "num_vertices + 2 * left_size * right_size",
56})]
57impl ReduceTo<ILP<bool>> for BalancedCompleteBipartiteSubgraph {
58    type Result = ReductionBCBSToILP;
59
60    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
61        let left = self.left_size();
62        let right = self.right_size();
63        let n = left + right;
64        let k = Self::exact_i64(self.k(), "encoding the selected partition size")?;
65        let mut constraints = Vec::new();
66
67        // Build edge lookup (bipartite-local coords)
68        let edge_set: HashSet<(usize, usize)> = self.graph().left_edges().iter().copied().collect();
69
70        // Σ x_l = k (for l in 0..left)
71        let left_terms: Vec<(usize, i64)> = (0..left).map(|l| (l, 1)).collect();
72        constraints.push(LinearConstraint::eq(left_terms, k));
73
74        // Σ y_r = k (for r in 0..right, variable index = left + r)
75        let right_terms: Vec<(usize, i64)> = (0..right).map(|r| (left + r, 1)).collect();
76        constraints.push(LinearConstraint::eq(right_terms, k));
77
78        // Non-edge constraints: x_l + y_r ≤ 1 for (l, r) not in E
79        for l in 0..left {
80            for r in 0..right {
81                if !edge_set.contains(&(l, r)) {
82                    constraints.push(LinearConstraint::le(vec![(l, 1), (left + r, 1)], 1));
83                }
84            }
85        }
86
87        let target = ILP::new(n, constraints, vec![], ObjectiveSense::Minimize)
88            .map_err(Self::target_construction)?;
89        Ok(ReductionBCBSToILP {
90            target,
91            num_vertices: n,
92        })
93    }
94}
95
96#[cfg(feature = "example-db")]
97pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
98    use crate::export::SolutionPair;
99    use crate::topology::BipartiteGraph;
100    vec![crate::example_db::specs::RuleExampleSpec {
101        id: "balancedcompletebipartitesubgraph_to_ilp",
102        build: || {
103            let source = BalancedCompleteBipartiteSubgraph::new(
104                BipartiteGraph::new(3, 3, vec![(0, 0), (0, 1), (1, 0), (1, 1), (2, 1), (2, 2)]),
105                2,
106            );
107            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
108                source,
109                SolutionPair {
110                    source_config: serde_json::json!(vec![true, true, false, true, true, false]),
111                    target_config: serde_json::json!(vec![1, 1, 0, 1, 1, 0]),
112                },
113            )
114        },
115    }]
116}
117
118#[cfg(test)]
119#[path = "../unit_tests/rules/balancedcompletebipartitesubgraph_ilp.rs"]
120mod tests;
problemreductions/rules/balancedcompletebipartitesubgraph_ilp.rs

problemreductions/rules/
balancedcompletebipartitesubgraph_ilp.rs
