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// Independence uses at most m distinct non-loop pairs (2m coefficients);
36// maximality uses n diagonal terms and at most 2m neighbor incidences.
37#[reduction(transform = {
38    exact {
39        num_vars = "num_vertices",
40    },
41    upper_bound {
42        max_constraint_magnitude_bits = "2 * num_edges + 2",
43        num_constraints = "num_edges + num_vertices",
44        num_nonzeros = "4 * num_edges + num_vertices",
45    },
46})]
47impl ReduceTo<ILP<bool>> for MaximalIS<SimpleGraph, i64> {
48    type Result = ReductionMxISToILP;
49
50    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
51        let n = self.num_vertices();
52        let mut constraints = Vec::new();
53
54        // Independence: ∀ edge (u,v): x_u + x_v ≤ 1
55        for u in 0..n {
56            for v in (u + 1)..n {
57                if self.graph().has_edge(u, v) {
58                    constraints.push(LinearConstraint::le(vec![(u, 1), (v, 1)], 1));
59                }
60            }
61        }
62
63        // Maximality: ∀ v: x_v + Σ_{u∈N(v)} x_u ≥ 1
64        for v in 0..n {
65            let mut terms = vec![(v, 1)];
66            for u in self.graph().neighbors(v) {
67                terms.push((u, 1));
68            }
69            constraints.push(LinearConstraint::ge(terms, 1));
70        }
71
72        // Objective: Maximize Σ w_v·x_v
73        let weights = self.weights();
74        let objective: Vec<(usize, i64)> = weights
75            .iter()
76            .enumerate()
77            .map(|(i, &weight)| (i, weight))
78            .collect();
79
80        let target = ILP::new(n, constraints, objective, ObjectiveSense::Maximize)
81            .map_err(Self::target_construction)?;
82        Ok(ReductionMxISToILP { target })
83    }
84}
85
86#[cfg(feature = "example-db")]
87pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
88    vec![crate::example_db::specs::RuleExampleSpec {
89        id: "maximalis_to_ilp",
90        build: || {
91            // Path P3: 0-1-2
92            let source = MaximalIS::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![1, 1, 1]);
93            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
94        },
95    }]
96}
97
98#[cfg(test)]
99#[path = "../unit_tests/rules/maximalis_ilp.rs"]
100mod tests;
problemreductions/rules/maximalis_ilp.rs

problemreductions/rules/
maximalis_ilp.rs
