pumpkin_core/branching/
mod.rs

1//! Contains structures and traits to define the decision making procedure of the [`Solver`].
2//!
3//! In general, it provides 3 traits:
4//! - 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)
5//!   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`].
6//! - The [`VariableSelector`] which defines the method required of a variable selector (including
7//!   the hooks into the solver); the main method of this trait is the
8//!   [`VariableSelector::select_variable`] method. An example implementation of this trait is the
9//!   [`AntiFirstFail`] strategy.
10//! - The [`ValueSelector`] which defines the method required of a value selector (including the
11//!   hooks into the solver); the main method of this trait is the [`ValueSelector::select_value`]
12//!   method.
13//!
14//! A [`Brancher`] is expected to be passed to [`Solver::satisfy`], and [`Solver::optimise`]:
15//! ```rust
16//! # use pumpkin_solver::Solver;
17//! # use pumpkin_solver::variables::Literal;
18//! # use pumpkin_solver::termination::Indefinite;
19//! # use pumpkin_solver::results::SatisfactionResult;
20//! # use crate::pumpkin_solver::results::ProblemSolution;
21//! let mut solver = Solver::default();
22//!
23//! let variables = vec![solver.new_literal()];
24//!
25//! let mut termination = Indefinite;
26//! let mut brancher = solver.default_brancher();
27//! let result = solver.satisfy(&mut brancher, &mut termination);
28//! if let SatisfactionResult::Satisfiable(satisfiable) = result {
29//!     // Getting the value of the literal in the solution should not panic
30//!     variables.into_iter().for_each(|variable| {
31//!         satisfiable.solution().get_literal_value(variable);
32//!     });
33//! } else {
34//!     panic!("Solving should have returned satsifiable")
35//! }
36//! ```
37//!
38//!
39//! A default implementation of a [`Brancher`]
40//! is provided using the method
41//! [`Solver::default_brancher`].
42//! ```rust
43//! # use pumpkin_solver::Solver;
44//! # use pumpkin_solver::variables::Literal;
45//! # use pumpkin_solver::termination::Indefinite;
46//! # use pumpkin_solver::results::SatisfactionResult;
47//! # use crate::pumpkin_solver::results::ProblemSolution;
48//! let mut solver = Solver::default();
49//!
50//! let literals = vec![solver.new_literal()];
51//!
52//! let mut termination = Indefinite;
53//! let mut brancher = solver.default_brancher();
54//! let result = solver.satisfy(&mut brancher, &mut termination);
55//! if let SatisfactionResult::Satisfiable(satisfiable) = result {
56//!     // Getting the value of the literal in the solution should not panic
57//!     literals.into_iter().for_each(|literal| {
58//!         satisfiable.solution().get_literal_value(literal);
59//!     })
60//! } else {
61//!     panic!("Solving should have returned satsifiable")
62//! }
63//! ```
64//!
65//! \[1\] F. Rossi, P. Van Beek, and T. Walsh, Handbook of constraint programming. Elsevier, 2006.
66
67mod brancher;
68pub mod branchers;
69mod selection_context;
70pub mod tie_breaking;
71pub mod value_selection;
72pub mod variable_selection;
73
74pub use brancher::*;
75pub use selection_context::SelectionContext;
76
77#[cfg(doc)]
78use crate::branching::branchers::independent_variable_value_brancher::IndependentVariableValueBrancher;
79#[cfg(doc)]
80use crate::branching::value_selection::ValueSelector;
81#[cfg(doc)]
82use crate::branching::variable_selection::AntiFirstFail;
83#[cfg(doc)]
84use crate::branching::variable_selection::VariableSelector;
85#[cfg(doc)]
86use crate::Solver;
pumpkin_core/branching/mod.rs

pumpkin_core/branching/
mod.rs
