Cbc trunk
Protected Attributes
CbcTree Class Reference

Using MS heap implementation. More...

#include <CbcTree.hpp>

Inheritance diagram for CbcTree:
Collaboration diagram for CbcTree:

List of all members.

Public Member Functions

Constructors and related
 CbcTree ()
 Default Constructor.
 CbcTree (const CbcTree &rhs)
 Copy constructor.
CbcTreeoperator= (const CbcTree &rhs)
 = operator
virtual ~CbcTree ()
 Destructor.
virtual CbcTreeclone () const
 Clone.
virtual void generateCpp (FILE *)
 Create C++ lines to get to current state.
Heap access and maintenance methods
void setComparison (CbcCompareBase &compare)
 Set comparison function and resort heap.
virtual CbcNodetop () const
 Return the top node of the heap.
virtual void push (CbcNode *x)
 Add a node to the heap.
virtual void pop ()
 Remove the top node from the heap.
virtual CbcNodebestNode (double cutoff)
 Gets best node and takes off heap.
virtual void rebuild ()
 Rebuild the heap.
Direct node access methods
virtual bool empty ()
 Test for an empty tree.
virtual int size () const
 Return size.
CbcNodeoperator[] (int i) const
 Return a node pointer.
CbcNodenodePointer (int i) const
 Return a node pointer.
Search tree maintenance
virtual void cleanTree (CbcModel *model, double cutoff, double &bestPossibleObjective)
 Prune the tree using an objective function cutoff.
CbcNodebestAlternate ()
 Get best on list using alternate method.
virtual void endSearch ()
 We may have got an intelligent tree so give it one more chance.
virtual double getBestPossibleObjective ()
 Get best possible objective function in the tree.
void resetNodeNumbers ()
 Reset maximum node number.
int maximumNodeNumber () const
 Get maximum node number.
void setNumberBranching (int value)
 Set number of branches.
int getNumberBranching () const
 Get number of branches.
void setMaximumBranching (int value)
 Set maximum branches.
int getMaximumBranching () const
 Get maximum branches.
unsigned int * branched () const
 Get branched variables.
int * newBounds () const
 Get bounds.
void addBranchingInformation (const CbcModel *model, const CbcNodeInfo *nodeInfo, const double *currentLower, const double *currentUpper)
 Adds branching information to complete state.
void increaseSpace ()
 Increase space for data.

Protected Attributes

std::vector< CbcNode * > nodes_
 Storage vector for the heap.
CbcCompare comparison_
 Sort predicate for heap ordering.
int maximumNodeNumber_
 Maximum "node" number so far to split ties.
int numberBranching_
 Size of variable list.
int maximumBranching_
 Maximum size of variable list.
unsigned int * branched_
 Integer variables branched or bounded top bit set if new upper bound next bit set if a branch.
int * newBound_
 New bound.

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.

#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 53 of file CbcTree.hpp.


Constructor & Destructor Documentation

CbcTree::CbcTree ( )

Default Constructor.

CbcTree::CbcTree ( const CbcTree rhs)

Copy constructor.

virtual CbcTree::~CbcTree ( ) [virtual]

Destructor.


Member Function Documentation

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

= operator

virtual CbcTree* CbcTree::clone ( ) const [virtual]

Clone.

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

virtual void CbcTree::generateCpp ( FILE *  ) [inline, virtual]

Create C++ lines to get to current state.

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

Definition at line 74 of file CbcTree.hpp.

void CbcTree::setComparison ( CbcCompareBase compare)

Set comparison function and resort heap.

virtual CbcNode* CbcTree::top ( ) const [virtual]

Return the top node of the heap.

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

virtual void CbcTree::push ( CbcNode x) [virtual]

Add a node to the heap.

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

virtual void CbcTree::pop ( ) [virtual]

Remove the top node from the heap.

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

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.

virtual void CbcTree::rebuild ( ) [virtual]

Rebuild the heap.

virtual bool CbcTree::empty ( ) [virtual]

Test for an empty tree.

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

virtual int CbcTree::size ( ) const [inline, virtual]

Return size.

Definition at line 109 of file CbcTree.hpp.

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

Return a node pointer.

Definition at line 112 of file CbcTree.hpp.

CbcNode* CbcTree::nodePointer ( int  i) const [inline]

Return a node pointer.

Definition at line 115 of file CbcTree.hpp.

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.

CbcNode* CbcTree::bestAlternate ( )

Get best on list using alternate method.

virtual void CbcTree::endSearch ( ) [inline, virtual]

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

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

Definition at line 132 of file CbcTree.hpp.

virtual double CbcTree::getBestPossibleObjective ( ) [virtual]

Get best possible objective function in the tree.

void CbcTree::resetNodeNumbers ( ) [inline]

Reset maximum node number.

Definition at line 138 of file CbcTree.hpp.

int CbcTree::maximumNodeNumber ( ) const [inline]

Get maximum node number.

Definition at line 141 of file CbcTree.hpp.

void CbcTree::setNumberBranching ( int  value) [inline]

Set number of branches.

Definition at line 144 of file CbcTree.hpp.

int CbcTree::getNumberBranching ( ) const [inline]

Get number of branches.

Definition at line 147 of file CbcTree.hpp.

void CbcTree::setMaximumBranching ( int  value) [inline]

Set maximum branches.

Definition at line 150 of file CbcTree.hpp.

int CbcTree::getMaximumBranching ( ) const [inline]

Get maximum branches.

Definition at line 153 of file CbcTree.hpp.

unsigned int* CbcTree::branched ( ) const [inline]

Get branched variables.

Definition at line 156 of file CbcTree.hpp.

int* CbcTree::newBounds ( ) const [inline]

Get bounds.

Definition at line 159 of file CbcTree.hpp.

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

Adds branching information to complete state.

void CbcTree::increaseSpace ( )

Increase space for data.


Member Data Documentation

std::vector<CbcNode *> CbcTree::nodes_ [protected]

Storage vector for the heap.

Definition at line 179 of file CbcTree.hpp.

Sort predicate for heap ordering.

Definition at line 181 of file CbcTree.hpp.

int CbcTree::maximumNodeNumber_ [protected]

Maximum "node" number so far to split ties.

Definition at line 183 of file CbcTree.hpp.

int CbcTree::numberBranching_ [protected]

Size of variable list.

Definition at line 185 of file CbcTree.hpp.

int CbcTree::maximumBranching_ [protected]

Maximum size of variable list.

Definition at line 187 of file CbcTree.hpp.

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 192 of file CbcTree.hpp.

int* CbcTree::newBound_ [protected]

New bound.

Definition at line 194 of file CbcTree.hpp.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines