problemreductions/rules/
kernel_ilp.rs

1//! Binary independence and absorption constraints for a directed graph kernel.
2
3use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
4use crate::models::graph::Kernel;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionKernelToILP {
10    target: ILP<bool>,
11}
12
13impl ReductionResult for ReductionKernelToILP {
14    type Source = Kernel;
15    type Target = ILP<bool>;
16
17    fn target_problem(&self) -> &Self::Target {
18        &self.target
19    }
20
21    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<bool>> {
22        crate::rules::traits::validate_target_witness(
23            self.target_problem(),
24            solution,
25            |value| value.value.is_some(),
26            "target ILP assignment does not select a kernel",
27        )?;
28        Ok(solution.iter().map(|&value| value == 1).collect())
29    }
30}
31
32#[crate::aggregate_reduction(ilp_feasibility)]
33impl crate::rules::AggregateReductionResult for ReductionKernelToILP {}
34
35#[reduction(transform = {
36    exact {
37        num_vars = "num_vertices",
38        num_constraints = "num_arcs + num_vertices",
39    },
40    upper_bound {
41        num_nonzeros = "3 * num_arcs + num_vertices",
42        max_constraint_magnitude_bits = "2",
43    },
44})]
45impl ReduceTo<ILP<bool>> for Kernel {
46    type Result = ReductionKernelToILP;
47
48    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
49        let mut constraints = Vec::new();
50        for (u, v) in self.graph().arcs() {
51            constraints.push(LinearConstraint::le(vec![(u, 1), (v, 1)], 1));
52        }
53        for u in 0..self.num_vertices() {
54            let mut successors = self.graph().successors(u);
55            successors.sort_unstable();
56            successors.dedup();
57            let mut terms = vec![(u, 1)];
58            terms.extend(successors.into_iter().map(|v| (v, 1)));
59            constraints.push(LinearConstraint::ge(terms, 1));
60        }
61        let target = ILP::new(
62            self.num_vertices(),
63            constraints,
64            vec![],
65            ObjectiveSense::Minimize,
66        )
67        .map_err(Self::target_construction)?;
68        Ok(Self::Result { target })
69    }
70}
71
72#[cfg(feature = "example-db")]
73pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
74    use crate::topology::DirectedGraph;
75    vec![crate::example_db::specs::RuleExampleSpec {
76        id: "kernel_to_ilp",
77        build: || {
78            let source = Kernel::new(DirectedGraph::new(3, vec![(0, 1), (1, 2)]));
79            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
80        },
81    }]
82}
83
84#[cfg(test)]
85#[path = "../unit_tests/rules/kernel_ilp.rs"]
86mod tests;
problemreductions/rules/kernel_ilp.rs

problemreductions/rules/
kernel_ilp.rs
