pumpkin_core/branching/variable_selection/
occurrence.rs

1use log::warn;
2
3use crate::branching::SelectionContext;
4use crate::branching::brancher::BrancherEvent;
5use crate::branching::tie_breaking::Direction;
6use crate::branching::tie_breaking::InOrderTieBreaker;
7use crate::branching::tie_breaking::TieBreaker;
8use crate::branching::variable_selection::VariableSelector;
9use crate::engine::variables::DomainId;
10use crate::pumpkin_assert_eq_simple;
11
12/// A [`VariableSelector`] which selects the variable with the largest number of attached
13/// constraints (where the provided `num_occurrences` stores the number of
14/// attached constraints per variable).
15pub struct Occurrence<Var, TieBreaking> {
16    variables: Vec<Var>,
17    tie_breaker: TieBreaking,
18    num_occurrences: Vec<u32>,
19}
20
21impl<Var, TieBreaking> std::fmt::Debug for Occurrence<Var, TieBreaking> {
22    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
23        f.debug_struct("Occurrence").finish()
24    }
25}
26
27impl<Var: Copy> Occurrence<Var, InOrderTieBreaker<Var, u32>> {
28    pub fn new(variables: &[Var], num_occurrences: &[u32]) -> Self {
29        pumpkin_assert_eq_simple!(
30            variables.len(),
31            num_occurrences.len(),
32            "The number of variables and the number of elements in num_occurrences for the Occurence variable selector should be the same"
33        );
34        if variables.is_empty() {
35            warn!("The Occurence variable selector was not provided with any variables");
36        }
37        Occurrence {
38            variables: variables.to_vec(),
39            tie_breaker: InOrderTieBreaker::new(Direction::Maximum),
40            num_occurrences: num_occurrences.to_vec(),
41        }
42    }
43}
44
45impl<TieBreaking> VariableSelector<DomainId> for Occurrence<DomainId, TieBreaking>
46where
47    TieBreaking: TieBreaker<DomainId, u32>,
48{
49    fn select_variable(&mut self, context: &mut SelectionContext) -> Option<DomainId> {
50        self.variables
51            .iter()
52            .enumerate()
53            .filter(|(_, variable)| !context.is_integer_fixed(**variable))
54            .for_each(|(index, variable)| {
55                self.tie_breaker
56                    .consider(*variable, self.num_occurrences[index])
57            });
58        self.tie_breaker.select()
59    }
60
61    fn subscribe_to_events(&self) -> Vec<BrancherEvent> {
62        vec![]
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69    use crate::basic_types::tests::TestRandom;
70
71    #[test]
72    fn test_correctly_selected() {
73        let (assignments, _) = SelectionContext::create_for_testing(vec![(0, 10), (10, 20)]);
74        let mut test_rng = TestRandom::default();
75        let mut context = SelectionContext::new(&assignments, &mut test_rng);
76        let integer_variables = context.get_domains().collect::<Vec<_>>();
77
78        let mut strategy = Occurrence::new(&integer_variables, &[2, 1]);
79        let selected = strategy.select_variable(&mut context);
80        assert!(selected.is_some());
81        assert_eq!(selected.unwrap(), integer_variables[0])
82    }
83
84    #[test]
85    fn fixed_variables_are_not_selected() {
86        let (assignments, _) = SelectionContext::create_for_testing(vec![(10, 10), (20, 20)]);
87        let mut test_rng = TestRandom::default();
88        let mut context = SelectionContext::new(&assignments, &mut test_rng);
89        let integer_variables = context.get_domains().collect::<Vec<_>>();
90
91        let mut strategy = Occurrence::new(&integer_variables, &[1, 2]);
92        let selected = strategy.select_variable(&mut context);
93        assert!(selected.is_none());
94    }
95}
pumpkin_core/branching/variable_selection/occurrence.rs

pumpkin_core/branching/variable_selection/
occurrence.rs
