Decomposition Class Reference

#include <Decomposition.h>

Inheritance diagram for Decomposition:

List of all members.

Public Types
typedef bool(*	SolutionCallback )(Decomposition &, bool &)
	The type of the solution callback functions.
typedef bool(*	EvaluationCallback )(Decomposition &, bool &)
	The type of the evaluation callback functions.
typedef bool(*	RefutationCallback )(Decomposition &, bool &)
	The type of the refutation callback functions.
typedef hash_set< Variable * >	ActiveVariablesSet
	The type used to pass sets of active variables around.
typedef hash_set< Constraint * >	ActiveConstraintsSet
	The type used to pass sets of active constraints around.
enum	Statistics {   NoStatistics = 0, AverageUninstantiatedVariables = 1, AverageModifiedVariables = 2, AverageDomainSize = 4,   AverageActiveConstraints = 8, AverageVariableDegree = 16, AverageConstrainedness = 32, AverageConstraintDensity = 64,   AverageConstraintTightness = 128, AverageLooseConstraints = 256, AverageLeafDepth = 512, Nodes = 1024,   Leaves = 2048, ExtraPropagationStatistics = 4096, VariableSelectionCounters = 8192, LastPathSelections = 16384,   Backdoor = 32768, BranchingAssignments = 65536, AllStatistics = UINT_MAX }
enum	Features {   NoFeatures = 0, StaticOptimismBucketing = 1, DynamicOptimismBucketing = 2, GreedyVariableProcessing = 8,   LooseConstraintsDeactivation = 16, FailFirstnessAnalysis = 32, AggregateScoreValueSelection = 64, AllFeatures = UINT_MAX }
Public Member Functions
virtual	~Decomposition ()
	Destructor. It deallocates the list of uninstantiated variables.
const wstring	name () const
	Return the name of the decomposition algorithm.
const wstring &	fullName () const
	Return the full name of the decomposition algorithm.
const wstring &	shortName () const
	Return the short name of the decomposition algorithm.
const Problem &	problem () const
	Return the problem to solve.
Problem &	problem ()
	Return the problem to solve.
const Filter &	filter () const
	Return the filter used.
Filter &	filter ()
	Return the filter used.
const Retraction &	retraction () const
	Return the retraction method used when backtracking.
Retraction &	retraction ()
	Return the retraction used when backtracking.
int	depth () const
	Return the current depth of the search.
void	keepBestValues (double percentage)
double	percentageOfInstantiatedVariables () const
void	getModifiedVariables (int depth, vector< Variable * > &modifiedVariables) const
ulonglong	solutions () const
bool	registerHeuristic (VariableOH &heuristic, bool back=true)
bool	unregisterHeuristic (VariableOH &heuristic)
size_t	variableOrderingHeuristics () const
	Return the number of variable ordering heuristics registered.
VariableOH &	variableOrderingHeuristic (size_t n) const
bool	registerHeuristic (ValueOH &heuristic, bool back=true)
bool	unregisterHeuristic (ValueOH &heuristic)
size_t	valueOrderingHeuristics () const
	Return the number of value ordering heuristics registered.
ValueOH &	valueOrderingHeuristic (size_t n) const
const vlist_type &	uninstantiatedVariables () const
void	getInstantiatedVariables (hash_set< const Variable * > &c) const
const shash_type &	solutionsLeft () const
	Return the list of known solutions that have not been found yet.
void	getKnownSolutions (const hash_set< const Variable * > &instantiatedVariables, const shash_type &solutionsLeft, shash_type &goodSolutions, shash_type &badSolutions) const
void	getPerfectValues (const Variable &variable, hash_set< const Value * > &values, const shash_type &solutions) const
void	setSolutionCallback (SolutionCallback solutionCallback)
SolutionCallback	solutionCallback () const
void	setEvaluationCallback (EvaluationCallback evaluationCallback)
EvaluationCallback	evaluationCallback () const
void	setRefutationCallback (RefutationCallback refutationCallback)
RefutationCallback	refutationCallback () const
ulonglong	search (const bool yield=false, const vlist_type &instantiables=s_all)
void	buildActiveSets (const vlist_type &variables, ActiveVariablesSet &avs, ActiveConstraintsSet &acs) const
int	depthOfDeepestModifiedVariable (const hash_set< id_t > &wanted) const
size_t	branching (Variable &variable, hash_map< const Value *, size_t > &costs, int level, bool minimum=true)
void	postPropagationDomainSizes (Variable &variable, hash_map< const Value *, size_t > &domainSizes, bool minimum=true)
ulonglong	totalNodes () const
	Return the total number of nodes so far.
double	staticOptimismPercentage () const
void	setStaticOptimismPercentage (double percentage)
double	dynamicOptimismPercentage () const
void	setDynamicOptimismPercentage (double percentage)
const BitFlags &	statistics () const
bool	setStatistics (const BitFlags::Flags flags)
const BitFlags &	features () const
bool	setFeatures (const BitFlags::Flags flags)
const PropagationStatistics &	propagationStatistics () const
	Return the object storing propagation-related statistics.
const Resources &	resources () const
	Return the resources used up by this decomposition.
Resources &	resources ()
	Return the resources used up by this decomposition.
const vector< long double > &	averageUninstantiatedVariables () const
const vector< long double > &	averageModifiedVariables () const
const vector< long double > &	averageDomainSize () const
	Return an object containing the average domain size per depth.
const vector< long double > &	averageMinimumDomainSize () const
	Return an object containing the average minimum domain size per depth.
const vector< long double > &	averageMaximumDomainSize () const
	Return an object containing the average maximum domain size per depth.
