problemreductions/rules/
twodimensionalconsecutivesets_ilp.rs

1//! Distinct labels within a subset occupy an interval of that subset's size.
2
3use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
4use crate::models::set::TwoDimensionalConsecutiveSets;
5use crate::rules::ilp_helpers::{bounded_order_comparison, decode_usize_values};
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionTwoDimensionalConsecutiveSetsToILP {
10    target: ILP<i64, i64, Bounded>,
11    alphabet_size: usize,
12}
13impl ReductionResult for ReductionTwoDimensionalConsecutiveSetsToILP {
14    type Source = TwoDimensionalConsecutiveSets;
15    type Target = ILP<i64, i64, Bounded>;
16    fn target_problem(&self) -> &Self::Target {
17        &self.target
18    }
19    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<usize>> {
20        crate::rules::traits::validate_target_witness(
21            &self.target,
22            solution,
23            |value| value.value.is_some(),
24            "target ILP assignment is infeasible",
25        )?;
26        decode_usize_values(&solution[..self.alphabet_size])
27    }
28}
29#[crate::aggregate_reduction(ilp_feasibility)]
30impl crate::rules::AggregateReductionResult for ReductionTwoDimensionalConsecutiveSetsToILP {}
31
32// P=sum_S choose(|S|,2) <= num_subsets * choose(alphabet_size,2).
33#[crate::reduction(transform = upper_bound {
34    num_vars = "alphabet_size + num_subsets * alphabet_size * (alphabet_size - 1) / 2",
35    num_constraints = "2 * num_subsets * alphabet_size * (alphabet_size - 1)",
36    num_nonzeros = "5 * num_subsets * alphabet_size * (alphabet_size - 1)",
37    max_constraint_magnitude_bits = "alphabet_size",
38})]
39impl ReduceTo<ILP<i64, i64, Bounded>> for TwoDimensionalConsecutiveSets {
40    type Result = ReductionTwoDimensionalConsecutiveSetsToILP;
41    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
42        let n = self.alphabet_size();
43        let bound = Self::exact_i64(n, "bounding group labels")?;
44        let mut variables = vec![
45            IntegerVariable::new(Some(0), Some(bound - 1))
46                .map_err(Self::target_construction)?;
47            n
48        ];
49        let mut constraints = Vec::new();
50        for subset in self.subsets() {
51            let width = Self::exact_i64(subset.len().saturating_sub(1), "bounding subset span")?;
52            for (i, &u) in subset.iter().enumerate() {
53                for &v in &subset[i + 1..] {
54                    let selector = variables.len();
55                    variables.push(IntegerVariable::binary());
56                    constraints.extend(bounded_order_comparison(u, v, selector, bound));
57                    constraints.push(LinearConstraint::le(vec![(v, 1), (u, -1)], width));
58                    constraints.push(LinearConstraint::le(vec![(u, 1), (v, -1)], width));
59                }
60            }
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            alphabet_size: 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: "twodimensionalconsecutivesets_to_ilp",
76        build: || {
77            crate::example_db::specs::rule_example_via_bounded_ilp(
78                TwoDimensionalConsecutiveSets::new(3, vec![vec![0, 1], vec![1, 2]]),
79            )
80        },
81    }]
82}
83
84#[cfg(test)]
85#[path = "../unit_tests/rules/twodimensionalconsecutivesets_ilp.rs"]
86mod tests;
problemreductions/rules/twodimensionalconsecutivesets_ilp.rs

problemreductions/rules/
twodimensionalconsecutivesets_ilp.rs
