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 = graph.degree(v);
48            let allowed_neighbors =
49                i64::try_from(bound_k.checked_sub(1).ok_or(())?.min(degree)).map_err(|_| ())?;
50            let degree = i64::try_from(degree).map_err(|_| ())?;
51            let mut terms: Vec<(usize, i64)> =
52                graph.neighbors(v).into_iter().map(|u| (u, 1)).collect();
53            if degree > 0 {
54                terms.push((v, degree));
55            }
56            let rhs = degree.checked_add(allowed_neighbors).ok_or(())?;
57            Ok(LinearConstraint::le(terms, rhs))
58        })
59        .collect()
60}
61
62fn reduce_cokplex_to_ilp<W>(
63    src: &MaximumCoKPlex<SimpleGraph, W, KN>,
64    constraints: Vec<LinearConstraint>,
65    objective: Vec<(usize, i64)>,
66) -> Result<ReductionCoKPlexToILP<W>, crate::registry::ConstructionError>
67where
68    W: WeightElement + VariantParam,
69{
70    let target = ILP::new(
71        src.num_vertices(),
72        constraints,
73        objective,
74        ObjectiveSense::Maximize,
75    )?;
76    Ok(ReductionCoKPlexToILP {
77        target,
78        _marker: PhantomData,
79    })
80}
81
82#[reduction(transform = {
83    exact {
84        num_vars = "num_vertices",
85        num_constraints = "num_vertices",
86    },
87    upper_bound {
88        max_constraint_magnitude_bits = "4 * num_edges + 2",
89        num_nonzeros = "num_vertices * num_vertices",
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(transform = {
113    exact {
114        num_vars = "num_vertices",
115        num_constraints = "num_vertices",
116    },
117    upper_bound {
118        max_constraint_magnitude_bits = "4 * num_edges + 2",
119        num_nonzeros = "num_vertices * num_vertices",
120    },
121})]
122impl ReduceTo<ILP<bool>> for MaximumCoKPlex<SimpleGraph, One, KN> {
123    type Result = ReductionCoKPlexToILP<One>;
124
125    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
126        let objective: Vec<(usize, i64)> = self
127            .weights()
128            .iter()
129            .enumerate()
130            .map(|(v, _)| (v, 1))
131            .collect();
132        let constraints = build_constraints(self.graph(), self.bound_k()).map_err(|_| {
133            crate::rules::ReductionError::integer_overflow::<
134                MaximumCoKPlex<SimpleGraph, One, KN>,
135                ILP<bool>,
136            >("encoding a degree or co-k-plex bound")
137        })?;
138        reduce_cokplex_to_ilp(self, constraints, objective).map_err(Self::target_construction)
139    }
140}
141
142#[cfg(feature = "example-db")]
143pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
144    vec![
145        crate::example_db::specs::RuleExampleSpec {
146            id: "weighted_maximumcokplex_to_ilp",
147            build: || {
148                let source = MaximumCoKPlex::<_, i64, KN>::with_k(
149                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]),
150                    vec![5, 1, 4, 1, 3],
151                    2,
152                );
153                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
154            },
155        },
156        crate::example_db::specs::RuleExampleSpec {
157            id: "cardinality_maximumcokplex_to_ilp",
158            build: || {
159                let source = MaximumCoKPlex::<_, One, KN>::with_k(
160                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]),
161                    vec![One; 5],
162                    2,
163                );
164                crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
165            },
166        },
167    ]
168}
169
170#[cfg(test)]
171#[path = "../unit_tests/rules/maximumcokplex_ilp.rs"]
172mod tests;
problemreductions/rules/maximumcokplex_ilp.rs

problemreductions/rules/
maximumcokplex_ilp.rs
