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, i64>;
19    type Target = ILP<bool>;
20
21    fn target_problem(&self) -> &ILP<bool> {
22        &self.target
23    }
24
25    fn extract_solution(
26        &self,
27        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
28    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
29        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
30
31        Ok(target_solution.iter().map(|&value| value == 1).collect())
32    }
33}
34
35#[reduction(
36    transform = exact {
37        num_vars = "num_vertices",
38        num_constraints = "num_edges + num_vertices",
39    },
40    unavailable = {
41        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
42    }
43)]
44impl ReduceTo<ILP<bool>> for MaximalIS<SimpleGraph, i64> {
45    type Result = ReductionMxISToILP;
46
47    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
48        let n = self.num_vertices();
49        let mut constraints = Vec::new();
50
51        // Independence: ∀ edge (u,v): x_u + x_v ≤ 1
52        for u in 0..n {
53            for v in (u + 1)..n {
54                if self.graph().has_edge(u, v) {
55                    constraints.push(LinearConstraint::le(vec![(u, 1), (v, 1)], 1));
56                }
57            }
58        }
59
60        // Maximality: ∀ v: x_v + Σ_{u∈N(v)} x_u ≥ 1
61        for v in 0..n {
62            let mut terms = vec![(v, 1)];
63            for u in self.graph().neighbors(v) {
64                terms.push((u, 1));
65            }
66            constraints.push(LinearConstraint::ge(terms, 1));
67        }
68
69        // Objective: Maximize Σ w_v·x_v
70        let weights = self.weights();
71        let objective: Vec<(usize, i64)> = weights
72            .iter()
73            .enumerate()
74            .map(|(i, &weight)| (i, weight))
75            .collect();
76
77        let target = ILP::new(n, constraints, objective, ObjectiveSense::Maximize)
78            .map_err(Self::target_construction)?;
79        Ok(ReductionMxISToILP { target })
80    }
81}
82
83#[cfg(feature = "example-db")]
84pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
85    vec![crate::example_db::specs::RuleExampleSpec {
86        id: "maximalis_to_ilp",
87        build: || {
88            // Path P3: 0-1-2
89            let source = MaximalIS::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![1, 1, 1]);
90            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
91        },
92    }]
93}
94
95#[cfg(test)]
96#[path = "../unit_tests/rules/maximalis_ilp.rs"]
97mod tests;
problemreductions/rules/maximalis_ilp.rs

problemreductions/rules/
maximalis_ilp.rs
