Minotaur::ParTreeManager Class Reference

Base class for managing the branch-and-bound tree. More...

#include <ParTreeManager.h>

Public Member Functions
	ParTreeManager (EnvPtr env)
	Constructor.
	~ParTreeManager ()
	Destroy.
bool	anyActiveNodesLeft ()
	Return true if any active nodes remain in the tree. False otherwise.
NodePtr	branch (Branches branches, NodePtr node, WarmStartPtr ws)
	Branch and create new nodes. More...
UInt	getActiveNodes () const
	Return the number of active nodes, i.e. nodes that have been created, but not processed yet.
double	getCutOff ()
	Return the cut off value. It is INFINITY if it is not set.
double	getPerGap ()
	Return the gap between the lower and upper bound as a percentage. It is calculated as .
double	getPerGapPar (double treeLb)
	Return the gap between the lower and upper bound as a percentage, given a lower bound, when executing in parallel mode. It is calculated as . More...
double	getLb ()
	Return the value of the highest lower bound evaluated in the last update of he bound. More...
double	getUb ()
	Return the best known upper bound.
UInt	getSize () const
	Return the size of the tree, including both active and processed nodes.
NodePtr	getCandidate ()
	Search for the best candidate that can be processed next. More...
void	insertRoot (NodePtr node)
	Insert the root node into the tree. More...
void	pruneNode (NodePtr node)
	Prune a given node from the tree. More...
void	removeActiveNode (NodePtr node)
	Remove a given active node from storage. More...
void	setCutOff (double value)
	Set the cut off value for the objective function. More...
void	setUb (double value)
	Set the best known objective function value. More...
bool	shouldDive ()
	Return true if the tree-manager recommends diving. False otherwise.
double	updateLb ()
	Recalculate and return the lower bound of the tree. More...

Friends
class	ParBranchAndBound
class	ParQGBranchAndBound

Detailed Description

Base class for managing the branch-and-bound tree.

Member Function Documentation

branch()

NodePtr ParTreeManager::branch	(	Branches	branches,
		NodePtr	node,
		WarmStartPtr	ws
	)

Branch and create new nodes.

Parameters

[in]	branches	The branching constraints or bounds or disjunctions that are used to create the new nodes after branching.
[in]	node	The node that we wish to branch upon.
[in]	ws	The warm starting information that should be linked to in the new nodes.

Returns

The first child node.

getCandidate()

NodePtr ParTreeManager::getCandidate

(

)

Search for the best candidate that can be processed next.

It may prune some of the nodes if their lower bound is more than the upper bound.

Returns

the best candidate found. If no candidate is found, it returns NULL. The candidate is not removed from the storage. It is removed only when removeActiveNode() is called.

getLb()

double ParTreeManager::getLb

(

)

Return the value of the highest lower bound evaluated in the last update of he bound.

Since evaluating the lower bound may be expensive or certain types of tree-managers, it may be updated infrequently. Consquently, the value returned here may be lower than the actual lower bound of the tree. Also see updateLb().

getPerGapPar()

double ParTreeManager::getPerGapPar

(

double

treeLb

)

Return the gap between the lower and upper bound as a percentage, given a lower bound, when executing in parallel mode. It is calculated as .

Parameters

[in]

treeLb

is the lower bound of the tree, considering active nodes and other open nodes that have not been sent to the node pool.

insertRoot()

void ParTreeManager::insertRoot

(

NodePtr

node

)

Insert the root node into the tree.

Parameters

[in]

node

The root node.

pruneNode()

void ParTreeManager::pruneNode

(

NodePtr

node

)

Prune a given node from the tree.

Parameters

[in]

node

The node that must be pruned.

removeActiveNode()

void ParTreeManager::removeActiveNode

(

NodePtr

node

)

Remove a given active node from storage.

It should be called after the node has been processed.

Parameters

[in]

node

The node to be removed from storage.

setCutOff()

void ParTreeManager::setCutOff

(

double

value

)

Set the cut off value for the objective function.

Nodes with lower bound can be pruned.

Parameters

[in]

value

The cut off value. It can be INFINITY.

setUb()

void ParTreeManager::setUb

(

double

value

)

Set the best known objective function value.

The function does NOT check if the given value is better than the previous. So care should be taken to pass only the best known value. It also updates the cutoff value that is used to prune nodes.

Parameters

[in]

value

The best known upper bound.

updateLb()

double ParTreeManager::updateLb

(

)

Recalculate and return the lower bound of the tree.

If the active nodes are stored in a heap, nothing really needs to be done. For other types of storage, this operation may be expensive. The result is cached into bestLowerBound_.

Returns

the updated lower bound.

---

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

• /home/amahajan/tmp/minotaur-test/src/base/ParTreeManager.h
• /home/amahajan/tmp/minotaur-test/src/base/ParTreeManager.cpp