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(
35        &self,
36        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
37    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
38        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
39
40        Ok(target_solution.iter().map(|&value| value == 1).collect())
41    }
42}
43
44fn build_constraints(graph: &SimpleGraph, bound_k: usize) -> Result<Vec<LinearConstraint>, ()> {
45    (0..graph.num_vertices())
46        .map(|v| {
47            let degree = i64::try_from(graph.degree(v)).map_err(|_| ())?;
48            let bound_k = i64::try_from(bound_k).map_err(|_| ())?;
49            let mut terms: Vec<(usize, i64)> =
50                graph.neighbors(v).into_iter().map(|u| (u, 1)).collect();
51            if degree > 0 {
52                terms.push((v, degree));
53            }
54            let rhs = degree
55                .checked_add(bound_k)
56                .and_then(|value| value.checked_sub(1))
57                .ok_or(())?;
58            Ok(LinearConstraint::le(terms, rhs))
59        })
60        .collect()
61}
62
63fn reduce_cokplex_to_ilp<W>(
64    src: &MaximumCoKPlex<SimpleGraph, W, KN>,
65    constraints: Vec<LinearConstraint>,
66    objective: Vec<(usize, i64)>,
67) -> Result<ReductionCoKPlexToILP<W>, crate::registry::ConstructionError>
68where
69    W: WeightElement + VariantParam,
70{
71    let target = ILP::new(
72        src.num_vertices(),
73        constraints,
74        objective,
75        ObjectiveSense::Maximize,
76    )?;
77    Ok(ReductionCoKPlexToILP {
78        target,
79        _marker: PhantomData,
80    })
81}
82
83#[reduction(
84    transform = exact {
85        num_vars = "num_vertices",
86        num_constraints = "num_vertices",
87    },
88    unavailable = {
89        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
90    }
91)]
92impl ReduceTo<ILP<bool>> for MaximumCoKPlex<SimpleGraph, i64, KN> {
93    type Result = ReductionCoKPlexToILP<i64>;
94
95    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
96        let objective: Vec<(usize, i64)> = self
97            .weights()
98            .iter()
99            .enumerate()
100            .map(|(vertex, &weight)| (vertex, weight))
101            .collect();
102        let constraints = build_constraints(self.graph(), self.bound_k()).map_err(|_| {
103            crate::rules::ReductionError::integer_overflow::<
104                MaximumCoKPlex<SimpleGraph, i64, KN>,
105                ILP<bool>,
106            >("encoding a degree or co-k-plex bound")
107        })?;
108        reduce_cokplex_to_ilp(self, constraints, objective).map_err(Self::target_construction)
109    }
110}
111
112#[reduction(
113    transform = exact {
114        num_vars = "num_vertices",
115        num_constraints = "num_vertices",
116    },
117    unavailable = {
118        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
119    }
120)]
121impl ReduceTo<ILP<bool>> for MaximumCoKPlex<SimpleGraph, One, KN> {
122    type Result = ReductionCoKPlexToILP<One>;
123
124    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
125        let objective: Vec<(usize, i64)> = self
126            .weights()
127            .iter()
128            .enumerate()
129            .map(|(v, _)| (v, 1))
130            .collect();
131        let constraints = build_constraints(self.graph(), self.bound_k()).map_err(|_| {
132            crate::rules::ReductionError::integer_overflow::<
133                MaximumCoKPlex<SimpleGraph, One, KN>,
134                ILP<bool>,
135            >("encoding a degree or co-k-plex bound")
136        })?;
137        reduce_cokplex_to_ilp(self, constraints, objective).map_err(Self::target_construction)
138    }
139}
140
141#[cfg(feature = "example-db")]
142pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
143    vec![
144        crate::example_db::specs::RuleExampleSpec {
145            id: "weighted_maximumcokplex_to_ilp",
146            build: || {
147                let source = MaximumCoKPlex::<_, i64, KN>::with_k(
148                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]),
149                    vec![5, 1, 4, 1, 3],
150                    2,
151                );
152                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
153            },
154        },
155        crate::example_db::specs::RuleExampleSpec {
156            id: "cardinality_maximumcokplex_to_ilp",
157            build: || {
158                let source = MaximumCoKPlex::<_, One, KN>::with_k(
159                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]),
160                    vec![One; 5],
161                    2,
162                );
163                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
164            },
165        },
166    ]
167}
168
169#[cfg(test)]
170#[path = "../unit_tests/rules/maximumcokplex_ilp.rs"]
171mod tests;
problemreductions/rules/maximumcokplex_ilp.rs

problemreductions/rules/
maximumcokplex_ilp.rs
