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, i32>;
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(&self, target_solution: &[usize]) -> Vec<usize> {
39        target_solution.to_vec()
40    }
41}
42
43#[reduction(
44    overhead = {
45        num_vars = "num_edges",
46        num_constraints = "num_vertices",
47    }
48)]
49impl ReduceTo<ILP<bool>> for MaximumMatching<SimpleGraph, i32> {
50    type Result = ReductionMatchingToILP;
51
52    fn reduce_to(&self) -> Self::Result {
53        let num_vars = self.graph().num_edges(); // Number of edges
54
55        // Constraints: For each vertex v, sum of incident edge variables <= 1
56        // This ensures at most one incident edge is selected per vertex
57        let v2e = self.vertex_to_edges();
58        let constraints: Vec<LinearConstraint> = v2e
59            .into_iter()
60            .filter(|(_, edges)| !edges.is_empty())
61            .map(|(_, edges)| {
62                let terms: Vec<(usize, f64)> = edges.into_iter().map(|e| (e, 1.0)).collect();
63                LinearConstraint::le(terms, 1.0)
64            })
65            .collect();
66
67        // Objective: maximize sum of w_e * x_e (weighted sum of selected edges)
68        let weights = self.weights();
69        let objective: Vec<(usize, f64)> = weights
70            .iter()
71            .enumerate()
72            .map(|(i, &w)| (i, w as f64))
73            .collect();
74
75        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
76
77        ReductionMatchingToILP { target }
78    }
79}
80
81#[cfg(test)]
82#[path = "../unit_tests/rules/maximummatching_ilp.rs"]
83mod tests;
problemreductions/rules/maximummatching_ilp.rs

problemreductions/rules/
maximummatching_ilp.rs
