Branch_And_Bound.H File Reference

Reusable branch-and-bound engine for implicit optimization spaces. More...

#include <concepts>
#include <utility>
#include <ah-errors.H>
#include <state_search_common.H>
#include <Transposition_Table.H>
#include <tpl_dynBinHeap.H>

Include dependency graph for Branch_And_Bound.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Maximize_Objective< Value >
	Objective policy for maximization problems. More...
struct	Aleph::Minimize_Objective< Value >
	Objective policy for minimization problems. More...
struct	Aleph::OptimizationSolution< State, Move, Objective >
	Snapshot of a complete optimization solution. More...
struct	Aleph::PreferBetterObjective< Solution, ObjectivePolicy >
	Compare two optimization solutions by objective quality. More...
class	Aleph::ObjectiveIncumbent< Solution, ObjectivePolicy >
	Global incumbent manager for branch and bound. More...
struct	Aleph::BranchAndBoundStats
	Branch-and-bound specific statistics. More...
struct	Aleph::BranchAndBoundResult< Solution, ObjectivePolicy >
	Result of a branch-and-bound execution. More...
class	Aleph::Branch_And_Bound< Domain, ObjectivePolicy >
	Reusable branch-and-bound engine over implicit state spaces. More...
struct	Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::FrontierNode
struct	Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::FrontierCompare

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Concepts
concept	Aleph::BranchAndBoundObjectivePolicy
	Concept for objective policies used by branch and bound.
concept	Aleph::CompleteSolutionPredicate
	Concept for complete-solution predicates in optimization domains.
concept	Aleph::OptimizationEvaluator
	Concept for domains that provide an objective and an optimistic bound.
concept	Aleph::BranchAndBoundDomain
	Minimal contract for branch-and-bound domains.

Enumerations
enum class	Aleph::OptimizationSense { Aleph::Minimize , Aleph::Maximize }
	Optimization direction supported by branch and bound. More...

Functions
template<BranchAndBoundDomain Domain, typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>> requires BranchAndBoundObjectivePolicy<ObjectivePolicy, typename Domain::Objective>
auto	Aleph::branch_and_bound_search (Domain domain, typename Domain::State initial_state, ExplorationPolicy policy=Branch_And_Bound< Domain, ObjectivePolicy >::default_policy(), SearchLimits limits={}, ObjectivePolicy objective={})
	Convenience wrapper for one-shot branch and bound.
template<BranchAndBoundDomain Domain, typename OnSolution , typename ObjectivePolicy = Maximize_Objective<typename Domain::Objective>> requires BranchAndBoundObjectivePolicy<ObjectivePolicy, typename Domain::Objective>
and SearchSolutionVisitor< OnSolution, OptimizationSolution< typename Domain::State, typename Domain::Move, typename Domain::Objective > > auto	Aleph::branch_and_bound_search (Domain domain, typename Domain::State initial_state, OnSolution &on_solution, ExplorationPolicy policy=Branch_And_Bound< Domain, ObjectivePolicy >::default_policy(), SearchLimits limits={}, ObjectivePolicy objective={})
	Convenience wrapper for branch and bound with a solution callback.

Detailed Description

Reusable branch-and-bound engine for implicit optimization spaces.

This module builds on the common state-space search vocabulary and adds the minimal machinery specific to optimization:

• optimization sense (minimize/maximize),
• optimistic bounds,
• global incumbent management,
• pruning when a node cannot improve the incumbent,
• depth-first and best-first exploration strategies,
• optional bound-guided child ordering for depth-first exploration.

Author

Leandro Rabindranath León

Definition in file Branch_And_Bound.H.