pumpkin_core/branching/variable_selection/
smallest.rs

1use log::warn;
2
3use super::VariableSelector;
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::SelectionContext;
9use crate::engine::variables::DomainId;
10use crate::pumpkin_assert_eq_simple;
11
12/// A [`VariableSelector`] which selects the variable with the smallest value in its domain.
13///
14/// Uses a [`TieBreaker`] to break ties, the default is the [`InOrderTieBreaker`] but it is
15/// possible to construct the variable selector with a custom [`TieBreaker`] by using
16/// the method [`Smallest::with_tie_breaker`].
17pub struct Smallest<Var, TieBreaking> {
18    variables: Vec<Var>,
19    tie_breaker: TieBreaking,
20}
21
22impl<Var, TieBreaking> std::fmt::Debug for Smallest<Var, TieBreaking> {
23    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
24        f.debug_struct("Smallest").finish()
25    }
26}
27
28impl<Var: Clone> Smallest<Var, InOrderTieBreaker<Var, i32>> {
29    pub fn new(variables: &[Var]) -> Self {
30        if variables.is_empty() {
31            warn!("The Smallest variable selector was not provided with any variables");
32        }
33        Smallest {
34            variables: variables.to_vec(),
35            tie_breaker: InOrderTieBreaker::new(Direction::Minimum),
36        }
37    }
38}
39
40impl<Var: Clone + 'static, TieBreaking: TieBreaker<Var, i32>> Smallest<Var, TieBreaking> {
41    pub fn with_tie_breaker(variables: &[Var], tie_breaker: TieBreaking) -> Self {
42        pumpkin_assert_eq_simple!(
43            tie_breaker.get_direction(),
44            Direction::Minimum,
45            "The provided tie-breaker to Smallest attempts to find the Maximum value
46             instead of the Minimum value, please ensure that you have passed the correct tie-breaker");
47        if variables.is_empty() {
48            warn!("The Smallest variable selector was not provided with any variables");
49            return Smallest {
50                variables: vec![],
51                tie_breaker,
52            };
53        }
54
55        Self {
56            variables: variables.to_vec(),
57            tie_breaker,
58        }
59    }
60}
61
62impl<TieBreaking> VariableSelector<DomainId> for Smallest<DomainId, TieBreaking>
63where
64    TieBreaking: TieBreaker<DomainId, i32>,
65{
66    fn select_variable(&mut self, context: &mut SelectionContext) -> Option<DomainId> {
67        self.variables
68            .iter()
69            .filter(|variable| !context.is_integer_fixed(**variable))
70            .for_each(|variable| {
71                self.tie_breaker
72                    .consider(*variable, context.lower_bound(*variable));
73            });
74        self.tie_breaker.select()
75    }
76
77    fn subscribe_to_events(&self) -> Vec<BrancherEvent> {
78        vec![]
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85    use crate::basic_types::tests::TestRandom;
86    use crate::predicate;
87
88    #[test]
89    fn test_correctly_selected() {
90        let (mut assignments, mut notification_engine) =
91            SelectionContext::create_for_testing(vec![(11, 15), (10, 20)]);
92        let integer_variables = assignments.get_domains().collect::<Vec<_>>();
93        let mut strategy = Smallest::new(&integer_variables);
94        let mut test_rng = TestRandom::default();
95        {
96            let mut context = SelectionContext::new(&assignments, &mut test_rng);
97
98            let selected = strategy.select_variable(&mut context);
99            assert!(selected.is_some());
100            assert_eq!(selected.unwrap(), integer_variables[1]);
101        }
102
103        let _ = assignments.post_predicate(
104            predicate!(integer_variables[1] >= 15),
105            None,
106            &mut notification_engine,
107        );
108        let mut context = SelectionContext::new(&assignments, &mut test_rng);
109        let selected = strategy.select_variable(&mut context);
110        assert!(selected.is_some());
111        assert_eq!(selected.unwrap(), integer_variables[0]);
112    }
113
114    #[test]
115    fn fixed_variables_are_not_selected() {
116        let (assignments, _) = SelectionContext::create_for_testing(vec![(10, 10), (20, 20)]);
117        let mut test_rng = TestRandom::default();
118        let mut context = SelectionContext::new(&assignments, &mut test_rng);
119        let integer_variables = context.get_domains().collect::<Vec<_>>();
120
121        let mut strategy = Smallest::new(&integer_variables);
122        let selected = strategy.select_variable(&mut context);
123        assert!(selected.is_none());
124    }
125}
pumpkin_core/branching/variable_selection/smallest.rs

pumpkin_core/branching/variable_selection/
smallest.rs
