Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
Aleph::Branch_And_Bound< Domain, ObjectivePolicy > Class Template Reference

Reusable branch-and-bound engine over implicit state spaces. More...

#include <Branch_And_Bound.H>

Collaboration diagram for Aleph::Branch_And_Bound< Domain, ObjectivePolicy >:
[legend]

Classes

struct  FrontierCompare
 
struct  FrontierNode
 

Public Types

using Domain_Type = Domain
 Type of the problem domain.
 
using State = typename Domain::State
 Concrete search state type.
 
using Move = typename Domain::Move
 Move type.
 
using Objective = typename Domain::Objective
 Type of the metric being optimized.
 
using Solution = OptimizationSolution< State, Move, Objective >
 Concrete solution type with objective value.
 
using Incumbent = ObjectiveIncumbent< Solution, ObjectivePolicy >
 Tracker for the best solution seen so far.
 
using Result = BranchAndBoundResult< Solution, ObjectivePolicy >
 Aggregated result type for optimization runs.
 

Public Member Functions

 Branch_And_Bound (Domain domain, ExplorationPolicy policy=default_policy(), const SearchLimits &limits={}, ObjectivePolicy objective={})
 Build a branch-and-bound engine bound to one optimization domain.
 
const Domain & domain () const noexcept
 
Domain & domain () noexcept
 
const ExplorationPolicy & policy () const noexcept
 
const SearchLimits & limits () const noexcept
 
const ObjectivePolicy & objective_policy () const noexcept
 
void set_policy (const ExplorationPolicy &policy) noexcept
 
void set_limits (const SearchLimits &limits) noexcept
 
Result search (State initial_state)
 Execute branch and bound and keep only the incumbent.
 
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
Result search (State initial_state, OnSolution &on_solution)
 Execute branch and bound with a callback/collector per solution.
 
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
Result search (State initial_state, OnSolution &&on_solution)
 
template<typename VisitedMap >
requires SearchStateKeyProvider<Domain>
Result search (State initial_state, VisitedMap &visited_map)
 Branch and bound with a visited-bound map (DFS only).
 
template<typename VisitedMap , typename OnSolution >
requires SearchStateKeyProvider<Domain>
and SearchSolutionVisitor< OnSolution, Solution > Result search (State initial_state, VisitedMap &visited_map, OnSolution &on_solution)
 Branch and bound with visited-bound map and solution callback.
 

Static Public Member Functions

static ExplorationPolicy default_policy () noexcept
 Return the default branch-and-bound exploration policy.
 

Static Public Attributes

static constexpr bool supports_best_first = true
 Compile-time marker: Branch_And_Bound supports both Depth_First and Best_First strategies.
 

Private Types

using Frontier = DynBinHeap< FrontierNode, FrontierCompare >
 

Private Member Functions

template<typename Recurse >
bool apply_move_and_recurse (const Move &move, State &state, SearchPath< Move > &path, Result &result, bool &stop, Recurse &&recurse)
 Apply one move, recurse, then undo — shared by dfs and dfs_visited.
 
bool ordering_active_for_depth_first () const noexcept
 
void validate_ordering_configuration () const
 
bool stop_after_solution (Result &result) const
 
bool expansion_limit_reached (Result &result) const
 
Array< RankedMove< Move, Objective > > collect_ordered_moves (State &state, Result &result)
 
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
bool handle_complete_solution (const State &state, const SearchPath< Move > &path, const size_t depth, Result &result, OnSolution &on_solution)
 
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
bool dfs (State &state, SearchPath< Move > &path, const size_t depth, Result &result, OnSolution &on_solution)
 
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
void search_depth_first (State &initial_state, Result &result, OnSolution &on_solution)
 
template<typename OnSolution , typename VisitedMap >
requires SearchSolutionVisitor<OnSolution, Solution>
and SearchStateKeyProvider< Domain > bool dfs_visited (State &state, SearchPath< Move > &path, const size_t depth, Result &result, OnSolution &on_solution, VisitedMap &visited)
 
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
bool process_best_first_candidate (State state, SearchPath< Move > path, const size_t depth, Result &result, Frontier &frontier, OnSolution &on_solution)
 
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
void search_best_first (State initial_state, Result &result, OnSolution &on_solution)
 

