pumpkin-core 0.4.0

The core of the Pumpkin constraint programming solver.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

use std::fmt::Debug;

use enum_map::Enum;

#[cfg(doc)]
use crate::Solver;
#[cfg(doc)]
use crate::basic_types::Random;
use crate::basic_types::SolutionReference;
#[cfg(doc)]
use crate::branching;
use crate::branching::SelectionContext;
#[cfg(doc)]
use crate::branching::branchers::dynamic_brancher::DynamicBrancher;
#[cfg(doc)]
use crate::branching::value_selection::ValueSelector;
#[cfg(doc)]
use crate::branching::variable_selection::VariableSelector;
#[cfg(doc)]
use crate::create_statistics_struct;
use crate::engine::predicates::predicate::Predicate;
use crate::engine::variables::DomainId;
#[cfg(doc)]
use crate::results::solution_iterator::SolutionIterator;
use crate::statistics::StatisticLogger;

/// A trait for definining a branching strategy (oftentimes utilising a [`VariableSelector`] and a
/// [`ValueSelector`]).
///
/// In general, implementations of this trait define how the search of the solver proceeds (i.e. it
/// controls how the solver determines which part of the search space to explore). It is required
/// that the resulting decision creates a smaller domain for at least 1 of the variables (and more
/// domains can be affected due to subsequent inference). See [`branching`] for
/// example usages.
///
/// If the [`Brancher`] (or any component thereof) is implemented incorrectly then the
/// behaviour of the solver is undefined.
pub trait Brancher: Debug {
    /// Logs statistics of the brancher using the provided [`StatisticLogger`].
    ///
    /// It is recommended to create a struct through the [`create_statistics_struct!`] macro!
    fn log_statistics(&self, _statistic_logger: StatisticLogger) {}

    /// Returns the next decision concerning a single variable and value; it returns the
    /// [`Predicate`] corresponding to this decision (or [`None`] if all variables under
    /// consideration are assigned).
    ///
    /// Note that this method **cannot** perform the assignment of the decision, it should only
    /// return a suggestion in the form of a [`Predicate`]; the [`SelectionContext`] is
    /// only mutable to account for the usage of random generators (e.g. see [`Random`]).
    fn next_decision(&mut self, context: &mut SelectionContext) -> Option<Predicate>;

    /// A function which is called after a conflict has been found and processed but (currently)
    /// does not provide any additional information.
    ///
    /// To receive information about this event, use [`BrancherEvent::Conflict`] in
    /// [`Self::subscribe_to_events`]
    fn on_conflict(&mut self) {}

    /// A function which is called whenever a backtrack occurs in the [`Solver`].
    ///
    /// To receive information about this event, use [`BrancherEvent::Backtrack`] in
    /// [`Self::subscribe_to_events`]
    fn on_backtrack(&mut self) {}

    /// This method is called when a solution is found; this will either be called when a new
    /// incumbent solution is found (i.e. a solution with a better objective value than previously
    /// known) or when a new solution is found when iterating over solutions using
    /// [`SolutionIterator`].
    ///
    /// To receive information about this event, use [`BrancherEvent::Solution`] in
    /// [`Self::subscribe_to_events`]
    fn on_solution(&mut self, _solution: SolutionReference) {}

    /// A function which is called after a [`DomainId`] is unassigned during backtracking (i.e. when
    /// it was fixed but is no longer), specifically, it provides `variable` which is the
    /// [`DomainId`] which has been reset and `value` which is the value to which the variable was
    /// previously fixed. This method could thus be called multiple times in a single
    /// backtracking operation by the solver.
    ///
    /// To receive information about this event, use [`BrancherEvent::UnassignInteger`] in
    /// [`Self::subscribe_to_events`]
    fn on_unassign_integer(&mut self, _variable: DomainId, _value: i32) {}

    /// A function which is called when a [`Predicate`] appears in a conflict during conflict
    /// analysis.
    ///
    /// To receive information about this event, use
    /// [`BrancherEvent::AppearanceInConflictPredicate`] in [`Self::subscribe_to_events`]
    fn on_appearance_in_conflict_predicate(&mut self, _predicate: Predicate) {}

    /// This method is called whenever a restart is performed.
    /// To receive information about this event, use [`BrancherEvent::Restart`] in
    /// [`Self::subscribe_to_events`]
    fn on_restart(&mut self) {}

    /// Called after backtracking.
    /// Used to reset internal data structures to account for the backtrack.
    ///
    /// To receive information about this event, use [`BrancherEvent::Synchronise`] in
    /// [`Self::subscribe_to_events`]
    fn synchronise(&mut self, _context: &mut SelectionContext) {}

    /// This method returns whether a restart is *currently* pointless for the [`Brancher`].
    ///
    /// For example, if a [`Brancher`] is using a static search strategy then a restart is
    /// pointless; however, if a [`Brancher`] is using a variable selector which
    /// changes throughout the search process then restarting is not pointless.
    ///
    /// Note that even if the [`Brancher`] has indicated that a restart is pointless, it could be
    /// that the restart is still performed (e.g. if this [`Brancher`] is a subcomponent of another
    /// [`Brancher`] and it is not the only `is_restart_pointless` response which is taken into
    /// account).
    fn is_restart_pointless(&mut self) -> bool {
        true
    }

    /// Indicates which [`BrancherEvent`] are relevant for this particular [`Brancher`].
    ///
    /// This can be used by [`Brancher::subscribe_to_events`] to determine upon which
    /// events which [`VariableSelector`] should be called.
    fn subscribe_to_events(&self) -> Vec<BrancherEvent>;
}

/// The events which can occur for a [`Brancher`]. Used for returning which events are relevant in
/// [`Brancher::subscribe_to_events`], [`VariableSelector::subscribe_to_events`],
/// and [`ValueSelector::subscribe_to_events`].
#[derive(Debug, Clone, Copy, Enum, Hash, PartialEq, Eq)]
pub enum BrancherEvent {
    /// Event for when a conflict is detected
    Conflict,
    /// Event for when a backtrack is performed
    Backtrack,
    /// Event for when a solution has been found
    Solution,
    /// Event for when an integer variable has become unassigned
    UnassignInteger,
    /// Event for when a predicate appears during conflict analysis
    AppearanceInConflictPredicate,
    /// Event for when a restart occurs
    Restart,
    /// Event which is called with the new state after a backtrack has occurred
    Synchronise,
}