problemreductions/rules/
maximumcokplex_ilp.rs

1//! Reduction from MaximumCoKPlex to ILP (Integer Linear Programming).
2//!
3//! Binary variable `x_v` per vertex.
4//! Objective: maximize `sum_v w_v x_v`.
5//! For each vertex `v`, if `x_v = 1` then at most `k - 1` neighbours may also
6//! be selected, encoded by `sum_{u in N(v)} x_u + d(v) x_v <= d(v) + k - 1`.
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::graph::MaximumCoKPlex;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::{Graph, SimpleGraph};
13use crate::types::{One, WeightElement};
14use crate::variant::{VariantParam, KN};
15use std::marker::PhantomData;
16
17#[derive(Debug, Clone)]
18pub struct ReductionCoKPlexToILP<W> {
19    target: ILP<bool>,
20    _marker: PhantomData<W>,
21}
22
23impl<W> ReductionResult for ReductionCoKPlexToILP<W>
24where
25    W: WeightElement + VariantParam,
26{
27    type Source = MaximumCoKPlex<SimpleGraph, W, KN>;
28    type Target = ILP<bool>;
29
30    fn target_problem(&self) -> &ILP<bool> {
31        &self.target
32    }
33
34    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
35        target_solution.to_vec()
36    }
37}
38
39fn build_constraints(graph: &SimpleGraph, bound_k: usize) -> Vec<LinearConstraint> {
40    (0..graph.num_vertices())
41        .map(|v| {
42            let degree = graph.degree(v) as f64;
43            let mut terms: Vec<(usize, f64)> =
44                graph.neighbors(v).into_iter().map(|u| (u, 1.0)).collect();
45            if degree > 0.0 {
46                terms.push((v, degree));
47            }
48            LinearConstraint::le(terms, degree + (bound_k - 1) as f64)
49        })
50        .collect()
51}
52
53fn reduce_cokplex_to_ilp<W>(
54    src: &MaximumCoKPlex<SimpleGraph, W, KN>,
55    objective: Vec<(usize, f64)>,
56) -> ReductionCoKPlexToILP<W>
57where
58    W: WeightElement + VariantParam,
59{
60    let target = ILP::new(
61        src.num_vertices(),
62        build_constraints(src.graph(), src.bound_k()),
63        objective,
64        ObjectiveSense::Maximize,
65    );
66    ReductionCoKPlexToILP {
67        target,
68        _marker: PhantomData,
69    }
70}
71
72#[reduction(
73    overhead = {
74        num_vars = "num_vertices",
75        num_constraints = "num_vertices",
76    }
77)]
78impl ReduceTo<ILP<bool>> for MaximumCoKPlex<SimpleGraph, i32, KN> {
79    type Result = ReductionCoKPlexToILP<i32>;
80
81    fn reduce_to(&self) -> Self::Result {
82        let objective: Vec<(usize, f64)> = self
83            .weights()
84            .iter()
85            .enumerate()
86            .map(|(v, &weight)| (v, weight as f64))
87            .collect();
88        reduce_cokplex_to_ilp(self, objective)
89    }
90}
91
92#[reduction(
93    overhead = {
94        num_vars = "num_vertices",
95        num_constraints = "num_vertices",
96    }
97)]
98impl ReduceTo<ILP<bool>> for MaximumCoKPlex<SimpleGraph, One, KN> {
99    type Result = ReductionCoKPlexToILP<One>;
100
101    fn reduce_to(&self) -> Self::Result {
102        let objective: Vec<(usize, f64)> = self
103            .weights()
104            .iter()
105            .enumerate()
106            .map(|(v, _)| (v, 1.0))
107            .collect();
108        reduce_cokplex_to_ilp(self, objective)
109    }
110}
111
112#[cfg(feature = "example-db")]
113pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
114    vec![
115        crate::example_db::specs::RuleExampleSpec {
116            id: "maximumcokplex_i32_to_ilp",
117            build: || {
118                let source = MaximumCoKPlex::<_, i32, KN>::with_k(
119                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]),
120                    vec![5, 1, 4, 1, 3],
121                    2,
122                );
123                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
124            },
125        },
126        crate::example_db::specs::RuleExampleSpec {
127            id: "maximumcokplex_one_to_ilp",
128            build: || {
129                let source = MaximumCoKPlex::<_, One, KN>::with_k(
130                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]),
131                    vec![One; 5],
132                    2,
133                );
134                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
135            },
136        },
137    ]
138}
139
140#[cfg(test)]
141#[path = "../unit_tests/rules/maximumcokplex_ilp.rs"]
142mod tests;
problemreductions/rules/maximumcokplex_ilp.rs

problemreductions/rules/
maximumcokplex_ilp.rs
