Implements Improved Branch and Bound (IBB) method, i.e., with fully computed node ordering. More...

#include <search_branch_and_bound_improved.hpp>

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

Public Types
typedef Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
	base class alias
typedef parent::PCriterion	PCriterion
	shared pointer to the criterion the search optimizes
typedef parent::PSubset	PSubset
	shared pointer to a feature subset
typedef parent::PNode	PNode
	pointer to a search-tree Node, see Search_Branch_And_Bound
typedef parent::Node	Node
	search-tree node record (feature, value, type, valid), see Search_Branch_And_Bound
typedef parent::NodeType	NodeType
	UNKNOWN/RANDOM/PREDICTED/COMPUTED node-value provenance, see Search_Branch_And_Bound.
typedef parent::PEvaluatorEngine	PEvaluatorEngine
	shared pointer to the injected evaluation-strategy engine
Public Types inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
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_Improved (PEvaluatorEngine engine=PEvaluatorEngine())
	`engine` forwarded to Search_Branch_And_Bound; defaults to sequential in-line evaluation if not supplied
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_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
	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)
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 Member Functions
virtual void	initialize (const DIMTYPE d, const DIMTYPE n, const PCriterion crit) override
	IBB keeps no structures of its own beyond the base class's tree, so there is nothing to set up.
virtual void	pre_evaluate_availables () override
	evaluates the criterion for every available feature (one batch through the evaluation engine) so that the next tree level can be ordered by true criterion values - this is what IBB buys its cuts with
virtual void	post_process_tree_level () override
	nothing to do: every node of the new level already carries a COMPUTED value from pre_evaluate_availables()
virtual bool	cut_possible () override
	reports whether the current node's (always computed) value fails to exceed the bound, in which case the whole sub-branch below it can be cut
Protected Member Functions inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
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)
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

Additional Inherited Members
Protected Types inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
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 Attributes inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
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())

Detailed Description

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

Implements Improved Branch and Bound (IBB) method, i.e., with fully computed node ordering.

IBB is the well-known B&B variant that orders tree nodes in each constructed tree level so as to increase the chance that the bound gets higher soon. This effectively improves chances that larger sub-trees can be cut and thus more time saved, but this is achieved at the cost of additional criterion evaluations in each tree level. In time consuming tasks this mechanism proves capable of considerably overperforming the Basic Branch & Bound algorithm.

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: All Branch & Bound algorithms by definition yield the solution with the same maximum criterion value, therefore the main concern regarding particular Branch & Bound algorithm is only its search speed.; 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.