pumpkin_core/branching/variable_selection/
random.rs

1use super::VariableSelector;
2use crate::branching::BrancherEvent;
3use crate::branching::SelectionContext;
4use crate::containers::SparseSet;
5use crate::variables::DomainId;
6
7/// A [`VariableSelector`] which selects a random unfixed variable.
8#[derive(Debug)]
9pub struct RandomSelector {
10    variables: SparseSet<DomainId>,
11}
12
13impl RandomSelector {
14    pub fn new(variables: impl IntoIterator<Item = DomainId>) -> Self {
15        // Note the -1 due to the fact that the indices of the domain ids start at 1
16        Self {
17            variables: SparseSet::new(variables.into_iter().collect()),
18        }
19    }
20
21    /// Add a domain to consideration in the variable selection.
22    pub fn add_domain(&mut self, domain: DomainId) {
23        self.variables.insert(domain);
24    }
25}
26
27impl VariableSelector<DomainId> for RandomSelector {
28    fn select_variable(&mut self, context: &mut SelectionContext) -> Option<DomainId> {
29        if self.variables.is_empty() {
30            return None;
31        }
32
33        let mut variable = *self.variables.get(
34            context
35                .random()
36                .generate_usize_in_range(0..self.variables.len()),
37        );
38
39        while context.is_integer_fixed(variable) {
40            self.variables.remove_temporarily(&variable);
41            if self.variables.is_empty() {
42                return None;
43            }
44
45            variable = *self.variables.get(
46                context
47                    .random()
48                    .generate_usize_in_range(0..self.variables.len()),
49            );
50        }
51
52        Some(variable)
53    }
54
55    fn on_unassign_integer(&mut self, variable: DomainId, _value: i32) {
56        self.variables.insert(variable);
57    }
58
59    fn is_restart_pointless(&mut self) -> bool {
60        false
61    }
62
63    fn subscribe_to_events(&self) -> Vec<BrancherEvent> {
64        vec![BrancherEvent::UnassignInteger]
65    }
66}
67
68#[cfg(test)]
69mod tests {
70    use crate::basic_types::tests::TestRandom;
71    use crate::branching::SelectionContext;
72    use crate::branching::variable_selection::RandomSelector;
73    use crate::branching::variable_selection::VariableSelector;
74    use crate::predicate;
75
76    #[test]
77    fn test_selects_randomly() {
78        let (assignments, _) = SelectionContext::create_for_testing(vec![(0, 10), (5, 20), (1, 3)]);
79        let mut test_rng = TestRandom {
80            usizes: vec![1],
81            ..Default::default()
82        };
83        let integer_variables = assignments.get_domains().collect::<Vec<_>>();
84        let mut strategy = RandomSelector::new(assignments.get_domains());
85
86        let mut context = SelectionContext::new(&assignments, &mut test_rng);
87
88        let selected = strategy.select_variable(&mut context);
89        assert!(selected.is_some());
90        assert_eq!(selected.unwrap(), integer_variables[1]);
91    }
92
93    #[test]
94    fn test_selects_randomly_not_unfixed() {
95        let (assignments, _) = SelectionContext::create_for_testing(vec![(0, 10), (5, 5), (1, 3)]);
96        let mut test_rng = TestRandom {
97            usizes: vec![1, 0],
98            ..Default::default()
99        };
100        let integer_variables = assignments.get_domains().collect::<Vec<_>>();
101        let mut strategy = RandomSelector::new(assignments.get_domains());
102
103        let mut context = SelectionContext::new(&assignments, &mut test_rng);
104
105        let selected = strategy.select_variable(&mut context);
106        assert!(selected.is_some());
107        assert_eq!(selected.unwrap(), integer_variables[0]);
108    }
109
110    #[test]
111    fn test_select_nothing_if_all_fixed() {
112        let (assignments, _) = SelectionContext::create_for_testing(vec![(0, 0), (5, 5), (1, 1)]);
113        let mut test_rng = TestRandom {
114            usizes: vec![1, 0, 0],
115            ..Default::default()
116        };
117        let mut strategy = RandomSelector::new(assignments.get_domains());
118
119        let mut context = SelectionContext::new(&assignments, &mut test_rng);
120
121        let selected = strategy.select_variable(&mut context);
122        assert!(selected.is_none());
123    }
124
125    #[test]
126    fn test_select_unfixed_variable_after_fixing() {
127        let (mut assignments, mut notification_engine) =
128            SelectionContext::create_for_testing(vec![(0, 0), (5, 7), (1, 1)]);
129        let mut test_rng = TestRandom {
130            usizes: vec![2, 0, 0, 0, 0],
131            ..Default::default()
132        };
133        let integer_variables = assignments.get_domains().collect::<Vec<_>>();
134        let mut strategy = RandomSelector::new(assignments.get_domains());
135
136        {
137            let mut context = SelectionContext::new(&assignments, &mut test_rng);
138
139            let selected = strategy.select_variable(&mut context);
140            assert!(selected.is_some());
141            assert_eq!(selected.unwrap(), integer_variables[1]);
142        }
143
144        assignments.new_checkpoint();
145        let _ = assignments.post_predicate(
146            predicate!(integer_variables[1] >= 7),
147            None,
148            &mut notification_engine,
149        );
150
151        {
152            let mut context = SelectionContext::new(&assignments, &mut test_rng);
153
154            let selected = strategy.select_variable(&mut context);
155            assert!(selected.is_none());
156        }
157
158        let _ = assignments.synchronise(0, &mut notification_engine);
159        strategy.on_unassign_integer(integer_variables[1], 7);
160        let mut context = SelectionContext::new(&assignments, &mut test_rng);
161        let selected = strategy.select_variable(&mut context);
162        assert!(selected.is_some());
163        assert_eq!(selected.unwrap(), integer_variables[1]);
164    }
165}
pumpkin_core/branching/variable_selection/random.rs

pumpkin_core/branching/variable_selection/
random.rs
