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

pumpkin_core/branching/variable_selection/
largest.rs
