Implements Branch and Bound template method as basis for more advanced B&B implementations. More...

#include <search_branch_and_bound.hpp>

Inheritance diagram for FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >:

Classes
struct	Node
	Structure representing search tree node. More...

Public Types
typedef Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
	base class: the abstract Search interface (search(), progress reporting, result tracker)
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion under optimization
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
typedef Candidate_Evaluator< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	EVALUATORENGINE
	the injected candidate-evaluation strategy type (sequential-inline or thread-pooled); process_leafs(), and descendants' pre_evaluate_availables()/post_process_tree_level() overrides, batch candidate evaluations through it
typedef std::shared_ptr< EVALUATORENGINE >	PEvaluatorEngine
	shared pointer to an EVALUATORENGINE, as accepted by the constructor and returned by get_engine()
Public Types inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion the search optimizes
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
typedef std::shared_ptr< Result_Tracker< RETURNTYPE, SUBSET > >	PResultTracker
	shared pointer to the result tracker enabled via enable_result_tracking()
typedef Search_Observer< RETURNTYPE, SUBSET >	OBSERVER
	the observer interface type this search reports through (see Search_Observer)
typedef std::shared_ptr< OBSERVER >	PObserver
	shared pointer to an OBSERVER, as set via set_observer()

Public Member Functions
	Search_Branch_And_Bound (PEvaluatorEngine engine=PEvaluatorEngine())
	Constructs the search, optionally injecting a candidate-evaluation engine.
virtual bool	search (const DIMTYPE target_d, RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os=std::cout) override
	returns the found subset of exactly target_d features + its criterion value; target_d must be nonzero (Branch & Bound searches one fixed cardinality, it does not optimize it)
virtual std::ostream &	print (std::ostream &os) const override
	writes a human-readable identification of the search and its configuration; base default writes nothing
Public Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	enable_result_tracking (PResultTracker tracker)
	assigns a result tracker to the search process, i.e., enables logging of all evaluated subsets for future reuse (re-evaluation, etc.)
void	disable_result_tracking ()
	detaches any result tracker (result_tracker_active() then returns false)
bool	result_tracker_active () const
	true if a result tracker was assigned via enable_result_tracking() and not since disabled
void	set_output_detail (OutputDetail detail)
	sets the amount of information that is logged to output stream throughout the course of search
OutputDetail	get_output_detail () const
	the currently configured output detail level
bool	output_normal () const
	true unless output detail is SILENT
bool	output_detailed () const
	true only at the DETAILED output level
void	set_observer (PObserver observer)
	redirects search progress reporting away from the default syncout text output to `observer`

Protected Types
enum	NodeType { UNKNOWN , RANDOM , PREDICTED , COMPUTED }
	Marks how a Node's value was obtained: UNKNOWN = not yet assigned; RANDOM = reserved but currently unused by any B&B variant in this file; PREDICTED = filled from a PREDICTOR estimate pending confirmation (FBB/BBPP node ordering); COMPUTED = an exact criterion value.
typedef Node *	PNode
	pointer to a Node, as used by the getFirst.../getNext... accessors below
typedef std::list< Node >	ListNode
	one tree level's not-yet-decided candidate nodes, kept sorted ascending by value; the main search loop visits/pops from the back (highest value = most promising) via get_current_node()
typedef std::vector< ListNode >	VectorListNode
	the search tree: one ListNode per level, indexed by tree depth k (see _tree)
typedef ListNode::iterator	ListNodeIter
	iterator into a single tree level's ListNode, as used by _nodeiter/getFirstNode()/getNextNode()
typedef std::vector< ListNode >::iterator	TreeLevelIter
	iterator over tree levels (used only to clear _tree in setup_default_structures())
typedef std::vector< Node >	VectorNode
	type of _available: one Node per original feature, indexed by feature id

Protected Member Functions
PCriterion const &	get_criterion () const
	accessor for _criterion, for use by descendant B&B variants' hooks
PEvaluatorEngine const &	get_engine () const
	accessor for the injected evaluation strategy (sequential-inline or thread-pooled), for use by descendant B&B variants' hooks
RETURNTYPE	get_bound_value () const
	the current best (bound) criterion value; meaningful only once is_bound_valid()
bool	is_bound_valid () const
	true once a valid bound has been established, see _boundvalid
