# CbcTree Class Reference

Using MS heap implementation. More...

`#include <CbcTree.hpp>`

Inheritance diagram for CbcTree:
[legend]
Collaboration diagram for CbcTree:
[legend]

List of all members.

## Public Member Functions
Constructors and related
| CbcTree ()
| Default Constructor.
| CbcTree (const CbcTree &rhs)
| Copy constructor.
CbcTree & | operator= (const CbcTree &rhs)
| = operator
virtual | ~CbcTree ()
| Destructor.
virtual CbcTree * | clone () 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 CbcNode * | top () 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 CbcNode * | bestNode (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.
CbcNode * | operator[] (int i) const
| Return a node pointer.
CbcNode * | nodePointer (int i) const
| Return a node pointer.
void | realpop ()
void | fixTop ()
| After changing data in the top node, fix the heap.
void | realpush (CbcNode *node)
Search tree maintenance
virtual void | cleanTree (CbcModel *model, double cutoff, double &bestPossibleObjective)
| Prune the tree using an objective function cutoff.
CbcNode * | bestAlternate ()
| 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.

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

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

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.

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 | ( |  | ) | `[inline, virtual]`

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

Reimplemented in CbcTreeLocal, and CbcTreeVariable.

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.

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

CbcCompare CbcTree::comparison_`[protected]`

Sort predicate for heap ordering.

Definition at line 185 of file CbcTree.hpp.

int CbcTree::maximumNodeNumber_`[protected]`

Maximum "node" number so far to split ties.

Definition at line 187 of file CbcTree.hpp.

int CbcTree::numberBranching_`[protected]`

Size of variable list.

Definition at line 189 of file CbcTree.hpp.

int CbcTree::maximumBranching_`[protected]`

Maximum size of variable list.

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

int* CbcTree::newBound_`[protected]`

New bound.

Definition at line 198 of file CbcTree.hpp.

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

- /home/coin/svn-release/Cbc-2.8.1/Cbc/src/CbcTree.hpp

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines