Using MS heap implementation. More...

#include <CbcTree.hpp>

Inheritance diagram for CbcTree:

Collaboration diagram for CbcTree:

Public Member Functions
Constructors and related
	CbcTree ()
	Default Constructor. More...

	CbcTree (const CbcTree &rhs)
	Copy constructor. More...

CbcTree &	operator= (const CbcTree &rhs)
	= operator More...

virtual	~CbcTree ()
	Destructor. More...

virtual CbcTree *	clone () const
	Clone. More...

virtual void	generateCpp (FILE *)
	Create C++ lines to get to current state. More...

Heap access and maintenance methods
void	setComparison (CbcCompareBase &compare)
	Set comparison function and resort heap. More...

virtual CbcNode *	top () const
	Return the top node of the heap. More...

virtual void	push (CbcNode *x)
	Add a node to the heap. More...

virtual void	pop ()
	Remove the top node from the heap. More...

virtual CbcNode *	bestNode (double cutoff)
	Gets best node and takes off heap. More...

virtual void	rebuild ()
	Rebuild the heap. More...

Direct node access methods
virtual bool	empty ()
	Test for an empty tree. More...

virtual int	size () const
	Return size. More...

CbcNode *	operator[] (int i) const
	Return a node pointer. More...

CbcNode *	nodePointer (int i) const
	Return a node pointer. More...

void	realpop ()

void	fixTop ()
	After changing data in the top node, fix the heap. More...

void	realpush (CbcNode *node)

Search tree maintenance
std::vector< CbcNode * >	nodes_
	Storage vector for the heap. More...

CbcCompare	comparison_
	Sort predicate for heap ordering. More...

int	maximumNodeNumber_
	Maximum "node" number so far to split ties. More...

int	numberBranching_
	Size of variable list. More...

int	maximumBranching_
	Maximum size of variable list. More...

double	lastObjective_
	Objective of last node pushed on tree. More...

int	lastDepth_
	Depth of last node pushed on tree. More...

int	lastUnsatisfied_
	Number unsatisfied of last node pushed on tree. More...

unsigned int *	branched_
	Integer variables branched or bounded top bit set if new upper bound next bit set if a branch. More...

int *	newBound_
	New bound. More...

virtual void	cleanTree (CbcModel *model, double cutoff, double &bestPossibleObjective)
	Prune the tree using an objective function cutoff. More...

CbcNode *	bestAlternate ()
	Get best on list using alternate method. More...

virtual void	endSearch ()
	We may have got an intelligent tree so give it one more chance. More...

virtual double	getBestPossibleObjective ()
	Get best possible objective function in the tree. More...

void	resetNodeNumbers ()
	Reset maximum node number. More...

int	maximumNodeNumber () const
	Get maximum node number. More...

void	setNumberBranching (int value)
	Set number of branches. More...

int	getNumberBranching () const
	Get number of branches. More...

void	setMaximumBranching (int value)
	Set maximum branches. More...

int	getMaximumBranching () const
	Get maximum branches. More...

unsigned int *	branched () const
	Get branched variables. More...

int *	newBounds () const
	Get bounds. More...

double	lastObjective () const
	Last objective in branch-and-cut search tree. More...

int	lastDepth () const
	Last depth in branch-and-cut search tree. More...

int	lastUnsatisfied () const
	Last number of objects unsatisfied. More...

void	addBranchingInformation (const CbcModel model, const CbcNodeInfo nodeInfo, const double currentLower, const double currentUpper)
	Adds branching information to complete state. More...

void	increaseSpace ()
	Increase space for data. More...

Detailed Description

Using MS heap implementation.

It's unclear if this is needed any longer, or even if it should be allowed. Cbc occasionally tries to do things to the tree (typically tweaking the comparison predicate) that can cause a violation of the heap property (parent better than either child). In a debug build, Microsoft's heap implementation does checks that detect this and fail. This symbol switched to an alternate implementation of CbcTree, and there are clearly differences, but no explanation as to why or what for.

As of 100921, the code is cleaned up to make it through ‘cbc -unitTest’ without triggering ‘Invalid heap’ in an MSVS debug build. The method validateHeap() can be used for debugging if this turns up again.

Controls search tree debugging

In order to have validateHeap() available, set CBC_DEBUG_HEAP to 1 or higher.