const vector< long double > &	averageActiveConstraints () const
const vector< long double > &	averageVariableDegree () const
const vector< long double > &	averageConstrainedness () const
const vector< long double > &	averageConstraintDensity () const
const vector< long double > &	averageConstraintTightness () const
const vector< long double > &	averageLooseConstraints () const
const vector< hash_map< Variable *, ulonglong > > &	variableSelectionCounters () const
const vector< vector< pair< Variable *, Domain * > > > &	lastPathSelections () const
	Return the selections made on the last path.
const vector< pair< Variable *, Domain * > > &	backdoor () const
const vector< vector< pair< Variable *, Domain * > > > &	branchingAssignments () const
Driver *	driver ()
	Return the decomposition's driver, if any.
const Driver *	driver () const
	Return the decomposition's driver, if any.
const timeval &	timeLimit () const
bool	timeLimitEnabled () const
	Return `true' if a time limit has been set, `false' otherwise.
timeval	setTimeLimit (const timeval &timeLimit)
bool	timeLimitExceeded ()
const ulonglong	nodeLimit () const
bool	nodeLimitEnabled () const
	Return `true' if a node limit has been set, `false' otherwise.
ulonglong	setNodeLimit (const ulonglong nodeLimit)
bool	nodeLimitExceeded ()
ulonglong	setRefutationsLimit (ulonglong refutationsLimit)
void	setRefutationNodesUpperBound (ulonglong nodes)
	Set the upper bound on the number of nodes for a refutation.
void	recordRefutationParameters (const ulonglong ccks, const ulonglong nodes, const Resources &resources, const int depth)
void	currentRefutation (vector< vector< id_t > > &variables, vector< vector< id_t > > &values)
bool	shortestRefutation (Refutation &refutation) const
ulonglong	shortestRefutationNodes () const
void	setRefutationDepthUpperBound (int depthUpperBound)
void	setIterativeDeepening (bool iterativeDeepening)
void	setLookAheadLevel (int lookAheadLevel)
void	setOptimalRefutationCaching (bool caching)
void	setConsistencyBeforeSearch (bool consistencyBeforeSearch)
size_t	ffaDynamicUpperBoundThreshold () const
void	setFFADynamicUpperBoundThreshold (size_t nVariables)
int	ffaProgressReportingDepthLimit () const
	Return the depth past which progress is not reported (FFA).
void	setFFAProgressReportingDepthLimit (int limit)
	Set the depth past which progress is not reported (FFA).
size_t	ffaLowerBoundLookAheadLevel () const
void	setFFALowerBoundLookAheadLevel (size_t level)
double	setFFAOptimismPercentage () const
void	setFFAOptimismPercentage (double percentage)
int	maximumSearchDepth () const
long double	constrainedness (const ActiveVariablesSet &avs, const ActiveConstraintsSet &acs) const
ulonglong	nodes (int depth) const
ulonglong	leaves (int depth) const
const vector< vector< ulonglong > > &	mistakePointNodes (int depth) const
const vector< vector< ulonglong > > &	mistakePointLeaves (int depth) const
ulonglong	backtracks (int depth) const
int	solutionDepth () const
const vector< ulonglong > &	solutionHeuristicMistakes () const
const vector< ulonglong > &	globalHeuristicMistakes () const
ulonglong	refutationSizeLowerBound (int lookAheadLevel)
ulonglong	initialRefutationSizeLowerBound () const
	Return the initial refutation size lower bound.
void	generateProblemGraph (wostream &wos) const
void	generateProblemGraph (const wstring &stem) const
bool	scheduleProblemGraphGeneration (const wstring &stem, int depth)
bool	scheduleSearchTreeGeneration (const wstring &stem, int depth)
Static Public Attributes
const timeval	NoTimeLimit = { LONG_MAX, LONG_MAX }
	Value used to disable the search time limit.
const ulonglong	NoNodeLimit = ULONGLONG_MAX
	Value used to disable the node limit during search.
const bool	KeepChanges = true
const bool	DiscardChanges = false
const bool	ReselectAllowed = true
const bool	ReselectProhibited = false
Protected Member Functions
virtual bool	init ()
virtual void	done ()
void	eureka ()
bool	hideBadValues (Variable &variable) const
ulonglong	totalValues (vlist_type &variables) const
virtual void	decompose ()=0
bool	propagate (const bool keepChanges=KeepChanges, const vlist_type &instantiables=s_all)
bool	propagateAndSearch (const vlist_type &instantiable=s_all)
bool	canYield () const
Variable *	selectVariable (const bool reselectOk=ReselectAllowed, const vlist_type &undesirables=s_empty)
Variable &	selectVariable (Variable &variable)
size_t	selectAllVariables (vlist_type *selection=0)
void	unselectVariable (Variable &variable)
Value *	selectValue (Variable &variable, Domain &domain)
void	unselectValue (Domain &domain, Value *value)
void	saveState ()
	Save the state of all current and future variables.
void	restoreState ()
	Restore the state of all current and future variables.
bool	moreWork ()
bool	moreSolutionsNeeded () const
bool	discardableSubtree ()
bool	atJumpDepth () const
void	restrict (const vlist_type &variables)
void	unrestrict ()
void	printStack ()
	Decomposition (const wstring &fullName, const wstring &shortName, Problem &problem, Filter &filter, Retraction &retraction, Randomizer &randomizer, bool consistencyBeforeSearch=true)
Protected Attributes
Problem &	m_problem
	The problem to be solved.
