problemreductions/rules/
maximummatching_ilp.rs

1//! Reduction from MaximumMatching to ILP (Integer Linear Programming).
2//!
3//! The Maximum Matching problem can be formulated as a binary ILP:
4//! - Variables: One binary variable per edge (0 = not selected, 1 = selected)
5//! - Constraints: For each vertex v, sum of incident edge variables <= 1
6//!   (at most one incident edge can be selected)
7//! - Objective: Maximize the sum of weights of selected edges
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::MaximumMatching;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14
15/// Result of reducing MaximumMatching to ILP.
16///
17/// This reduction creates a binary ILP where:
18/// - Each edge corresponds to a binary variable
19/// - Vertex constraints ensure at most one incident edge is selected per vertex
20/// - The objective maximizes the total weight of selected edges
21#[derive(Debug, Clone)]
22pub struct ReductionMatchingToILP {
23    target: ILP<bool>,
24}
25
26impl ReductionResult for ReductionMatchingToILP {
27    type Source = MaximumMatching<SimpleGraph, i64>;
28    type Target = ILP<bool>;
29
30    fn target_problem(&self) -> &ILP<bool> {
31        &self.target
32    }
33
34    /// Extract solution from ILP back to MaximumMatching.
35    ///
36    /// Since the mapping is 1:1 (each edge maps to one binary variable),
37    /// the solution extraction is simply copying the configuration.
38    fn extract_solution(
39        &self,
40        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
41    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
42        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
43
44        Ok(target_solution.iter().map(|&value| value == 1).collect())
45    }
46}
47
48#[reduction(transform = {
49    exact {
50        num_vars = "num_edges",
51    },
52    upper_bound {
53        max_constraint_magnitude_bits = "2",
54        num_constraints = "num_vertices",
55        num_nonzeros = "2 * num_edges",
56    },
57})]
58impl ReduceTo<ILP<bool>> for MaximumMatching<SimpleGraph, i64> {
59    type Result = ReductionMatchingToILP;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        let num_vars = self.graph().num_edges(); // Number of edges
63
64        // Constraints: For each vertex v, sum of incident edge variables <= 1
65        // This ensures at most one incident edge is selected per vertex
66        let v2e = self.vertex_to_edges();
67        let constraints: Vec<LinearConstraint> = (0..self.graph().num_vertices())
68            .filter_map(|vertex| v2e.get(&vertex))
69            .filter(|edges| !edges.is_empty())
70            .map(|edges| {
71                let terms: Vec<(usize, i64)> = edges.iter().map(|&e| (e, 1)).collect();
72                LinearConstraint::le(terms, 1)
73            })
74            .collect();
75
76        // Objective: maximize sum of w_e * x_e (weighted sum of selected edges)
77        let weights = self.weights();
78        let objective: Vec<(usize, i64)> = weights
79            .iter()
80            .enumerate()
81            .map(|(edge, &weight)| (edge, weight))
82            .collect();
83
84        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
85            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
86
87        Ok(ReductionMatchingToILP { target })
88    }
89}
90
91#[cfg(feature = "example-db")]
92pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
93    vec![crate::example_db::specs::RuleExampleSpec {
94        id: "maximummatching_to_ilp",
95        build: || {
96            let (n, edges) = crate::topology::small_graphs::petersen();
97            let source = MaximumMatching::unit_weights(SimpleGraph::new(n, edges));
98            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
99        },
100    }]
101}
102
103#[cfg(test)]
104#[path = "../unit_tests/rules/maximummatching_ilp.rs"]
105mod tests;
problemreductions/rules/maximummatching_ilp.rs

problemreductions/rules/
maximummatching_ilp.rs