int	get_k () const
	the tree depth/level currently being processed (root is 0; the deepest stored level is n-d-1, and level n-d is the leaf level, evaluated but never stored). The return type is int, while the member k is DIMTYPE
DIMTYPE	get_n () const
	total number of features, see n
DIMTYPE	get_d () const
	target subset cardinality, see d
bool	getFirstNode (PNode &nod)
	begins forward iteration (ascending by value, from _tree[k].begin()) over the current level's not-yet-decided nodes into nod; returns false if the level is empty
bool	getNextNode (PNode &nod)
	advances the getFirstNode() iteration; returns false once the level's end is reached
bool	getFirstAvailable (PNode &avail)
	begins iteration over _available in feature-index order, skipping withdrawn (invalid) entries, into avail; returns false if none are available
bool	getNextAvailable (PNode &avail)
	advances the getFirstAvailable() iteration, again skipping invalid entries; returns false once exhausted
bool	getAvailable (DIMTYPE idx, PNode &avail)
	direct lookup of _available[idx] by feature index, regardless of its valid flag; returns false if idx is out of range
PSubset &	get_currentset ()
	mutable accessor for _currentset, for use by descendant B&B variants' hooks
Node &	get_parent_node ()
	the node one level up (_tree[k-1].back()) whose feature removal defines the branch currently being followed; valid at the leaf level too (k==n-d==_tree.size(), the unstored leaf level whose parent is the last stored one), which is where FBB/BBPP's leaf hooks call it
Node &	get_current_node ()
	the node at the current level k presently being visited (_tree[k].back()), i.e. about to be tested for cutting or descended into
void	setup_default_structures (const DIMTYPE d, const DIMTYPE n)
	Allocates and resets everything one search() run needs: the n-d stored tree levels (all emptied), the _available pool (all n features valid), _currentset (all features selected, i.e. the root), the _tempset scratch subset and the _boundset holder (bound marked invalid).
void	update_bound (const RETURNTYPE val, const PSubset &sub)
	Registers one fully-evaluated candidate subset of target cardinality d against the running bound. Updates _boundset/_boundvalue/_boundvalid whenever val improves on (or is the first) bound and, at NORMAL output or above, reports the improvement as a new solution; unconditionally feeds (val,sub) to the result tracker if one is active. Called from process_rightmost_path() and from process_leafs()'s per-leaf engine callback.
void	make_tree_level ()
	Builds the k-th tree level (_tree[k]), keeping exactly n-d-k+1 candidates in reserve for the levels still to come. Calls pre_evaluate_availables() to obtain each still-available feature's ordering value, sorts the best (levelsize = get_available_size()-(n-d-k+1)) of them ascending by value into _tree[k] (withdrawing the chosen features from _available via available_remove()), then calls post_process_tree_level() so a descendant can substitute exact values for any node whose ordering value was only an estimate.
void	process_rightmost_path ()
	Evaluates and registers the "rightmost" leaf reachable from the current branch by removing every feature still in _available at once. Copies _currentset into _tempset, deselects every remaining available feature, evaluates the criterion on the result and passes it to update_bound() - this seeds/tightens the bound as soon as each new tree level is built, before further descent, so later cuts can trigger sooner.
virtual void	process_leafs ()
	engine-routed leaf evaluation; descendants hook per-leaf work via leaf_result() instead of overriding this
virtual void	leaf_result (const DIMTYPE feature, const RETURNTYPE value)
virtual void	initialize (const DIMTYPE d, const DIMTYPE n, const PCriterion crit)=0
	Called once per search() run, after setup_default_structures() and the root evaluation but before the traversal starts, so descendants can size and reset their own structures. The arguments repeat the run's parameters; the criterion is the one search() was called with and is already initialize()d.
virtual void	pre_evaluate_availables ()=0
	Called by make_tree_level() before the k-th level is built. It must assign Node::value (and Node::type) to EVERY currently valid entry of _available, since those values are what the level is sorted by; features left at type UNKNOWN sort to the end of the level. When it is called, _currentset is the subset of the branch above level k and _tree[k] is still empty.
virtual void	post_process_tree_level ()=0
	Called by make_tree_level() once the k-th level has been filled and its features withdrawn from _available. It is the place to replace values that are only estimates (type PREDICTED) by exact ones (type COMPUTED) where the variant requires it; it may leave the level untouched.