vector< SolutionCallback >	m_solutionCallbacks
vector< EvaluationCallback >	m_evaluationCallbacks
vector< RefutationCallback >	m_refutationCallbacks
bool	m_consistencyBeforeSearch
	`true' if consistency should be restored before search.
Friends
class	Driver

---

Detailed Description

The super class of all the decomposition algorithms.

---

Member Enumeration Documentation

enum Decomposition::Features

Enumeration values: NoFeatures  No features. StaticOptimismBucketing  This controls bucketing when static optimism is active. When it is, values that are equally good according to the value ordering heuristic are grouped together. DynamicOptimismBucketing  This controls bucketing when dynamic optimism is active. When it is, values that are equally good according to the value ordering heuristic are grouped together. GreedyVariableProcessing  Control the automatic processing of variables whose domain has been reduced to a single value. If this is active, such variables will be automatically instantiated and removed from the set of active variables, thus reducing the depth of the search tree. LooseConstraintsDeactivation  This controls the deactivation of loose constraints (i.e. constraints whose tightness=0). Deactivating loose constraints can increase the accuracy of certain variable ordering heuristics, like min-domain/degree. FailFirstnessAnalysis  This controls whether or not the decomposition will attempt to analyze the variable ordering heuristic's fail-firstness. If turned on, the decomposition will try to find a shorter refutation for each insoluble subtree. It employs an exhaustive search that takes a lot of time. AggregateScoreValueSelection  Select the value with the highest score. A value's score is computed by multiplying the scores assigned to that value by each heuristic in the chain of value ordering heuristics. By default, this is off and value selection proceeds in the normal, tie-breaking mode, i.e. each value ordering heuristic selects a set of values and ties are broken by the next heuristic in the chain. AllFeatures  This include all the above flags.

enum Decomposition::Statistics

Enumeration values: NoStatistics  No statistics. AverageUninstantiatedVariables  This controls the computation of the average number of uninstantiate variables at each depth. AverageModifiedVariables  This controls the computation of the average number of modified variables at each depth. AverageDomainSize  This controls the computation of the average domain size at each depth. AverageActiveConstraints  This controls the computation of the average number of active constraints at each depth. AverageVariableDegree  This controls the computation of the average degree at each depth. AverageConstrainedness  This controls the computation of the average constrainedness at each depth. AverageConstraintDensity  This controls the computation of the average constraint density at each depth. AverageConstraintTightness  This controls the computation of the average constraint tightness at each depth. AverageLooseConstraints  This controls the computation of the average number of loose constraints at each depth. AverageLeafDepth  This controls the computation of the average leaf depth, measured from the mistake point. Nodes  This controls the computation of the number of nodes. Based on this we can compute the number of backtracks. Leaves  This controls the computation of the number of leaves. ExtraPropagationStatistics  This controls the computation of the extra propagation statistics. VariableSelectionCounters  This controls the computation of the variable selection counters. LastPathSelections  This controls the computation of the last path variable selection counters and selected values. Backdoor  This controls the computation of the backdoor. BranchingAssignments  This controls the computation of the branching assignments. AllStatistics  This include all the above flags.

---

Constructor & Destructor Documentation

Decomposition::Decomposition (  const wstring &  fullName, const wstring &  shortName, Problem &  problem, Filter &  filter, Retraction &  retraction, Randomizer &  randomizer, bool  consistencyBeforeSearch = true )  [protected]

Constructor for various decomposition algorithms. Parameters: name  the name of the algorithm. problem  the problem to be solved. filter  the filter to be used. retraction  the retraction to be used when backtracking. randomizer  the random number generator to be used.

---

Member Function Documentation

bool Decomposition::atJumpDepth (   )  const [inline, protected]

If the installed retraction considers this depth as a return target, then this function returns true. Returns: `true' if the current depth is a retraction target depth, `false' otherwise.

const vector<long double>& Decomposition::averageActiveConstraints (   )  const [inline]

Return an object containing the average number of active constraints per depth.

const vector<long double>& Decomposition::averageConstrainedness (   )  const [inline]

Return an object containing the average constrainedness per depth.

const vector<long double>& Decomposition::averageConstraintDensity (   )  const [inline]

Return an object containing the average constraint density per depth.

const vector<long double>& Decomposition::averageConstraintTightness (   )  const [inline]

Return an object containing the average constraint tightness per depth.

const vector<long double>& Decomposition::averageLooseConstraints (   )  const [inline]

Return an object containing the average number of loose constraints per depth.

const vector<long double>& Decomposition::averageModifiedVariables (   )  const [inline]

Return an object containing the average number of modified variables per depth.

const vector<long double>& Decomposition::averageUninstantiatedVariables (   )  const [inline]

Return an object containing the average number of uninstantiated variables per depth.

const vector<long double>& Decomposition::averageVariableDegree (   )  const [inline]

Return an object containing the average variable degree per depth.

const vector<pair <Variable*, Domain*> >& Decomposition::backdoor (   )  const [inline]

Return the backdoor computed for the most recent solution. Note that the returned object is valid only for the duration of the call to the solution callback.

ulonglong Decomposition::backtracks (  int  depth  )  const

Return the number of backtracks at a given depth. Parameters: depth  the depth. Returns: the number of backtracks at the given depth.

size_t Decomposition::branching (  Variable &  variable, hash_map< const Value *, size_t > &  costs, int  level, bool  minimum = true )

Compute branching for a given variable. Parameters: variable  the variable to compute branching for. costs  the branching contributions, per value. level  the number of levels to look ahead. minimum  `true' for minimum, `false' for maximum. Returns: the branching contribution of `variable'.

const vector<vector<pair <Variable*, Domain*> > >& Decomposition::branchingAssignments (   )  const [inline]

Return the branching assignments computed for the most recent solution. Note that the returned object is valid only for the duration of the call to the solution callback.

void Decomposition::buildActiveSets (  const vlist_type &  variables, ActiveVariablesSet &  avs, ActiveConstraintsSet &  acs )  const

Build the set of the active constraints and variables starting from a set of uninstantiated variables. Parameters: variables  the set of uninstantiated variables. avs  container where the set of active variables are to be placed. acs  container where the set of active constraints are to be placed.

bool Decomposition::canYield (   )  const [protected]

Ask the driver (if any) if there is a registered decomposition algorithm to yield to. Depending on whether or not we can yield control to another decomposition algorithm, the implementation can choose to decompose the problem into subproblems in a different way. Returns: `true' if yielding control is possible, `false' otherwise.