1 calls validateHeap() after each change to the heap
2 will print a line for major operations (clean, set comparison, etc.)
3 will print information about each push and pop

#define CBC_DEBUG_HEAP 1

Implementation of the live set as a heap.

This class is used to hold the set of live nodes in the search tree.

Definition at line 52 of file CbcTree.hpp.

Constructor & Destructor Documentation

◆ CbcTree() [1/2]

CbcTree::CbcTree ( )

Default Constructor.

◆ CbcTree() [2/2]

CbcTree::CbcTree ( const CbcTree & rhs )

Copy constructor.

◆ ~CbcTree()

virtual CbcTree::~CbcTree ( )

virtual

Destructor.

Member Function Documentation

◆ operator=()

CbcTree& CbcTree::operator= ( const CbcTree & rhs )

= operator

◆ clone()

virtual CbcTree* CbcTree::clone ( ) const

virtual

Clone.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

◆ generateCpp()

virtual void CbcTree::generateCpp ( FILE * )

inlinevirtual

Create C++ lines to get to current state.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

Definition at line 73 of file CbcTree.hpp.

◆ setComparison()

void CbcTree::setComparison ( CbcCompareBase & compare )

Set comparison function and resort heap.

◆ top()

virtual CbcNode* CbcTree::top ( ) const

virtual

Return the top node of the heap.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

◆ push()

virtual void CbcTree::push ( CbcNode * x )

virtual

Add a node to the heap.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

◆ pop()

virtual void CbcTree::pop ( )

virtual

Remove the top node from the heap.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

◆ bestNode()

virtual CbcNode* CbcTree::bestNode ( double cutoff )

virtual

Gets best node and takes off heap.

Before returning the node from the top of the heap, the node is offered an opportunity to reevaluate itself. Callers should be prepared to check that the node returned is suitable for use.

◆ rebuild()

virtual void CbcTree::rebuild ( )

virtual

Rebuild the heap.

◆ empty()

virtual bool CbcTree::empty ( )

virtual

Test for an empty tree.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

◆ size()

virtual int CbcTree::size ( ) const

inlinevirtual

Return size.

Definition at line 108 of file CbcTree.hpp.

◆ operator[]()

CbcNode* CbcTree::operator[] ( int i ) const

inline

Return a node pointer.

Definition at line 111 of file CbcTree.hpp.

◆ nodePointer()

CbcNode* CbcTree::nodePointer ( int i ) const

inline

Return a node pointer.

Definition at line 114 of file CbcTree.hpp.

◆ realpop()

void CbcTree::realpop ( )

◆ fixTop()

void CbcTree::fixTop ( )

After changing data in the top node, fix the heap.

◆ realpush()

void CbcTree::realpush ( CbcNode * node )

◆ cleanTree()

virtual void CbcTree::cleanTree	(	CbcModel *	model,
		double	cutoff,
		double &	bestPossibleObjective
	)

virtual

Prune the tree using an objective function cutoff.

This routine removes all nodes with objective worse than the specified cutoff value. It also sets bestPossibleObjective to the best objective over remaining nodes.

◆ bestAlternate()

CbcNode* CbcTree::bestAlternate ( )

Get best on list using alternate method.

◆ endSearch()

virtual void CbcTree::endSearch ( )

inlinevirtual

We may have got an intelligent tree so give it one more chance.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

Definition at line 135 of file CbcTree.hpp.

◆ getBestPossibleObjective()

virtual double CbcTree::getBestPossibleObjective ( )

virtual

Get best possible objective function in the tree.

◆ resetNodeNumbers()

void CbcTree::resetNodeNumbers ( )

inline

Reset maximum node number.

Definition at line 141 of file CbcTree.hpp.

◆ maximumNodeNumber()

int CbcTree::maximumNodeNumber ( ) const

inline

Get maximum node number.

Definition at line 144 of file CbcTree.hpp.

◆ setNumberBranching()

void CbcTree::setNumberBranching ( int value )

inline

Set number of branches.

Definition at line 147 of file CbcTree.hpp.

◆ getNumberBranching()

int CbcTree::getNumberBranching ( ) const

inline

Get number of branches.

Definition at line 150 of file CbcTree.hpp.

◆ setMaximumBranching()

void CbcTree::setMaximumBranching ( int value )

inline

Set maximum branches.

Definition at line 153 of file CbcTree.hpp.

◆ getMaximumBranching()