virtual bool	cut_possible ()=0
	Tests the current node (get_current_node(), i.e. _tree[k].back()) for the possibility to cut the whole sub-branch below it. It is called only with a non-empty _tree[k], and it MUST return false while is_bound_valid() is false - there is nothing to compare against yet. A variant whose node value is not COMPUTED yet is expected to compute it here (on the calling thread: this is a single evaluation on the traversal's critical path).
Protected Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	report (std::ostream &os, const msgbuf &m) const
	delivers one pre-formatted progress message: to the observer if attached, otherwise as syncout text to os
void	report_solution (std::ostream &os, const RETURNTYPE value, const SUBSET &sub, const msgbuf &m) const
	like report(), for sites announcing a new (sub-)solution; fires on_solution instead

Protected Attributes
std::ostream *	shared_os
	to enable sharing the same stream across the methods below
std::shared_ptr< StopWatch >	swatch
	stopwatch for the running search, (re)created at the start of search() and reported alongside progress/solution messages
Protected Attributes inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
PResultTracker	_tracker
	the assigned result tracker, or null (see enable_result_tracking()/result_tracker_active())
OutputDetail	_detail
	the output detail level set via set_output_detail(); read by output_normal()/output_detailed()
PObserver	_observer
	the attached progress observer, or null (see set_observer(), report(), report_solution())

Private Member Functions
DIMTYPE	get_available_size ()
	number of features still undecided (valid==true) in _available
void	available_add (const DIMTYPE feature)
	re-admits feature to the undecided candidate pool (valid=true, type reset to UNKNOWN); used on backtrack and when a cut releases it
void	available_remove (const DIMTYPE feature)
	withdraws feature from the undecided candidate pool (valid=false), e.g. once it has been sorted into a tree level
void	currentset_add (const DIMTYPE feature)
	re-selects feature in _currentset, undoing a prior currentset_remove() (used when backtracking up the tree)
void	currentset_remove (const DIMTYPE feature)
	deselects feature from _currentset, committing its removal as the branch descends past it

Private Attributes
PCriterion	_criterion
	the criterion supplied to search(), assigned once initialize() has run (see search())
PEvaluatorEngine	_engine
	injected evaluation strategy (sequential-inline or thread-pooled)
VectorListNode	_tree
	the search tree; _tree[k] holds the not-yet-decided candidate nodes at depth k (see make_tree_level())
ListNodeIter	_nodeiter
	used in get*Node()
DIMTYPE	_availiter
	iteration cursor used by getFirstAvailable()/getNextAvailable() over _available
VectorNode	_available
	the pool of still-undecided features, one entry per original feature and indexed by feature id: Node::feature repeats that id, and Node::valid is the in-pool indicator (true = still undecided, see available_add()/available_remove())
PSubset	_currentset
	the subset defined by the branch currently being followed: all n features minus the ones removed on the path from the root down to level k
PSubset	_tempset
	temporary copy of _currentset subset to be modified and evaluated
PSubset	_boundset
	the best subset of target cardinality d found so far; meaningful only once _boundvalid is true
RETURNTYPE	_boundvalue
	the criterion value of _boundset; meaningful only once _boundvalid is true
bool	_boundvalid
	true once at least one candidate of target cardinality d has been evaluated, so _boundset/_boundvalue hold a valid bound
DIMTYPE	k
	current tree level
DIMTYPE	n
	no. of all features
DIMTYPE	d
	no. of features to be selected

Detailed Description

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>
class FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >

Implements Branch and Bound template method as basis for more advanced B&B implementations.

This is the abstract basis of concrete Branch & Bound implementations.

Warning: All Branch & Bound feature selection algorithms require the used CRITERION to be monotonic with respect to cardinality. More precisely, it must hold that removing a feature from a set MUST NOT increase criterion value. Otherwise there is no guarantee as of the optimality of obtained results with respect to the used criterion.

Note: Due to possibly high number of subsets to be tested expect excessive computational time.; Result tracking in case of Branch & Bound algorithms records only results of target cardinality.

Constructor & Destructor Documentation

◆ Search_Branch_And_Bound()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::Search_Branch_And_Bound ( PEvaluatorEngine engine = PEvaluatorEngine() )

inlineexplicit

Constructs the search, optionally injecting a candidate-evaluation engine.

Parameters

engine the evaluation strategy candidate batches are routed through (e.g. Candidate_Evaluator_Sequential or a thread-pooled implementation); a default-constructed (null) shared_ptr installs a Candidate_Evaluator_Sequential, so plain sequential B&B needs no explicit engine argument.

Member Function Documentation

◆ cut_possible()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

virtual bool FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::cut_possible ( )

protectedpure virtual

Tests the current node (get_current_node(), i.e. _tree[k].back()) for the possibility to cut the whole sub-branch below it. It is called only with a non-empty _tree[k], and it MUST return false while is_bound_valid() is false - there is nothing to compare against yet. A variant whose node value is not COMPUTED yet is expected to compute it here (on the calling thread: this is a single evaluation on the traversal's critical path).

Implemented in FST::Search_Branch_And_Bound_Basic< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >, FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, and FST::Search_Branch_And_Bound_Partial_Prediction< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >.

◆ initialize()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

virtual void FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::initialize	(	const DIMTYPE	d,
		const DIMTYPE	n,
		const PCriterion	crit )

protectedpure virtual

Called once per search() run, after setup_default_structures() and the root evaluation but before the traversal starts, so descendants can size and reset their own structures. The arguments repeat the run's parameters; the criterion is the one search() was called with and is already initialize()d.

Implemented in FST::Search_Branch_And_Bound_Basic< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >, FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, and FST::Search_Branch_And_Bound_Partial_Prediction< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >.

◆ leaf_result()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

virtual void FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::leaf_result	(	const DIMTYPE	feature,
		const RETURNTYPE	value )

inlineprotectedvirtual

fired once per leaf in candidate (enumeration) order from process_leafs' engine callback, after the bound update - FBB/BBPP learn prediction contrasts here

Reimplemented in FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >, and FST::Search_Branch_And_Bound_Partial_Prediction< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >.

◆ post_process_tree_level()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

virtual void FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::post_process_tree_level ( )

protectedpure virtual

Called by make_tree_level() once the k-th level has been filled and its features withdrawn from _available. It is the place to replace values that are only estimates (type PREDICTED) by exact ones (type COMPUTED) where the variant requires it; it may leave the level untouched.

Implemented in FST::Search_Branch_And_Bound_Basic< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >, FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, and FST::Search_Branch_And_Bound_Partial_Prediction< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >.

◆ pre_evaluate_availables()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

virtual void FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::pre_evaluate_availables ( )

protectedpure virtual

Called by make_tree_level() before the k-th level is built. It must assign Node::value (and Node::type) to EVERY currently valid entry of _available, since those values are what the level is sorted by; features left at type UNKNOWN sort to the end of the level. When it is called, _currentset is the subset of the branch above level k and _tree[k] is still empty.

Implemented in FST::Search_Branch_And_Bound_Basic< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >, FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, and FST::Search_Branch_And_Bound_Partial_Prediction< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >.

◆ print()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

virtual std::ostream & FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::print ( std::ostream & os ) const

inlineoverridevirtual

writes a human-readable identification of the search and its configuration; base default writes nothing

Reimplemented from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >.

Reimplemented in FST::Search_Branch_And_Bound_Basic< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >, FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >, and FST::Search_Branch_And_Bound_Partial_Prediction< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >.

◆ search()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

bool FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::search	(	const DIMTYPE	target_d,
		RETURNTYPE &	result,
		const PSubset	sub,
		const PCriterion	crit,
		std::ostream &	os = std::cout )

overridevirtual

returns the found subset of exactly target_d features + its criterion value; target_d must be nonzero (Branch & Bound searches one fixed cardinality, it does not optimize it)

Implements FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >.

◆ setup_default_structures()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

void FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::setup_default_structures	(	const DIMTYPE	d,
		const DIMTYPE	n )

protected

Allocates and resets everything one search() run needs: the n-d stored tree levels (all emptied), the _available pool (all n features valid), _currentset (all features selected, i.e. the root), the _tempset scratch subset and the _boundset holder (bound marked invalid).

Parameters

d	target subset cardinality; must satisfy 0 < d < n
n	total number of features

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

/Users/psms/dev/devtest1/_src_search/search_branch_and_bound.hpp

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Search_Branch_And_Bound()

Member Function Documentation

◆ cut_possible()

◆ initialize()

◆ leaf_result()

◆ post_process_tree_level()

◆ pre_evaluate_availables()

◆ print()

◆ search()

◆ setup_default_structures()