problemreductions/rules/
maximalis_ilp.rs

1//! Reduction from MaximalIS to ILP (Integer Linear Programming).
2//!
3//! Binary variable x_v per vertex. Independence: ∀ edge (u,v): x_u + x_v ≤ 1.
4//! Maximality: ∀ v: x_v + Σ_{u∈N(v)} x_u ≥ 1. Maximize Σ w_v·x_v.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::graph::MaximalIS;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11
12#[derive(Debug, Clone)]
13pub struct ReductionMxISToILP {
14    target: ILP<bool>,
15}
16
17impl ReductionResult for ReductionMxISToILP {
18    type Source = MaximalIS<SimpleGraph, i32>;
19    type Target = ILP<bool>;
20
21    fn target_problem(&self) -> &ILP<bool> {
22        &self.target
23    }
24
25    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
26        target_solution.to_vec()
27    }
28}
29
30#[reduction(
31    overhead = {
32        num_vars = "num_vertices",
33        num_constraints = "num_edges + num_vertices",
34    }
35)]
36impl ReduceTo<ILP<bool>> for MaximalIS<SimpleGraph, i32> {
37    type Result = ReductionMxISToILP;
38
39    fn reduce_to(&self) -> Self::Result {
40        let n = self.num_vertices();
41        let mut constraints = Vec::new();
42
43        // Independence: ∀ edge (u,v): x_u + x_v ≤ 1
44        for u in 0..n {
45            for v in (u + 1)..n {
46                if self.graph().has_edge(u, v) {
47                    constraints.push(LinearConstraint::le(vec![(u, 1.0), (v, 1.0)], 1.0));
48                }
49            }
50        }
51
52        // Maximality: ∀ v: x_v + Σ_{u∈N(v)} x_u ≥ 1
53        for v in 0..n {
54            let mut terms = vec![(v, 1.0)];
55            for u in self.graph().neighbors(v) {
56                terms.push((u, 1.0));
57            }
58            constraints.push(LinearConstraint::ge(terms, 1.0));
59        }
60
61        // Objective: Maximize Σ w_v·x_v
62        let weights = self.weights();
63        let objective: Vec<(usize, f64)> = weights
64            .iter()
65            .enumerate()
66            .map(|(i, w)| (i, *w as f64))
67            .collect();
68
69        let target = ILP::new(n, constraints, objective, ObjectiveSense::Maximize);
70        ReductionMxISToILP { target }
71    }
72}
73
74#[cfg(feature = "example-db")]
75pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
76    vec![crate::example_db::specs::RuleExampleSpec {
77        id: "maximalis_to_ilp",
78        build: || {
79            // Path P3: 0-1-2
80            let source = MaximalIS::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![1, 1, 1]);
81            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
82        },
83    }]
84}
85
86#[cfg(test)]
87#[path = "../unit_tests/rules/maximalis_ilp.rs"]
88mod tests;
problemreductions/rules/maximalis_ilp.rs

problemreductions/rules/
maximalis_ilp.rs
