pumpkin_core/branching/variable_selection/
most_constrained.rs

1use std::cmp::Ordering;
2
3use log::warn;
4
5use crate::branching::brancher::BrancherEvent;
6use crate::branching::tie_breaking::Direction;
7use crate::branching::tie_breaking::InOrderTieBreaker;
8use crate::branching::tie_breaking::TieBreaker;
9#[cfg(doc)]
10use crate::branching::variable_selection::FirstFail;
11use crate::branching::variable_selection::VariableSelector;
12use crate::branching::SelectionContext;
13use crate::engine::variables::DomainId;
14use crate::pumpkin_assert_eq_simple;
15
16/// A [`VariableSelector`] which selects the variable with the smallest domain (similar to
17/// [`FirstFail`]).
18///
19/// It breaks ties according to the number of attached
20/// constraints (giving priority to variable with more attached constraints).
21pub struct MostConstrained<Var, TieBreaking> {
22    variables: Vec<Var>,
23    tie_breaker: TieBreaking,
24    num_occurrences: Vec<u32>,
25}
26
27impl<Var, TieBreaking> std::fmt::Debug for MostConstrained<Var, TieBreaking> {
28    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
29        f.debug_struct("MostConstrained").finish()
30    }
31}
32
33#[derive(PartialEq)]
34struct MostConstrainedValue {
35    domain_size: i32,
36    number_of_attached_constraints: u32,
37}
38
39impl PartialOrd for MostConstrainedValue {
40    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
41        match self.domain_size.cmp(&other.domain_size) {
42            Ordering::Equal => Some(
43                // Note that we are comparing `other` to `self` instead of the normal `self` to
44                // `other`, this is because the tie-breaking is minimizing while we want to
45                // tie-break in the maximizing direction.
46                other
47                    .number_of_attached_constraints
48                    .cmp(&self.number_of_attached_constraints),
49            ),
50            ordering => Some(ordering),
51        }
52    }
53}
54
55impl<Var: Copy + 'static> MostConstrained<Var, InOrderTieBreaker<Var, MostConstrainedValue>> {
56    pub fn new(variables: &[Var], num_occurrences: &[u32]) -> Self {
57        pumpkin_assert_eq_simple!(
58            variables.len(), num_occurrences.len(),
59            "The number of variables and the number of elements in num_occurrences for the MostConstrained variable selector should be the same"
60        );
61        if variables.is_empty() {
62            warn!("The MostConstrained variable selector was not provided with any variables");
63        }
64        MostConstrained {
65            variables: variables.to_vec(),
66            tie_breaker: InOrderTieBreaker::new(Direction::Minimum),
67            num_occurrences: num_occurrences.to_vec(),
68        }
69    }
70}
71
72impl<TieBreaking> VariableSelector<DomainId> for MostConstrained<DomainId, TieBreaking>
73where
74    TieBreaking: TieBreaker<DomainId, MostConstrainedValue>,
75{
76    fn select_variable(&mut self, context: &mut SelectionContext) -> Option<DomainId> {
77        self.variables
78            .iter()
79            .enumerate()
80            .filter(|(_, variable)| !context.is_integer_fixed(**variable))
81            .for_each(|(index, variable)| {
82                self.tie_breaker.consider(
83                    *variable,
84                    MostConstrainedValue {
85                        domain_size: context.get_size_of_domain(*variable),
86                        number_of_attached_constraints: self.num_occurrences[index],
87                    },
88                );
89            });
90
91        self.tie_breaker.select()
92    }
93
94    fn subscribe_to_events(&self) -> Vec<BrancherEvent> {
95        vec![]
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102    use crate::basic_types::tests::TestRandom;
103    use crate::predicate;
104
105    #[test]
106    fn test_correctly_selected() {
107        let (mut assignments, mut notification_engine) =
108            SelectionContext::create_for_testing(vec![(0, 10), (15, 20)]);
109        let mut test_rng = TestRandom::default();
110        let integer_variables = assignments.get_domains().collect::<Vec<_>>();
111        let mut strategy = MostConstrained::new(&integer_variables, &[2, 1]);
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[1]);
119        }
120
121        let _ = assignments.post_predicate(
122            predicate!(integer_variables[0] <= 2),
123            None,
124            &mut notification_engine,
125        );
126        let mut context = SelectionContext::new(&assignments, &mut test_rng);
127        let selected = strategy.select_variable(&mut context);
128        assert!(selected.is_some());
129        assert_eq!(selected.unwrap(), integer_variables[0]);
130    }
131
132    #[test]
133    fn test_correctly_selected_tie() {
134        let (assignments, _) = SelectionContext::create_for_testing(vec![(0, 10), (10, 20)]);
135        let mut test_rng = TestRandom::default();
136        let mut context = SelectionContext::new(&assignments, &mut test_rng);
137        let integer_variables = context.get_domains().collect::<Vec<_>>();
138
139        let mut strategy = MostConstrained::new(&integer_variables, &[2, 1]);
140        let selected = strategy.select_variable(&mut context);
141        assert!(selected.is_some());
142        assert_eq!(selected.unwrap(), integer_variables[0])
143    }
144
145    #[test]
146    fn fixed_variables_are_not_selected() {
147        let (assignments, _) = SelectionContext::create_for_testing(vec![(10, 10), (20, 20)]);
148        let mut test_rng = TestRandom::default();
149        let mut context = SelectionContext::new(&assignments, &mut test_rng);
150        let integer_variables = context.get_domains().collect::<Vec<_>>();
151
152        let mut strategy = MostConstrained::new(&integer_variables, &[1, 2]);
153        let selected = strategy.select_variable(&mut context);
154        assert!(selected.is_none());
155    }
156}
pumpkin_core/branching/variable_selection/most_constrained.rs

pumpkin_core/branching/variable_selection/
most_constrained.rs