Static Private Member Functions

static void register_visit (const size_t depth, Result &result)
 

Private Attributes

Domain domain_
 
ExplorationPolicy policy_
 
SearchLimits limits_
 
ObjectivePolicy objective_
 

Detailed Description

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
requires BranchAndBoundObjectivePolicy<ObjectivePolicy, typename Domain::Objective>
class Aleph::Branch_And_Bound< Domain, ObjectivePolicy >

Reusable branch-and-bound engine over implicit state spaces.

Template Parameters
DomainProblem adapter exposing bound(state), is_complete(state) and objective_value(state).
ObjectivePolicyPolicy used to compare solutions (Maximize_Objective or Minimize_Objective).

Definition at line 298 of file Branch_And_Bound.H.

Member Typedef Documentation

◆ Domain_Type

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
using Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::Domain_Type = Domain

Type of the problem domain.

Definition at line 302 of file Branch_And_Bound.H.

◆ Frontier

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
using Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::Frontier = DynBinHeap<FrontierNode, FrontierCompare>
private

Definition at line 352 of file Branch_And_Bound.H.

◆ Incumbent

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
using Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::Incumbent = ObjectiveIncumbent<Solution, ObjectivePolicy>

Tracker for the best solution seen so far.

Definition at line 312 of file Branch_And_Bound.H.

◆ Move

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
using Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::Move = typename Domain::Move

Move type.

Definition at line 306 of file Branch_And_Bound.H.

◆ Objective

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
using Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::Objective = typename Domain::Objective

Type of the metric being optimized.

Definition at line 308 of file Branch_And_Bound.H.

◆ Result

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
using Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::Result = BranchAndBoundResult<Solution, ObjectivePolicy>

Aggregated result type for optimization runs.

Definition at line 314 of file Branch_And_Bound.H.

◆ Solution

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
using Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::Solution = OptimizationSolution<State, Move, Objective>

Concrete solution type with objective value.

Definition at line 310 of file Branch_And_Bound.H.

◆ State

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
using Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::State = typename Domain::State

Concrete search state type.

Definition at line 304 of file Branch_And_Bound.H.

Constructor & Destructor Documentation

◆ Branch_And_Bound()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::Branch_And_Bound ( Domain  domain,
ExplorationPolicy  policy = default_policy(),
const SearchLimits &  limits = {},
ObjectivePolicy  objective = {} 
)
inlineexplicit

Build a branch-and-bound engine bound to one optimization domain.

Definition at line 365 of file Branch_And_Bound.H.

Member Function Documentation

◆ apply_move_and_recurse()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename Recurse >
bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::apply_move_and_recurse ( const Move &  move,
State &  state,
SearchPath< Move > &  path,
Result &  result,
bool &  stop,
Recurse &&  recurse 
)
inlineprivate

Apply one move, recurse, then undo — shared by dfs and dfs_visited.

Captures the common try/catch pattern that protects undo and the path rollback against exceptions thrown during apply, recursion or tracing.

Template Parameters
RecurseCallable () -> bool that performs the recursive descent after the move has been applied and appended to path.
Parameters
moveMove to apply and undo.
stateMutable search state (modified in-place).
pathCurrent move path (extended and restored in-place).
resultResult object whose statistics are updated in-place.
stopOut-parameter set by the recursive call; true signals an early stop propagated upward.
recurseCallable invoked after apply; its return value is stored in stop.
Returns
true to continue sibling enumeration; false to stop.

Definition at line 544 of file Branch_And_Bound.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_, Aleph::SearchStats::generated_successors, Aleph::Array< T >::remove_last(), and Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited().

◆ collect_ordered_moves()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
Array< RankedMove< Move, Objective > > Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::collect_ordered_moves ( State &  state,
Result &  result 
)
inlineprivate

Definition at line 605 of file Branch_And_Bound.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_, Aleph::Array< T >::is_empty(), Aleph::RankedMove< Move, Priority >::move, Aleph::SearchStats::move_ordering, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_, Aleph::MoveOrderingStats::ordered_batches, Aleph::MoveOrderingStats::ordered_moves, Aleph::MoveOrderingStats::priority_estimates, Aleph::Array< T >::size(), Aleph::sort_ranked_moves(), and Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited().

