problemreductions/rules/
betweenness_ilp.rs

1//! One orientation selector per betweenness triple, with bounded element ranks.
2
3use crate::models::algebraic::{Bounded, IntegerVariable, ObjectiveSense, ILP};
4use crate::models::misc::Betweenness;
5use crate::rules::ilp_helpers::{bounded_order_comparison, ranks_to_positions};
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionBetweennessToILP {
10    target: ILP<i64, i64, Bounded>,
11    num_elements: usize,
12}
13
14impl ReductionResult for ReductionBetweennessToILP {
15    type Source = Betweenness;
16    type Target = ILP<i64, i64, Bounded>;
17    fn target_problem(&self) -> &Self::Target {
18        &self.target
19    }
20    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<usize>> {
21        crate::rules::traits::validate_target_witness(
22            &self.target,
23            solution,
24            |value| value.value.is_some(),
25            "target ILP assignment is infeasible",
26        )?;
27        Ok(ranks_to_positions(&solution[..self.num_elements]))
28    }
29}
30#[crate::aggregate_reduction(ilp_feasibility)]
31impl crate::rules::AggregateReductionResult for ReductionBetweennessToILP {}
32
33#[crate::reduction(transform = {
34    exact {
35        num_vars = "num_elements + num_triples",
36        num_constraints = "4 * num_triples",
37        num_nonzeros = "12 * num_triples",
38    },
39    upper_bound { max_constraint_magnitude_bits = "num_elements", },
40})]
41impl ReduceTo<ILP<i64, i64, Bounded>> for Betweenness {
42    type Result = ReductionBetweennessToILP;
43    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
44        let n = self.num_elements();
45        let count = n.checked_add(self.num_triples()).ok_or_else(|| {
46            crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
47                "counting betweenness variables",
48            )
49        })?;
50        let bound = Self::exact_i64(n, "bounding ordering ranks")?;
51        let mut variables = vec![
52            IntegerVariable::new(Some(0), Some(bound - 1))
53                .map_err(Self::target_construction)?;
54            n
55        ];
56        variables.resize(count, IntegerVariable::binary());
57        let mut constraints = Vec::new();
58        for (index, &(a, b, c)) in self.triples().iter().enumerate() {
59            constraints.extend(bounded_order_comparison(a, b, n + index, bound));
60            constraints.extend(bounded_order_comparison(b, c, n + index, bound));
61        }
62        let target = ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
63            .map_err(Self::target_construction)?;
64        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<Self>(&target)?;
65        Ok(Self::Result {
66            target,
67            num_elements: n,
68        })
69    }
70}
71
72#[cfg(feature = "example-db")]
73pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
74    vec![crate::example_db::specs::RuleExampleSpec {
75        id: "betweenness_to_ilp",
76        build: || {
77            crate::example_db::specs::rule_example_via_bounded_ilp(Betweenness::new(
78                3,
79                vec![(0, 1, 2)],
80            ))
81        },
82    }]
83}
84
85#[cfg(test)]
86#[path = "../unit_tests/rules/betweenness_ilp.rs"]
87mod tests;
problemreductions/rules/betweenness_ilp.rs

problemreductions/rules/
betweenness_ilp.rs
