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(
49    transform = exact {
50        num_vars = "num_edges",
51        num_constraints = "num_vertices",
52    },
53    unavailable = {
54        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
55    }
56)]
57impl ReduceTo<ILP<bool>> for MaximumMatching<SimpleGraph, i64> {
58    type Result = ReductionMatchingToILP;
59
60    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
61        let num_vars = self.graph().num_edges(); // Number of edges
62
63        // Constraints: For each vertex v, sum of incident edge variables <= 1
64        // This ensures at most one incident edge is selected per vertex
65        let v2e = self.vertex_to_edges();
66        let constraints: Vec<LinearConstraint> = (0..self.graph().num_vertices())
67            .filter_map(|vertex| v2e.get(&vertex))
68            .filter(|edges| !edges.is_empty())
69            .map(|edges| {
70                let terms: Vec<(usize, i64)> = edges.iter().map(|&e| (e, 1)).collect();
71                LinearConstraint::le(terms, 1)
72            })
73            .collect();
74
75        // Objective: maximize sum of w_e * x_e (weighted sum of selected edges)
76        let weights = self.weights();
77        let objective: Vec<(usize, i64)> = weights
78            .iter()
79            .enumerate()
80            .map(|(edge, &weight)| (edge, weight))
81            .collect();
82
83        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
84            .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?;
85
86        Ok(ReductionMatchingToILP { target })
87    }
88}
89
90#[cfg(feature = "example-db")]
91pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
92    vec![crate::example_db::specs::RuleExampleSpec {
93        id: "maximummatching_to_ilp",
94        build: || {
95            let (n, edges) = crate::topology::small_graphs::petersen();
96            let source = MaximumMatching::unit_weights(SimpleGraph::new(n, edges));
97            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
98        },
99    }]
100}
101
102#[cfg(test)]
103#[path = "../unit_tests/rules/maximummatching_ilp.rs"]
104mod tests;
problemreductions/rules/maximummatching_ilp.rs

problemreductions/rules/
maximummatching_ilp.rs
