pumpkin_core/branching/variable_selection/
random.rs

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

pumpkin_core/branching/variable_selection/
random.rs
