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

pumpkin_core/branching/variable_selection/
max_regret.rs