long double Decomposition::constrainedness (  const ActiveVariablesSet &  avs, const ActiveConstraintsSet &  acs )  const

Compute the problem's constrainedness. Parameters: avs  container where the set of active variables are to be placed. acs  container where the set of active constraints are to be placed. Returns: the problem's constrainedness.

void Decomposition::currentRefutation (  vector< vector< id_t > > &  variables, vector< vector< id_t > > &  values )

Return the assignments making up the current, not verified refutation. This will be used from the refutation callback to evaluate the refutation. Parameters: variables  the predefined ordering for variables, per depth. values  the predefined ordering for values, per depth.

virtual void Decomposition::decompose (   )  [protected, pure virtual]

The actual search engine. It implements the decomposition. Note that this method is not supposed to be called directly, therefore it should be made "private" in the derived classes.

int Decomposition::depthOfDeepestModifiedVariable (  const hash_set< id_t > &  wanted  )  const

Given a set of variables, search for the one that has been modified most recently (i.e. can be found closer to the top of the stack in the decomposition's history of selected and unselectable variables), and return its depth. Parameters: wanted  the list of variables of interest. Returns: the depth of a variable matching the criteria, or -1 if no such variable is found.

bool Decomposition::discardableSubtree (   )  [protected]

If an evaluation callback is installed at this depth, this function will tell whether the remaingin search subtree can be discarded or not. The tree can be discarded if the evaluation callback decides that no solution can be found in it. Returns: `true' if there's no point in searching the remaining subtree, `false' otherwise.

void Decomposition::done (   )  [protected, virtual]

Finalize a search. Derived classes overwriting this should always call it!

double Decomposition::dynamicOptimismPercentage (   )  const [inline]

Return the percentage of dynamic optimism. See setDynamicOptimismPercentage() for details.

void Decomposition::eureka (   )  [protected]

This method gets called when all the variables are instantiated (and thus we have a solution).

EvaluationCallback Decomposition::evaluationCallback (   )  const [inline]

Return the current evaluation callback. Returns: the current evaluation callback.

const BitFlags& Decomposition::features (   )  const [inline]

Return the object containing the decomposition's features-related flags. See the Features enum for details.

size_t Decomposition::ffaDynamicUpperBoundThreshold (   )  const [inline]

Return the number of variables a (sub)problem must contain for the search for optimal refutations to attempt to obtain tighter upper bounds dynamically by running a search in that subtree.

size_t Decomposition::ffaLowerBoundLookAheadLevel (   )  const [inline]

Return the look-ahead level for the algorithm estimating the refutation size lower bound (FFA).

void Decomposition::generateProblemGraph (  const wstring &  stem  )  const

Generate a graph of the current (sub)problem in AT&T's Graphviz DOT format. Parameters: stem  the stem of the file to be used to store the graph representation (i.e. the file name without the ".dot" extension).

void Decomposition::generateProblemGraph (  wostream &  wos  )  const

Generate a graph of the current (sub)problem in AT&T's Graphviz DOT format. Parameters: wos  an output stream to output the graph to.

void Decomposition::getInstantiatedVariables (  hash_set< const Variable * > &  c  )  const

Create a list containing all the instantiated variables, including those that have been permanently selected at each depth. Parameters: c  the container where instantiated variables are to be placed.

void Decomposition::getKnownSolutions (  const hash_set< const Variable * > &  instantiatedVariables, const shash_type &  solutionsLeft, shash_type &  goodSolutions, shash_type &  badSolutions )  const

Compute the list of possible solutions based on the set of variables that have just been instantiated and the list of previously known good solutions. Parameters: instantiatedVariables  the list of variables that have been instantiated since solutionsLeft has been computed. solutionsLeft  the list of solutions that used to be considered valid before the latest instantiations. goodSolutions  a container where known good solutions are to be stored. badSolutions  a container where known bad solutions are to be stored.

void Decomposition::getModifiedVariables (  int  depth, vector< Variable * > &  modifiedVariables )  const

Return the set of variables modified at the given depth. The depth should be less than or equal to the current depth. Parameters: depth  the depth to report on. modifiedVariables  the vector in which the variables should be placed.

void Decomposition::getPerfectValues (  const Variable &  variable, hash_set< const Value * > &  values, const shash_type &  solutions )  const

Compute the set of values that can be assigned to the given variable and would extend the current set of instantiated variables towards a solution. Parameters: variable  the variable for which perfect values are to be computed. values  a container to store perfect values into. solutions  the currently known valid solutions, as returned by getKnownSolutions().

const vector<ulonglong>& Decomposition::globalHeuristicMistakes (   )  const [inline]

Return the sum, over all the solutions found so far, of the number of value ordering heuristic mistakes at each depth. Returns: a vector containing the described data.

bool Decomposition::hideBadValues (  Variable &  variable  )  const [protected]

Hide bad values for the current variable if dynamic optimism is on. Parameters: variable  the variable whose bad values are to be hidden. Returns: `true' if some values were hidden, `false' otherwise.

bool Decomposition::init (   )  [protected, virtual]

Prepare the decomposition for a new search. Derived classes overwriting this should always call it! Returns: `true' on success, `false' otherwise.

void Decomposition::keepBestValues (  double  percentage  )

Keep the best values in the domain of each variable. Best values are determined based on the order in which they are sorted by the first value ordering heuristic installed. If no value ordering heuristics are installed, this function will not do anything. Parameters: percentage  the percentage of values to be kept; the rest of the values will simply be discarded, i.e. permanently removed from the domain of the variable.

ulonglong Decomposition::leaves (  int  depth  )  const

Return the number of leaves touched at a given depth. Parameters: depth  the depth. Returns: the number of leaves touched at the given depth.

int Decomposition::maximumSearchDepth (   )  const

Return the maximum depth reached so far by this decomposition algorithm during search.

const vector<vector<ulonglong> >& Decomposition::mistakePointLeaves (  int  depth  )  const [inline]

Return a vector of vectors containing the number of leaves per depth in each subtree rooted at a mistake point located at the given depth. Parameters: depth  the depth of the mistake point. Returns: the vector of vectors containing the number of leaves per depth for each mistake point.

const vector<vector<ulonglong> >& Decomposition::mistakePointNodes (  int  depth  )  const [inline]

Return a vector of vectors containing the number of nodes per depth in each subtree rooted at a mistake point located at the given depth. Parameters: depth  the depth of the mistake point. Returns: the vector of vectors containing the number of nodes per depth for each mistake point.

bool Decomposition::moreSolutionsNeeded (   )  const [inline, protected]

Return `true' if more solutions are needed at the current depth in the search. This is based on the solution callback's return value. Returns: `true' if the search should look for more solutions, `false' otherwise.

bool Decomposition::moreWork (   )  [protected]

Check whether or not the decomposition should continue at the current depth. Currently, moreWork() returns `false' only if one of the following 4 conditions is true: 1. According to the solution callback no more solutions are needed. 2. According to the evaluation callback, no solution can be found in the remaining search subtree. 3. All the variables have been instantiated. 4. We're not at a depth that is considered a backjumping target by the retraction. This is not a one-size-fits-all solution to terminating a decomposition. It is suitable for most decompositions, but not all. Some decompositions are more complex, requiring a much closer monitoring of their termination condition. See Local Changes (LC) for an example. Returns: `true' if the decomposition should continue at the current depth, `false' otherwise.

const ulonglong Decomposition::nodeLimit (   )  const [inline]

Return the number of nodes the algorithm is allowed to create from the moment it has been started. Returns: the node limit.

bool Decomposition::nodeLimitExceeded (   )

Check whether or not the node limit has been exceeded. Returns: `true' if the node limit has been exceeded, `false' otherwise.

ulonglong Decomposition::nodes (  int  depth  )  const

Return the number of nodes touched at a given depth. Parameters: depth  the depth. Returns: the number of nodes touched at the given depth.

double Decomposition::percentageOfInstantiatedVariables (   )  const

Return the percentage of instantiated variables. Note that since the uninstantiated variables are kept in a list, this function is not constant time.

void Decomposition::postPropagationDomainSizes (  Variable &  variable, hash_map< const Value *, size_t > &  domainSizes, bool  minimum = true )

Compute the minimum/maximum post-propagation domain sizes among future variables for a given variable's values. Parameters: variable  the variable to compute post-propagation data for. domainSizes  the post-propagation domain sizes, per value. preference  `true' for minimum, `false' for maximum.

void Decomposition::printStack (   )  [protected]

Print the stack of all the calls to decompose() and their arguments. To be used for debugging purposes only!

bool Decomposition::propagate (  const bool  keepChanges = KeepChanges, const vlist_type &  instantiables = s_all )  [protected]

Call the filter to make sure the problem is consistent (or arc consistent), depending on the type of the filter used. Depending on how this function has been called, the changes caused to the domains of the variables filtered will be restored or postponed. If this has been a permanent filtration at the current depth, then the only way to restore those changes is to return to the previous depth in the decomposition. Upon successful return from a non-preview call, all variables selected at the current depth will be unselected. Parameters: keepChanges  if `false', work in preview mode, that is restore upon return the domains of the variables filtered out; this can be used to see if the problem is still consistent, w/o leaving the results of the filtration in place. instantiables  a list of variables that can be instantiated at this level before a recursive search; if not given, all uninstantiated variables whose domains have been reduced to one value will be instantiated. LC is a good example of a decomposition that uses this - it selects variables but it doesn't necessarily instantiate them, not even if their domain has been reduced to one single value - it adds them to its list of "uncertain variables" instead. Returns: `true' if the filtration succeeded, `false' otherwise.

bool Decomposition::propagateAndSearch (  const vlist_type &  instantiable = s_all  )  [protected]

This function implements the usual sequence, used in most decomposition algorithms, that saves the state of all the uninstantiated variables, filters the problem (and does a recursive `search()' if succesful), then restores the state of the uninstantiated variables. Note that variables considered selected will continue to be so upon return from this function. Parameters: instantiable  a list of variables that can be instantiated at this level before a recursive search; if not given, all uninstantiated variables whose domains have been reduced to one value will be instantiated. Returns: `true' if the propagation has been successful (and thus a recursive search has been attempted).

void Decomposition::recordRefutationParameters (  const ulonglong  ccks, const ulonglong  nodes, const Resources &  resources, const int  depth )

Record the parameters of a new refutation when performing fail-firstness analysis. The refutation callback is called to verify whether or not a newly found refutation is shorter than the previous shortest. If it is, then those refutation parameters that are only accessible in the callback are gonna be made available to this Decomposition object through this function. Parameters: ccks  the number of constraint checks. nodes  the number of nodes. resources  the resources (usually time). depth  the depth.

RefutationCallback Decomposition::refutationCallback (   )  const [inline]

Return the current refutation callback. Returns: the current refutation callback.

ulonglong Decomposition::refutationSizeLowerBound (  int  lookAheadLevel  )

Return a lower bound on the number of nodes in any refutation. Look ahead the given number of levels. If the look-ahead level is 0, then this only takes into consideration the current depth limit (if iterative deepening is on) and the extra cost (if computed previously). Parameters: lookAheadLevel  the level of look-ahead. Returns: the lower bound on the number of nodes.

bool Decomposition::registerHeuristic (  ValueOH &  heuristic, bool  back = true )

Register a value ordering heuristic. Parameters: heuristic  the value ordering heuristic. back  `true' if the new heuristic is to be added at the end of the list of heuristics, `false' if it is to be inserted at the beginning of the list. `true'  on success, `false' if the heuristic is already registered or some other error occured.

bool Decomposition::registerHeuristic (  VariableOH &  heuristic, bool  back = true )

Register a variable ordering heuristic. Parameters: heuristic  the variable ordering heuristic. back  `true' if the new heuristic is to be added at the end of the list of heuristics, `false' if it is to be inserted at the beginning of the list. Returns: `true' on success, `false' if the heuristic is already registered or some other error occured.

void Decomposition::restrict (  const vlist_type &  variables  )  [protected]

Restrict subsequent recursive searches in this decomposition to a subset of the uninstantiated variables. All uninstantiated variables that are not part of the given subset are marked as hidden, and so are all their active constraints. A new solution counter is gonna be used, and it is initialized to 0. The solution callback is reset, but it can be set upon return from restrict(), if that is useful. Unless that's done, the search for a solution in the subproblem will stop once the first solution is found. Finally, the evaluation callback is set to 0 as well, which means that unless it is set to something else before the next recursive call, restricted subproblems will always evaluate as if there is still potential for a (sub)solution. Parameters: variables  the set of uninstantiated variables to restrict the search to.

bool Decomposition::scheduleProblemGraphGeneration (  const wstring &  stem, int  depth )

Generate two graphs of the current (sub)problem by calling generateProblemGraph() the next time the search reaches the given depth (once going down and another time when backtracking). Parameters: stem  the stem of the file to be used to store the graph representation (i.e. the file name without the ".dot" extension). depth  the depth that will trigger the graph generation, or -1 if graph generation is to be disabled. return  `true' on success, `false' otherwise.

bool Decomposition::scheduleSearchTreeGeneration (  const wstring &  stem, int  depth )

Generate a graph of the current (sub)tree using AT&T's Graphviz DOT format. Parameters: stem  the stem of the file to be used to store the graph representation (i.e. the file name without the ".dot" extension). depth  the depth that will trigger the search tree generation, or -1 if search tree generation is to be disabled. return  `true' on success, `false' otherwise.

ulonglong Decomposition::search (  const bool  yield = false, const vlist_type &  instantiables = s_all )

This method will invoke the search engine to look for solutions. `search()' will use `decompose()' internally to keep looking for solutions as long as the current solution callback - which is called every time a solution is found - returns `true'. The actual number of solutions found until the search was stopped (by the current solution callback returning `false' or by the lack of more solutions) is returned. The value returned by the solution callback is stored in `m_moreSolutionsNeeded'. Parameters: yield  `true' if the decompose() function is willing to yield control to another decomposition algorithm, `false' otherwise. Obviously, it doesn't make sense to pass this parameter to the top-level call to `search()'. instantiables  a list of variables that can be instantiated at this level before a recursive search; if not given, all uninstantiated variables whose domains have been reduced to one value will be instantiated. Returns: the number of solutions found. See also: #solution

size_t Decomposition::selectAllVariables (  vlist_type *  selection = 0  )  [protected]

Sometimes it may be necessary to select all the variables that remain unselected at a certain level. This function does that quickly, without applying any heuristics, as the order in which they are selected is not important. Parameters: selection  a pointer to a list of variables; if not NULL, this method should fill the list with the selected variables. Returns: the number of variables selected.

Value * Decomposition::selectValue (  Variable &  variable, Domain &  domain )  [protected]

Apply the value ordering heuristics. Select a value from the given domain using the heuristic objects registered. `domain' must be subset of the variable's domain containing only those values that are to be considered eligible by this selection. The variable's actual domain object is not changed by this function. Parameters: variable  the variable to select a value for. domain  a subset of eligible values in the domain of the given variable. Returns: a pointer to the most eligible value.

Variable & Decomposition::selectVariable (  Variable &  variable  )  [protected]

Similar to selectVariable(), but using a given non-instantiated variable from `m_uninstantiatedVariables' rather than computing one using the variable ordering heuristics. Reselection is allowed implicitly. Parameters: variable  the variable to be selected. Returns: the variable that has just been selected.

Variable * Decomposition::selectVariable (  const bool  reselectOk = ReselectAllowed, const vlist_type &  undesirables = s_empty )  [protected]

Apply the variable order heuristics. Select a variable from `m_uninstantiatedVariables' using the heuristic objects registered. A decomposition algorithm should not change the domain of a variable unless that variable has been selected (and not unselected) prior to the change. The purpose of the selection mechanism is two-fold. One reason is that we want to be able to select variables based on variable ordering heuristics, and selectVariable() calls each such heuristic in the order in which they were registered, successively reducing the list of preferred variables until only one variable is left or there are no more heuristics to try (in which case the first preferred variable is selected). The second purpose of the variable selection mechanism is that the library needs to keep track of the changes made to the domains of uninstantiated variables by filters and decompositions. By forcing decompositions to select variables using selectVariable(), the library can pass to each filter a list of variables whose domains have been (potentially) modified, saving the filter some unnecessary work. Inside decompose() (which is where variables are normally selected), depending on the decomposition algorithm, either propagateAndSearch() or propagate() will be called. In the first case, upon return from propagateAndSearch(), selected variables will continue to be selected, as all changes and filtrations that had happened during that recursive call have been undone. In the second case however, if propagate(true) succeeds in further filtering the problem, it will perform changes that are considered permanent at the current depth, and so all selected variables will be unselected. Some variables will even become instantiated (as a result of filtration reducing their domain to one value) and will be marked as unselectable. Upon a successful return from propagate(true), all selected variables that the decomposition still wants to work on will have to be re-selected. The MC.cc code is a good example of what needs to be done when calling both propagateAndSearch() and propagate(). Note that once a variable has been selected, the decomposition algorithm can change its domain in any way it sees fit, as long as it never adds to it values that weren't in its domain at the current depth. Parameters: reselectOk  `ReselectAllowed' if variables that have already been selected are to be considered, `ReselectProhibited' otherwise. undesirables  a list of variables that should not be selected by this function even if they are uninstantiated and `reselectOk' is set to `ReselectAllowed'. Returns: a pointer to the most eligible variable, or NULL if no selectable variable can be found (the list of uninstantiated variables is either empty or a subset of the list of undesirables.

void Decomposition::setConsistencyBeforeSearch (  bool  consistencyBeforeSearch  )

Activate/deactivate the enforcement of consistency at the beginning of the search. This has no effect when filters that restore arc-consistency are in use.

void Decomposition::setDynamicOptimismPercentage (  double  percentage  )  [inline]

Set the dynamic optimism percentage. If the decomposition's optimism percentage is greater than 0, then each variable's domain of values is sorted according to the first value ordering heuristic, then the given percentage of values is removed from the end of the sorted domain. A decomposition that implements this should return `true' in `supportsOptimism()'. Parameters: factor  the percentage of values to be removed.

void Decomposition::setEvaluationCallback (  EvaluationCallback  evaluationCallback  )  [inline]

Set the function to be called to evaluate the possibility that a solution will be found in the current subtree. If the function returns `false' the subtree is skipped. System resources used by the refutation callback are by default included when computing the resources used by search(). If a callback changes the order of the values in the domain of a variable and the library is in "predictable" mode, the callback must restore the order by calling Variable::sortDomain(). Parameters: evaluationCallback  the function to be called.

bool Decomposition::setFeatures (  const BitFlags::Flags  flags  )

Set the decomposition's features-related flags. See the Features enum for details. Note that flags cannot be set during search (i.e. on callbacks). Returns: `true' upon success, `false' upon failure.

void Decomposition::setFFADynamicUpperBoundThreshold (  size_t  nVariables  )  [inline]

Set the number of variables a (sub)problem must contain for the search for optimal refutations to attempt to obtain tighter upper bounds dynamically by running a search in that subtree.

void Decomposition::setFFALowerBoundLookAheadLevel (  size_t  level  )  [inline]

Set the look-ahead level for the algorithm estimating the refutation size lower bound (FFA).

void Decomposition::setFFAOptimismPercentage (  double  percentage  )  [inline]

Set the percentage of optimism ((1-optimism)*100 = the percentage of work to complete at each depth in the search for optimal refutations.

double Decomposition::setFFAOptimismPercentage (   )  const [inline]

Return the percentage of optimism ((1-optimism)*100 = the percentage of work to complete at each depth in the search for optimal refutations.

void Decomposition::setIterativeDeepening (  bool  iterativeDeepening  )  [inline]

Activate/deactivate iterative deepening in the fail-firstness analysis. Default is on.

void Decomposition::setLookAheadLevel (  int  lookAheadLevel  )  [inline]

The level of look-ahead in the fail-firstness analysis. Only levels 0 to 2 (default) have been implemented so far.

ulonglong Decomposition::setNodeLimit (  const ulonglong  nodeLimit  )

Control the number of nodes that the search is allowed to create. A value of `NoNodeLimit' disables the node limit. Parameters: nodeLimit  the number of nodes the search is allowed to create. Returns: the previous value of the node limit.

void Decomposition::setOptimalRefutationCaching (  bool  caching  )  [inline]

Activate/deactivate the caching of optimal refutations in the fail-firstness analysis. Default is off.

void Decomposition::setRefutationCallback (  RefutationCallback  refutationCallback  )  [inline]

Set the function to be called to validate a refutation found during the fail-firstness analysis. If the function returns `true' the refutation is considered better than the current one. System resources used by the refutation callback are _not_ included by default when computing the resources used by search(). If a callback changes the order of the values in the domain of a variable and the library is in "predictable" mode, the callback must restore the order by calling Variable::sortDomain(). Parameters: refutationCallback  the function to be called.

void Decomposition::setRefutationDepthUpperBound (  int  depthUpperBound  )

Set the depth limit for refutations found during the search for optimal refutations. No refutation tree depth can exceed the depth configured here.

ulonglong Decomposition::setRefutationsLimit (  ulonglong  refutationsLimit  )

Control the number of "better" refutations to search for. The default is unlimited (or ULONGLONG_MAX). Parameters: refutationsLimit  the number of "better" refutations to search for. Returns: the previous value of the limit.

void Decomposition::setSolutionCallback (  SolutionCallback  solutionCallback  )  [inline]

Set the function to be called when a solution is found. That function should return `true' or `false' depending on whether the search should be continued or not. If no solution callback is provided, the search will stop after the first solution is found. The callback takes as arguments a Decomposition object and a boolean reference. The boolean is `true' by default, but can be set to `false' to prevent the decomposition from taking into account the time spent in the callback in its statistics and timeout (i.e. the Decomposition's timeout will be extended with the appropriate amount of time). System resources used by the refutation callback are by default included when computing the resources used by search(). If a callback changes the order of the values in the domain of a variable and the library is in "predictable" mode, the callback must restore the order by calling Variable::sortDomain(). Parameters: solutionCallback  the function to be called.

void Decomposition::setStaticOptimismPercentage (  double  percentage  )  [inline]

Set the static optimism percentage. If the decomposition's optimism percentage is greater than 0, then each variable's domain of values is sorted according to the first value ordering heuristic, then the given percentage of values is removed from the end of the sorted domain. The search will proceed on the resulting problem, with the expectation that at least one solution will still be found in the smaller problem, potentiall much faster. Parameters: factor  the percentage of values to be removed.

bool Decomposition::setStatistics (  const BitFlags::Flags  flags  )

Set the decomposition's statistics-related flags. See the Statistics enum for details. Note that flags cannot be set during search (i.e. on callbacks). Returns: `true' upon success, `false' upon failure.

timeval Decomposition::setTimeLimit (  const timeval &  timeLimit  )

Control the amount of time that the search is allowed to run. A value of `NoTimeLimit' disables the time limit. Parameters: timeLimit  the amount of time the search is allowed to run. Returns: the previous value of the time limit.

bool Decomposition::shortestRefutation (  Refutation &  refutation  )  const

If fail-firstness is turned on for this decomposition, this function will return the shortest refutation found so far. That consists of a predefined ordering for variables and values, but also includes (to avoid re-computation) the number of nodes in that refutation and its maximum depth, among other things. Parameters: refutation  a placeholder for the shortest refutation's parameters. Returns: `true' if at least one refutation has been found, `false' otherwise.

ulonglong Decomposition::shortestRefutationNodes (   )  const [inline]

Return the number of nodes in the shortest refutation found so far.

SolutionCallback Decomposition::solutionCallback (   )  const [inline]

Return the current solution callback. Returns: the current solution callback.

int Decomposition::solutionDepth (   )  const [inline]

Return the maximum search depth that was reached in the search for the most recent solution.

const vector<ulonglong>& Decomposition::solutionHeuristicMistakes (   )  const [inline]

Return the number of value ordering heuristic mistakes at each depth for the most recent solution. Returns: a vector containing the described data.

ulonglong Decomposition::solutions (   )  const [inline]

Return the number of solutions found so far. Note that the number of solutions is counted separately for each restriction of the problem. See `restrict()' and `unrestrict()' for details. Returns: the number of solutions found.

double Decomposition::staticOptimismPercentage (   )  const [inline]

Return the percentage of static optimism. See setStaticOptimismPercentage() for details.

const BitFlags& Decomposition::statistics (   )  const [inline]

Return the object containing the decomposition's statistics-related flags. See the Statistics enum for details.

const timeval& Decomposition::timeLimit (   )  const [inline]

Return the amount of time the algorithm is allowed to run from the moment it has been started. Returns: the time limit.

bool Decomposition::timeLimitExceeded (   )

Check whether or not the time limit has been exceeded. If it has been, set `m_moreSolutionsNeeded' to false and return true. Setting `m_moreSolutionsNeeded' here is ugly, but it decreases the amount of code people have to write in decompose() in order to deal with timeouts. Note that we do not try to be extremely accurate here - it is quite difficult to do so without increased support from decompose(), something that we want to avoid. The only guarantees are that the algorithm will be allowed to run for at least m_timeLimit time and that it will eventually stop some time after that (depending on the time required to return from all the nested calls). Also, for short timeouts, you might have to wait until the initialization procedures complete (i.e. when using AC-X).

ulonglong Decomposition::totalValues (  vlist_type &  variables  )  const [protected]

Compute the sum of the number of values found in the domains of all the variables in the given list. Parameters: variables  a list of variables. Returns: the requested sum.

const vlist_type& Decomposition::uninstantiatedVariables (   )  const [inline]

Return the list of uninstantiated variables.

bool Decomposition::unregisterHeuristic (  ValueOH &  heuristic  )

Unregister a previously registered value ordering heuristic. Parameters: heuristic  the value ordering heuristic. Returns: `true' on success, `false' if the heuristic is not registered.

bool Decomposition::unregisterHeuristic (  VariableOH &  heuristic  )

Unregister a previously registered variable ordering heuristic. Parameters: heuristic  the variable ordering heuristic. Returns: `true' on success, `false' if the heuristic is not registered.

void Decomposition::unrestrict (   )  [protected]

Reverse the action of the latest `restrict()' call. Hidden variables are reinserted into the list of uninstantiated variables, and their constraints become active again. The solution counter and callback are restored to the values they had before `restrict()' was called. So is the evaluation callback.

void Decomposition::unselectValue (  Domain &  domain, Value *  value )  [inline, protected]

Place `value' back into `domain'. Parameters: domain  the domain of values. value  a pointer to the value to reinsert into the domain.

void Decomposition::unselectVariable (  Variable &  variable  )  [protected]

Unselect a variable whose domain has been restored so that it contains all the values it contained when was first selected at the current depth. Parameters: variable  the variable to be unselected.

ValueOH& Decomposition::valueOrderingHeuristic (  size_t  n  )  const [inline]

Return the nth value ordering heuristic registered. Parameters: n  the index of the requested heuristic. Returns: the nth value ordering heuristic registered.

VariableOH& Decomposition::variableOrderingHeuristic (  size_t  n  )  const [inline]

Return the nth variable ordering heuristic registered. Parameters: n  the index of the requested heuristic. Returns: the nth variable ordering heuristic registered.

const vector<hash_map<Variable*, ulonglong> >& Decomposition::variableSelectionCounters (   )  const [inline]

Return an object containing the number of times a variable has been selected for instantiation at each depth.

---

Friends And Related Function Documentation

friend class Driver [friend]

The driver class needs access to some of the Decomposition's private fields.

---

Member Data Documentation

const bool Decomposition::DiscardChanges = false [static]

The constant passed to `propagate()' to make it discard the filtration changes.

const bool Decomposition::KeepChanges = true [static]

The constant passed to `propagate()' to make it keep the filtration changes.

vector<EvaluationCallback> Decomposition::m_evaluationCallbacks [protected]

The user-supplied function called during the search to evaluate whether or not (acceptable) solutions do exist in the current subtree.

vector<RefutationCallback> Decomposition::m_refutationCallbacks [protected]

The user-supplied function called during the search to determine whether or not the current refutation found during the fail-firstness analysis is better than the previous one. If it is, this callback must call setRefutationUpperBounds() to update the upper bounds.

vector<SolutionCallback> Decomposition::m_solutionCallbacks [protected]

The user-supplied function called during the search when solutions are found.

const bool Decomposition::ReselectAllowed = true [static]

The constant passed to selectVariable() to specify that selecting variables that have already been selected is allowed.

const bool Decomposition::ReselectProhibited = false [static]

The constant passed to selectVariable() to specify that selecting variables that have already been selected is not allowed.

---

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

• Decomposition.h
• Decomposition.cc

---