◆ default_policy()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
static ExplorationPolicy Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::default_policy ( )
inlinestaticnoexcept

Return the default branch-and-bound exploration policy.

Definition at line 356 of file Branch_And_Bound.H.

References Aleph::ExplorationPolicy::Depth_First, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy(), Aleph::ExplorationPolicy::stop_at_first_solution, and Aleph::ExplorationPolicy::strategy.

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ dfs()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs ( State &  state,
SearchPath< Move > &  path,
const size_t  depth,
Result &  result,
OnSolution &  on_solution 
)
inlineprivate

Definition at line 691 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::apply_move_and_recurse(), Aleph::ObjectiveIncumbent< Solution, ObjectivePolicy >::can_improve(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::collect_ordered_moves(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), Aleph::divide_and_conquer_partition_dp(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_, Aleph::SearchStats::expanded_states, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::expansion_limit_reached(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::handle_complete_solution(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::incumbent, Aleph::search_engine_detail::is_terminal_state(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_, Aleph::SearchLimits::max_depth, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::ordering_active_for_depth_first(), Aleph::BranchAndBoundStats::pruned_by_bound, Aleph::SearchStats::pruned_by_depth, Aleph::SearchStats::pruned_by_domain, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::register_visit(), Aleph::search_engine_detail::should_prune_state(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats, and Aleph::SearchStats::terminal_states.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_depth_first().

◆ dfs_visited()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename OnSolution , typename VisitedMap >
requires SearchSolutionVisitor<OnSolution, Solution>
and SearchStateKeyProvider< Domain > bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited ( State &  state,
SearchPath< Move > &  path,
const size_t  depth,
Result &  result,
OnSolution &  on_solution,
VisitedMap &  visited 
)
inlineprivate

Definition at line 769 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::apply_move_and_recurse(), Aleph::ObjectiveIncumbent< Solution, ObjectivePolicy >::can_improve(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::collect_ordered_moves(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), Aleph::divide_and_conquer_partition_dp(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_, Aleph::SearchStats::expanded_states, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::expansion_limit_reached(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::handle_complete_solution(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::incumbent, Aleph::search_engine_detail::is_terminal_state(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_, Aleph::SearchLimits::max_depth, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::ordering_active_for_depth_first(), Aleph::BranchAndBoundStats::pruned_by_bound, Aleph::SearchStats::pruned_by_depth, Aleph::SearchStats::pruned_by_domain, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::register_visit(), Aleph::search_engine_detail::should_prune_state(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats, and Aleph::SearchStats::terminal_states.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search().

◆ domain() [1/2]

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
const Domain & Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain ( ) const
inlinenoexcept

Definition at line 374 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_.

◆ domain() [2/2]

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
Domain & Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain ( )
inlinenoexcept

Definition at line 379 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_.

◆ expansion_limit_reached()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::expansion_limit_reached ( Result &  result) const
inlineprivate

Definition at line 595 of file Branch_And_Bound.H.

References Aleph::search_engine_detail::expansion_limit_reached(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_best_first().

◆ handle_complete_solution()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::handle_complete_solution ( const State &  state,
const SearchPath< Move > &  path,
const size_t  depth,
Result &  result,
OnSolution &  on_solution 
)
inlineprivate

Definition at line 664 of file Branch_And_Bound.H.

References Aleph::ObjectiveIncumbent< Solution, ObjectivePolicy >::consider(), Aleph::SearchSolution< State, Move >::depth, Aleph::divide_and_conquer_partition_dp(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::incumbent, Aleph::BranchAndBoundStats::incumbent_updates, Aleph::OptimizationSolution< State, Move, Objective >::objective_value, Aleph::SearchSolution< State, Move >::path, Aleph::SearchStats::solutions_found, Aleph::SearchSolution< State, Move >::state, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::status, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::stop_after_solution(), and Aleph::StoppedOnSolution.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::process_best_first_candidate().

◆ limits()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
const SearchLimits & Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits ( ) const
inlinenoexcept

Definition at line 389 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::set_limits().

◆ objective_policy()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
const ObjectivePolicy & Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_policy ( ) const
inlinenoexcept

Definition at line 394 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_.

◆ ordering_active_for_depth_first()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::ordering_active_for_depth_first ( ) const
inlineprivatenoexcept

Definition at line 575 of file Branch_And_Bound.H.

References Aleph::Estimated_Bound, Aleph::ExplorationPolicy::move_ordering, and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy_.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited().

◆ policy()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
const ExplorationPolicy & Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy ( ) const
inlinenoexcept

Definition at line 384 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy_.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::default_policy(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::set_policy().

◆ process_best_first_candidate()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::process_best_first_candidate ( State  state,
SearchPath< Move >  path,
const size_t  depth,
Result &  result,
Frontier &  frontier,
OnSolution &  on_solution 
)
inlineprivate

Definition at line 876 of file Branch_And_Bound.H.

References Aleph::ObjectiveIncumbent< Solution, ObjectivePolicy >::can_improve(), Aleph::divide_and_conquer_partition_dp(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::handle_complete_solution(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::incumbent, Aleph::search_engine_detail::is_terminal_state(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_, Aleph::SearchLimits::max_depth, Aleph::BranchAndBoundStats::pruned_by_bound, Aleph::SearchStats::pruned_by_depth, Aleph::SearchStats::pruned_by_domain, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::register_visit(), Aleph::search_engine_detail::should_prune_state(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats, and Aleph::SearchStats::terminal_states.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_best_first().

◆ register_visit()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
static void Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::register_visit ( const size_t  depth,
Result &  result 
)
inlinestaticprivate

Definition at line 600 of file Branch_And_Bound.H.

References Aleph::search_engine_detail::register_visit().

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::process_best_first_candidate().

◆ search() [1/5]

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
Result Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search ( State  initial_state)
inline

Execute branch and bound and keep only the incumbent.

Definition at line 410 of file Branch_And_Bound.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search().

Referenced by main(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), TEST(), and TEST().

◆ search() [2/5]

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
Result Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search ( State  initial_state,
OnSolution &&  on_solution 
)
inline

Definition at line 455 of file Branch_And_Bound.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search().

◆ search() [3/5]

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
Result Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search ( State  initial_state,
OnSolution &  on_solution 
)
inline

Execute branch and bound with a callback/collector per solution.

Definition at line 419 of file Branch_And_Bound.H.

References ah_invalid_argument_if, Aleph::ExplorationPolicy::Best_First, Aleph::ExplorationPolicy::Depth_First, Aleph::divide_and_conquer_partition_dp(), Aleph::SearchStats::elapsed_ms, Aleph::Exhausted, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::limits, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_, Aleph::SearchLimits::max_solutions, Aleph::NotStarted, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::policy, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy_, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_best_first(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_depth_first(), Aleph::search_elapsed_ms(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::status, Aleph::ExplorationPolicy::strategy, and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::validate_ordering_configuration().

◆ search() [4/5]

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename VisitedMap >
requires SearchStateKeyProvider<Domain>
Result Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search ( State  initial_state,
VisitedMap &  visited_map 
)
inline

Branch and bound with a visited-bound map (DFS only).

Before expanding a node, checks whether the same state was already visited with an equal-or-better optimistic bound. If so, the current branch is pruned; otherwise the stored bound is updated. This eliminates redundant sub-tree explorations when the same state is reachable via multiple paths.

The domain must expose state_key(state) (see Aleph::SearchStateKeyProvider).

Parameters
[in]initial_stateMutable root state.
[in,out]visited_mapCaller-owned map from state key to best bound.
Returns
Search result with statistics and best retained solution.

Definition at line 477 of file Branch_And_Bound.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search().

◆ search() [5/5]

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename VisitedMap , typename OnSolution >
requires SearchStateKeyProvider<Domain>
and SearchSolutionVisitor< OnSolution, Solution > Result Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search ( State  initial_state,
VisitedMap &  visited_map,
OnSolution &  on_solution 
)
inline

Branch and bound with visited-bound map and solution callback.

Definition at line 491 of file Branch_And_Bound.H.

References ah_invalid_argument_if, Aleph::ExplorationPolicy::Depth_First, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), Aleph::divide_and_conquer_partition_dp(), Aleph::SearchStats::elapsed_ms, Aleph::Exhausted, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::limits, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_, Aleph::SearchLimits::max_solutions, Aleph::NotStarted, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::policy, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy_, Aleph::reserve_search_path(), Aleph::search_elapsed_ms(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats, Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::status, Aleph::ExplorationPolicy::strategy, and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::validate_ordering_configuration().

◆ search_best_first()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
void Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_best_first ( State  initial_state,
Result &  result,
OnSolution &  on_solution 
)
inlineprivate

Definition at line 919 of file Branch_And_Bound.H.

References Aleph::and, Aleph::ObjectiveIncumbent< Solution, ObjectivePolicy >::can_improve(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::FrontierNode::depth, Aleph::divide_and_conquer_partition_dp(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_, Aleph::SearchStats::expanded_states, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::expansion_limit_reached(), Aleph::SearchStats::generated_successors, Aleph::ObjectiveIncumbent< Solution, ObjectivePolicy >::has_value(), Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::incumbent, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::FrontierNode::path, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::process_best_first_candidate(), Aleph::BranchAndBoundStats::pruned_by_bound, Aleph::reserve_search_path(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::FrontierNode::state, and Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >::stats.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search().

◆ search_depth_first()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>
void Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_depth_first ( State &  initial_state,
Result &  result,
OnSolution &  on_solution 
)
inlineprivate

Definition at line 759 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), Aleph::divide_and_conquer_partition_dp(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_, and Aleph::reserve_search_path().

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search().

◆ set_limits()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
void Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::set_limits ( const SearchLimits &  limits)
inlinenoexcept

Definition at line 404 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_.

◆ set_policy()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
void Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::set_policy ( const ExplorationPolicy &  policy)
inlinenoexcept

Definition at line 399 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy_.

◆ stop_after_solution()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::stop_after_solution ( Result &  result) const
inlineprivate

Definition at line 590 of file Branch_And_Bound.H.

References Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy_, and Aleph::search_engine_detail::stop_after_solution().

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::handle_complete_solution().

◆ validate_ordering_configuration()

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
void Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::validate_ordering_configuration ( ) const
inlineprivate

Definition at line 580 of file Branch_And_Bound.H.

References ah_invalid_argument_if, Aleph::Estimated_Score, Aleph::ExplorationPolicy::move_ordering, Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy_, Aleph::ExplorationPolicy::use_history_heuristic, and Aleph::ExplorationPolicy::use_killer_moves.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search().

Member Data Documentation

◆ domain_

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
Domain Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain_
private

Definition at line 521 of file Branch_And_Bound.H.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::apply_move_and_recurse(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::collect_ordered_moves(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::domain(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::handle_complete_solution(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::process_best_first_candidate(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_best_first().

◆ limits_

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
SearchLimits Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits_
private

Definition at line 523 of file Branch_And_Bound.H.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::expansion_limit_reached(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::limits(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::process_best_first_candidate(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_best_first(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_depth_first(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::set_limits(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::stop_after_solution().

◆ objective_

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
ObjectivePolicy Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_
private

Definition at line 524 of file Branch_And_Bound.H.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::collect_ordered_moves(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::dfs_visited(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::objective_policy(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search_best_first().

◆ policy_

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
ExplorationPolicy Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy_
private

Definition at line 522 of file Branch_And_Bound.H.

Referenced by Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::ordering_active_for_depth_first(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::policy(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::search(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::set_policy(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::stop_after_solution(), and Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::validate_ordering_configuration().

◆ supports_best_first

template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>>
constexpr bool Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::supports_best_first = true
staticconstexpr

Compile-time marker: Branch_And_Bound supports both Depth_First and Best_First strategies.

Unlike Aleph::Negamax and Aleph::Alpha_Beta (which only support Depth_First), this engine also accepts ExplorationPolicy::Strategy::Best_First. Check this constant alongside those engines' supports_best_first = false to detect strategy mismatches at compile time.

Definition at line 325 of file Branch_And_Bound.H.

The documentation for this class was generated from the following file: