pumpkin_core/branching/variable_selection/
most_constrained.rs

1use std::cmp::Ordering;
2
3use log::warn;
4
5use crate::branching::SelectionContext;
6use crate::branching::brancher::BrancherEvent;
7use crate::branching::tie_breaking::Direction;
8use crate::branching::tie_breaking::InOrderTieBreaker;
9use crate::branching::tie_breaking::TieBreaker;
10#[cfg(doc)]
11use crate::branching::variable_selection::FirstFail;
12use crate::branching::variable_selection::VariableSelector;
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(),
59            num_occurrences.len(),
60            "The number of variables and the number of elements in num_occurrences for the MostConstrained variable selector should be the same"
61        );
62        if variables.is_empty() {
63            warn!("The MostConstrained variable selector was not provided with any variables");
64        }
65        MostConstrained {
66            variables: variables.to_vec(),
67            tie_breaker: InOrderTieBreaker::new(Direction::Minimum),
68            num_occurrences: num_occurrences.to_vec(),
69        }
70    }
71}
72
73impl<TieBreaking> VariableSelector<DomainId> for MostConstrained<DomainId, TieBreaking>
74where
75    TieBreaking: TieBreaker<DomainId, MostConstrainedValue>,
76{
77    fn select_variable(&mut self, context: &mut SelectionContext) -> Option<DomainId> {
78        self.variables
79            .iter()
80            .enumerate()
81            .filter(|(_, variable)| !context.is_integer_fixed(**variable))
82            .for_each(|(index, variable)| {
83                self.tie_breaker.consider(
84                    *variable,
85                    MostConstrainedValue {
86                        domain_size: context.get_size_of_domain(*variable),
87                        number_of_attached_constraints: self.num_occurrences[index],
88                    },
89                );
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), (15, 20)]);
110        let mut test_rng = TestRandom::default();
111        let integer_variables = assignments.get_domains().collect::<Vec<_>>();
112        let mut strategy = MostConstrained::new(&integer_variables, &[2, 1]);
113
114        {
115            let mut context = SelectionContext::new(&assignments, &mut test_rng);
116
117            let selected = strategy.select_variable(&mut context);
118            assert!(selected.is_some());
119            assert_eq!(selected.unwrap(), integer_variables[1]);
120        }
121
122        let _ = assignments.post_predicate(
123            predicate!(integer_variables[0] <= 2),
124            None,
125            &mut notification_engine,
126        );
127        let mut context = SelectionContext::new(&assignments, &mut test_rng);
128        let selected = strategy.select_variable(&mut context);
129        assert!(selected.is_some());
130        assert_eq!(selected.unwrap(), integer_variables[0]);
131    }
132
133    #[test]
134    fn test_correctly_selected_tie() {
135        let (assignments, _) = SelectionContext::create_for_testing(vec![(0, 10), (10, 20)]);
136        let mut test_rng = TestRandom::default();
137        let mut context = SelectionContext::new(&assignments, &mut test_rng);
138        let integer_variables = context.get_domains().collect::<Vec<_>>();
139
140        let mut strategy = MostConstrained::new(&integer_variables, &[2, 1]);
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 = MostConstrained::new(&integer_variables, &[1, 2]);
154        let selected = strategy.select_variable(&mut context);
155        assert!(selected.is_none());
156    }
157}
pumpkin_core/branching/variable_selection/most_constrained.rs

pumpkin_core/branching/variable_selection/
most_constrained.rs
