pumpkin_core/branching/variable_selection/
first_fail.rs

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

pumpkin_core/branching/variable_selection/
first_fail.rs
