pumpkin_core/propagators/hypercube_linear/
linear.rs

1use std::num::NonZero;
2
3use crate::containers::HashMap;
4use crate::variables::AffineView;
5use crate::variables::DomainId;
6use crate::variables::TransformableVariable;
7
8/// The linear inequality part of a hypercube linear constraint.
9#[derive(Clone, Debug)]
10pub struct LinearInequality {
11    terms: Box<[AffineView<DomainId>]>,
12    bound: i32,
13}
14
15impl LinearInequality {
16    /// Create a linear inequality that is trivially false.
17    pub fn trivially_false() -> LinearInequality {
18        LinearInequality {
19            terms: [].into(),
20            bound: -1,
21        }
22    }
23
24    /// Construct a new linear inequality.
25    ///
26    /// If the terms simplify to 0 and the `bound` is at least 0, then `None` is returned.
27    pub fn new(
28        terms: impl IntoIterator<Item = (NonZero<i32>, DomainId)>,
29        bound: i32,
30    ) -> Option<Self> {
31        // To merge terms with the same domain, we go through a HashMap mapping the weight to the
32        // domain.
33        let mut domain_to_weight = HashMap::new();
34
35        for (weight, domain_id) in terms {
36            let existing_weight = domain_to_weight.entry(domain_id).or_insert(0);
37            *existing_weight += weight.get();
38        }
39
40        let terms = domain_to_weight
41            .into_iter()
42            .filter(|&(_, weight)| weight != 0)
43            .map(|(domain, weight)| domain.scaled(weight))
44            .collect::<Box<[_]>>();
45
46        if terms.is_empty() && bound >= 0 {
47            return None;
48        }
49
50        Some(LinearInequality { terms, bound })
51    }
52
53    /// Iterate over the terms in the linear inequality.
54    pub fn terms(&self) -> impl Iterator<Item = AffineView<DomainId>> + '_ {
55        self.terms.iter().copied()
56    }
57
58    /// The bound of the linear inequality.
59    pub fn bound(&self) -> i32 {
60        self.bound
61    }
62
63    /// Tests whether the left-hand side simplifies to 0 and the right-hand side is less than 0.
64    pub fn is_trivially_false(&self) -> bool {
65        self.terms.is_empty() && self.bound < 0
66    }
67
68    /// Get the term for the given domain.
69    pub fn term_for_domain(&self, domain: DomainId) -> Option<AffineView<DomainId>> {
70        self.terms().find(|view| view.inner == domain)
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77    use crate::containers::HashSet;
78    use crate::state::State;
79
80    #[test]
81    fn terms_are_iterable() {
82        let mut state = State::default();
83
84        let x = state.new_interval_variable(1, 10, Some("x".into()));
85        let y = state.new_interval_variable(1, 10, Some("y".into()));
86
87        let linear = LinearInequality::new(
88            [(NonZero::new(2).unwrap(), x), (NonZero::new(3).unwrap(), y)],
89            8,
90        )
91        .expect("not trivially true");
92
93        let iterated_terms = linear.terms().collect::<HashSet<_>>();
94
95        assert_eq!(
96            [x.scaled(2), y.scaled(3)]
97                .into_iter()
98                .collect::<HashSet<_>>(),
99            iterated_terms
100        );
101    }
102
103    #[test]
104    fn terms_for_same_variable_are_merged() {
105        let mut state = State::default();
106
107        let x = state.new_interval_variable(1, 10, Some("x".into()));
108
109        let linear = LinearInequality::new(
110            [(NonZero::new(2).unwrap(), x), (NonZero::new(3).unwrap(), x)],
111            8,
112        )
113        .expect("not trivially true");
114
115        let iterated_terms = linear.terms().collect::<HashSet<_>>();
116
117        assert_eq!(
118            [x.scaled(5)].into_iter().collect::<HashSet<_>>(),
119            iterated_terms
120        );
121    }
122
123    #[test]
124    fn trivially_satisfied_linear_inequalities_are_not_created() {
125        let mut state = State::default();
126
127        let x = state.new_interval_variable(1, 10, Some("x".into()));
128
129        let linear = LinearInequality::new(
130            [
131                (NonZero::new(2).unwrap(), x),
132                (NonZero::new(-2).unwrap(), x),
133            ],
134            8,
135        );
136
137        assert!(linear.is_none());
138    }
139
140    #[test]
141    fn trivially_unsatisfied_linear_are_okay() {
142        let mut state = State::default();
143
144        let x = state.new_interval_variable(1, 10, Some("x".into()));
145
146        let linear = LinearInequality::new(
147            [
148                (NonZero::new(2).unwrap(), x),
149                (NonZero::new(-2).unwrap(), x),
150            ],
151            -1,
152        )
153        .expect("not trivially satisfiable");
154
155        assert_eq!(
156            Vec::<AffineView<DomainId>>::new(),
157            linear.terms().collect::<Vec<_>>()
158        );
159    }
160}
pumpkin_core/propagators/hypercube_linear/linear.rs

pumpkin_core/propagators/hypercube_linear/
linear.rs
