pumpkin_solver/branching/
mod.rs

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
//! Contains structures and traits to define the decision making procedure of the [`Solver`].
//!
//! In general, it provides 3 traits:
//! - The [`Brancher`] which defines how a branching procedure (which selects an unfixed variable and splits the domain in some way, see [Section 4.3.1 of \[1\]](http://www.cse.unsw.com.au/~tw/brwhkr08.pdf)
//!   for more information) should operate; the main method of this trait is the [`Brancher::next_decision`] method. An example implementation of this trait is the [`IndependentVariableValueBrancher`].
//! - The [`VariableSelector`] which defines the method required of a variable selector (including
//!   the hooks into the solver); the main method of this trait is the
//!   [`VariableSelector::select_variable`] method. An example implementation of this trait is the
//!   [`Vsids`] strategy.
//! - The [`ValueSelector`] which defines the method required of a value selector (including the
//!   hooks into the solver); the main method of this trait is the [`ValueSelector::select_value`]
//!   method.
//!
//! A [`Brancher`] is expected to be passed to [`Solver::satisfy`], [`Solver::maximise`], and
//! [`Solver::minimise`]:
//! ```rust
//! # use pumpkin_solver::Solver;
//! # use pumpkin_solver::variables::PropositionalVariable;
//! # use pumpkin_solver::branching::variable_selection::Vsids;
//! # use pumpkin_solver::branching::value_selection::PhaseSaving;
//! # use pumpkin_solver::branching::branchers::independent_variable_value_brancher::IndependentVariableValueBrancher;
//! # use pumpkin_solver::variables::Literal;
//! # use pumpkin_solver::termination::Indefinite;
//! # use pumpkin_solver::results::SatisfactionResult;
//! # use crate::pumpkin_solver::results::ProblemSolution;
//! let mut solver = Solver::default();
//!
//! let variables = vec![solver.new_literal().get_propositional_variable()];
//!
//! let mut termination = Indefinite;
//! let mut brancher = IndependentVariableValueBrancher::new(
//!     Vsids::new(&variables),
//!     PhaseSaving::new(&variables),
//! );
//! let result = solver.satisfy(&mut brancher, &mut termination);
//! if let SatisfactionResult::Satisfiable(solution) = result {
//!     // Getting the value of the literal in the solution should not panic
//!     variables.into_iter().for_each(|variable| {
//!         solver.get_literal_value(Literal::new(variable, true));
//!     });
//! } else {
//!     panic!("Solving should have returned satsifiable")
//! }
//! ```
//!
//!
//! A default implementation of a [`Brancher`]
//! is provided using the method
//! [`Solver::default_brancher_over_all_propositional_variables`].
//! ```rust
//! # use pumpkin_solver::Solver;
//! # use pumpkin_solver::variables::PropositionalVariable;
//! # use pumpkin_solver::branching::branchers::independent_variable_value_brancher::IndependentVariableValueBrancher;
//! # use pumpkin_solver::variables::Literal;
//! # use pumpkin_solver::termination::Indefinite;
//! # use pumpkin_solver::results::SatisfactionResult;
//! # use crate::pumpkin_solver::results::ProblemSolution;
//! let mut solver = Solver::default();
//!
//! let literals = vec![solver.new_literal()];
//!
//! let mut termination = Indefinite;
//! let mut brancher = solver.default_brancher_over_all_propositional_variables();
//! let result = solver.satisfy(&mut brancher, &mut termination);
//! if let SatisfactionResult::Satisfiable(solution) = result {
//!     // Getting the value of the literal in the solution should not panic
//!     literals.into_iter().for_each(|literal| {
//!         solution.get_literal_value(literal);
//!     })
//! } else {
//!     panic!("Solving should have returned satsifiable")
//! }
//! ```
//!
//! \[1\] F. Rossi, P. Van Beek, and T. Walsh, Handbook of constraint programming. Elsevier, 2006.

mod brancher;
pub mod branchers;
mod selection_context;
pub mod tie_breaking;
pub mod value_selection;
pub mod variable_selection;

pub use brancher::Brancher;
pub use selection_context::SelectionContext;
pub use tie_breaking::*;
pub use value_selection::*;
pub use variable_selection::*;

#[cfg(doc)]
use crate::branching::branchers::independent_variable_value_brancher::IndependentVariableValueBrancher;
#[cfg(doc)]
use crate::branching::value_selection::ValueSelector;
#[cfg(doc)]
use crate::branching::variable_selection::VariableSelector;
#[cfg(doc)]
use crate::Solver;