problemreductions/rules/
cyclicordering_ilp.rs

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

problemreductions/rules/
cyclicordering_ilp.rs