int CbcTree::getMaximumBranching ( ) const

inline

Get maximum branches.

Definition at line 156 of file CbcTree.hpp.

◆ branched()

unsigned int* CbcTree::branched ( ) const

inline

Get branched variables.

Definition at line 159 of file CbcTree.hpp.

◆ newBounds()

int* CbcTree::newBounds ( ) const

inline

Get bounds.

Definition at line 162 of file CbcTree.hpp.

◆ lastObjective()

double CbcTree::lastObjective ( ) const

inline

Last objective in branch-and-cut search tree.

Definition at line 165 of file CbcTree.hpp.

◆ lastDepth()

int CbcTree::lastDepth ( ) const

inline

Last depth in branch-and-cut search tree.

Definition at line 170 of file CbcTree.hpp.

◆ lastUnsatisfied()

int CbcTree::lastUnsatisfied ( ) const

inline

Last number of objects unsatisfied.

Definition at line 175 of file CbcTree.hpp.

◆ addBranchingInformation()

void CbcTree::addBranchingInformation	(	const CbcModel *	model,
		const CbcNodeInfo *	nodeInfo,
		const double *	currentLower,
		const double *	currentUpper
	)

Adds branching information to complete state.

◆ increaseSpace()

void CbcTree::increaseSpace ( )

Increase space for data.

Member Data Documentation

◆ nodes_

std::vector< CbcNode * > CbcTree::nodes_

protected

Storage vector for the heap.

Definition at line 197 of file CbcTree.hpp.

◆ comparison_

CbcCompare CbcTree::comparison_

protected

Sort predicate for heap ordering.

Definition at line 199 of file CbcTree.hpp.

◆ maximumNodeNumber_

int CbcTree::maximumNodeNumber_

protected

Maximum "node" number so far to split ties.

Definition at line 201 of file CbcTree.hpp.

◆ numberBranching_

int CbcTree::numberBranching_

protected

Size of variable list.

Definition at line 203 of file CbcTree.hpp.

◆ maximumBranching_

int CbcTree::maximumBranching_

protected

Maximum size of variable list.

Definition at line 205 of file CbcTree.hpp.

◆ lastObjective_

double CbcTree::lastObjective_

protected

Objective of last node pushed on tree.

Definition at line 207 of file CbcTree.hpp.

◆ lastDepth_

int CbcTree::lastDepth_

protected

Depth of last node pushed on tree.

Definition at line 209 of file CbcTree.hpp.

◆ lastUnsatisfied_

int CbcTree::lastUnsatisfied_

protected

Number unsatisfied of last node pushed on tree.

Definition at line 211 of file CbcTree.hpp.

◆ branched_

unsigned int* CbcTree::branched_

protected

Integer variables branched or bounded top bit set if new upper bound next bit set if a branch.

Definition at line 216 of file CbcTree.hpp.

◆ newBound_

int* CbcTree::newBound_

protected

New bound.

Definition at line 218 of file CbcTree.hpp.

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

/home/ted/Projects/Cbc/Cbc/src/CbcTree.hpp

Public Member Functions

Search tree maintenance

Detailed Description

Constructor & Destructor Documentation

◆ CbcTree() [1/2]

◆ CbcTree() [2/2]

◆ ~CbcTree()

Member Function Documentation

◆ operator=()

◆ clone()

◆ generateCpp()

◆ setComparison()

◆ top()

◆ push()

◆ pop()

◆ bestNode()

◆ rebuild()

◆ empty()

◆ size()

◆ operator[]()

◆ nodePointer()

◆ realpop()

◆ fixTop()

◆ realpush()

◆ cleanTree()

◆ bestAlternate()

◆ endSearch()

◆ getBestPossibleObjective()

◆ resetNodeNumbers()

◆ maximumNodeNumber()

◆ setNumberBranching()

◆ getNumberBranching()

◆ setMaximumBranching()

◆ getMaximumBranching()

◆ branched()

◆ newBounds()

◆ lastObjective()

◆ lastDepth()

◆ lastUnsatisfied()

◆ addBranchingInformation()

◆ increaseSpace()

Member Data Documentation

◆ nodes_

◆ comparison_

◆ maximumNodeNumber_

◆ numberBranching_

◆ maximumBranching_

◆ lastObjective_

◆ lastDepth_

◆ lastUnsatisfied_

◆ branched_

◆ newBound_