Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Protected Attributes | List of all members
CbcTree Class Reference

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...
 
CbcTreeoperator= (const CbcTree &rhs)
 = operator More...
 
virtual ~CbcTree ()
 Destructor. More...
 
virtual CbcTreeclone () 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 CbcNodetop () 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 CbcNodebestNode (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...
 
CbcNodeoperator[] (int i) const
 Return a node pointer. More...
 
CbcNodenodePointer (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
virtual void cleanTree (CbcModel *model, double cutoff, double &bestPossibleObjective)
 Prune the tree using an objective function cutoff. More...
 
CbcNodebestAlternate ()
 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...
 

Protected Attributes

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...
 

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 CbcTreeVariable, and CbcTreeLocal.

virtual void CbcTree::generateCpp ( FILE *  )
inlinevirtual

Create C++ lines to get to current state.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

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 CbcTreeVariable, and CbcTreeLocal.

virtual void CbcTree::push ( CbcNode x)
virtual

Add a node to the heap.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

virtual void CbcTree::pop ( )
virtual

Remove the top node from the heap.

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

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 CbcTreeVariable, and CbcTreeLocal.

virtual int CbcTree::size ( ) const
inlinevirtual

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.

void CbcTree::realpop ( )
void CbcTree::fixTop ( )

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

void CbcTree::realpush ( CbcNode node)
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 ( )
inlinevirtual

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

Reimplemented in CbcTreeVariable, and CbcTreeLocal.

Definition at line 136 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 142 of file CbcTree.hpp.

int CbcTree::maximumNodeNumber ( ) const
inline

Get maximum node number.

Definition at line 145 of file CbcTree.hpp.

void CbcTree::setNumberBranching ( int  value)
inline

Set number of branches.

Definition at line 148 of file CbcTree.hpp.

int CbcTree::getNumberBranching ( ) const
inline

Get number of branches.

Definition at line 151 of file CbcTree.hpp.

void CbcTree::setMaximumBranching ( int  value)
inline

Set maximum branches.

Definition at line 154 of file CbcTree.hpp.

int CbcTree::getMaximumBranching ( ) const
inline

Get maximum branches.

Definition at line 157 of file CbcTree.hpp.

unsigned int* CbcTree::branched ( ) const
inline

Get branched variables.

Definition at line 160 of file CbcTree.hpp.

int* CbcTree::newBounds ( ) const
inline

Get bounds.

Definition at line 163 of file CbcTree.hpp.

double CbcTree::lastObjective ( ) const
inline

Last objective in branch-and-cut search tree.

Definition at line 166 of file CbcTree.hpp.

int CbcTree::lastDepth ( ) const
inline

Last depth in branch-and-cut search tree.

Definition at line 170 of file CbcTree.hpp.

int CbcTree::lastUnsatisfied ( ) const
inline

Last number of objects unsatisfied.

Definition at line 174 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 195 of file CbcTree.hpp.

CbcCompare CbcTree::comparison_
protected

Sort predicate for heap ordering.

Definition at line 197 of file CbcTree.hpp.

int CbcTree::maximumNodeNumber_
protected

Maximum "node" number so far to split ties.

Definition at line 199 of file CbcTree.hpp.

int CbcTree::numberBranching_
protected

Size of variable list.

Definition at line 201 of file CbcTree.hpp.

int CbcTree::maximumBranching_
protected

Maximum size of variable list.

Definition at line 203 of file CbcTree.hpp.

double CbcTree::lastObjective_
protected

Objective of last node pushed on tree.

Definition at line 205 of file CbcTree.hpp.

int CbcTree::lastDepth_
protected

Depth of last node pushed on tree.

Definition at line 207 of file CbcTree.hpp.

int CbcTree::lastUnsatisfied_
protected

Number unsatisfied of last node pushed on tree.

Definition at line 209 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 214 of file CbcTree.hpp.

int* CbcTree::newBound_
protected

New bound.

Definition at line 216 of file CbcTree.hpp.


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