problemreductions/rules/
minimummaximalmatching_ilp.rs

1//! Reduction from MinimumMaximalMatching to ILP (Integer Linear Programming).
2//!
3//! The Minimum Maximal Matching problem can be formulated as a binary ILP:
4//! - Variables: One binary variable e_i per edge (0 = not selected, 1 = selected)
5//! - Matching constraints: For each vertex v, sum of e_i for edges incident to v <= 1
6//! - Maximality constraints: For each edge j, e_j + sum_{i shares endpoint with j, i≠j} e_i >= 1
7//!   (if edge j is not selected, at least one edge adjacent to it must be)
8//! - Objective: Minimize sum e_i
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::graph::MinimumMaximalMatching;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14use crate::topology::{Graph, SimpleGraph};
15
16/// Result of reducing MinimumMaximalMatching to ILP.
17///
18/// This reduction creates a binary ILP where:
19/// - Each edge corresponds to a binary variable
20/// - Vertex constraints ensure at most one incident edge is selected per vertex
21/// - Edge constraints ensure that each edge is either selected or blocked by an adjacent
22///   selected edge (maximality)
23/// - The objective minimizes the total number of selected edges
24#[derive(Debug, Clone)]
25pub struct ReductionMMMToILP {
26    target: ILP<bool>,
27}
28
29impl ReductionResult for ReductionMMMToILP {
30    type Source = MinimumMaximalMatching<SimpleGraph>;
31    type Target = ILP<bool>;
32
33    fn target_problem(&self) -> &ILP<bool> {
34        &self.target
35    }
36
37    /// Extract solution from ILP back to MinimumMaximalMatching.
38    ///
39    /// Since the mapping is 1:1 (each edge maps to one binary variable),
40    /// the solution extraction is simply copying the configuration.
41    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
42        target_solution.to_vec()
43    }
44}
45
46#[reduction(
47    overhead = {
48        num_vars = "num_edges",
49        num_constraints = "num_vertices + num_edges",
50    }
51)]
52impl ReduceTo<ILP<bool>> for MinimumMaximalMatching<SimpleGraph> {
53    type Result = ReductionMMMToILP;
54
55    fn reduce_to(&self) -> Self::Result {
56        let edges = self.graph().edges();
57        let num_vars = edges.len();
58        let mut constraints = Vec::new();
59
60        // Matching constraints: for each vertex v, sum of incident edge variables <= 1.
61        // Build vertex -> incident edge index map.
62        let n = self.graph().num_vertices();
63        let mut v2e: Vec<Vec<usize>> = vec![Vec::new(); n];
64        for (idx, &(u, v)) in edges.iter().enumerate() {
65            v2e[u].push(idx);
66            v2e[v].push(idx);
67        }
68        for incident in &v2e {
69            if !incident.is_empty() {
70                let terms: Vec<(usize, f64)> = incident.iter().map(|&e| (e, 1.0)).collect();
71                constraints.push(LinearConstraint::le(terms, 1.0));
72            }
73        }
74
75        // Maximality constraints: for each edge j, the closed neighborhood (j itself plus all
76        // edges sharing an endpoint with j) must contain at least one selected edge.
77        // i.e. e_j + sum_{i: i shares endpoint with j, i≠j} e_i >= 1  for all j.
78        for (j, &(uj, vj)) in edges.iter().enumerate() {
79            // Collect all edges in the closed neighborhood of edge j.
80            let mut neighbors: Vec<usize> = vec![j];
81            for &i in v2e[uj].iter().chain(v2e[vj].iter()) {
82                if i != j && !neighbors.contains(&i) {
83                    neighbors.push(i);
84                }
85            }
86            let terms: Vec<(usize, f64)> = neighbors.iter().map(|&i| (i, 1.0)).collect();
87            constraints.push(LinearConstraint::ge(terms, 1.0));
88        }
89
90        // Objective: minimize sum e_i
91        let objective: Vec<(usize, f64)> = (0..num_vars).map(|i| (i, 1.0)).collect();
92
93        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
94        ReductionMMMToILP { target }
95    }
96}
97
98#[cfg(feature = "example-db")]
99pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
100    vec![crate::example_db::specs::RuleExampleSpec {
101        id: "minimummaximalmatching_to_ilp",
102        build: || {
103            // Path graph P6
104            let source = MinimumMaximalMatching::new(SimpleGraph::new(
105                6,
106                vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)],
107            ));
108            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
109        },
110    }]
111}
112
113#[cfg(test)]
114#[path = "../unit_tests/rules/minimummaximalmatching_ilp.rs"]
115mod tests;
problemreductions/rules/minimummaximalmatching_ilp.rs

problemreductions/rules/
minimummaximalmatching_ilp.rs
