Public Member Functions | |
| tree () | |
| > Sort function for heap ordering. | |
Heap access and maintenance methods | |
| void | setComparison (SbbCompareBase &compare) |
| Set comparison function and resort heap. | |
| SbbNode * | top () |
| Return the top node of the heap. | |
| void | push (SbbNode *x) |
| Add a node to the heap. | |
| void | pop () |
| Remove the top node from the heap. | |
Search tree maintenance | |
| void | cleanTree (SbbModel *model, double cutoff) |
| Prune the tree using an objective function cutoff. | |
Private Attributes | |
| SbbCompare | comparison_ |
This class is used to hold the set of live nodes in the search tree.
Definition at line 53 of file SbbModel.cpp.
|
||||||||||||
|
Prune the tree using an objective function cutoff. This routine removes all nodes with objective worst than the specified cutoff value. Definition at line 96 of file SbbModel.cpp. References SbbModel::addCuts1(), SbbModel::addedCuts(), SbbModel::currentNumberCuts(), SbbCountRowCut::decrement(), SbbNode::depth(), CoinWarmStartBasis::getArtifStatus(), SbbModel::getEmptyBasis(), SbbNode::nodeInfo(), SbbNodeInfo::numberBranchesLeft(), SbbModel::numberRowsAtContinuous(), SbbNode::objectiveValue(), pop(), push(), SbbNodeInfo::throwAway(), and top(). Referenced by SbbModel::branchAndBound().
00097 {
00098 int j;
00099 int nNodes = size();
00100 SbbNode ** nodeArray = new SbbNode * [nNodes];
00101 int * depth = new int [nNodes];
00102 int k=0;
00103 int kDelete=nNodes;
00104 /*
00105 Destructively scan the heap. Nodes to be retained go into the front of
00106 nodeArray, nodes to be deleted into the back. Store the depth in a
00107 correlated array for nodes to be deleted.
00108 */
00109 for (j=0;j<nNodes;j++) {
00110 SbbNode * node = top();
00111 pop();
00112 if (node->objectiveValue() >= cutoff) {
00113 nodeArray[--kDelete] = node;
00114 depth[kDelete] = node->depth();
00115 } else {
00116 nodeArray[k++]=node;
00117 }
00118 }
00119 /*
00120 Rebuild the heap using the retained nodes.
00121 */
00122 for (j=0;j<k;j++) { push(nodeArray[j]); }
00123 /*
00124 Sort the list of nodes to be deleted, nondecreasing.
00125 */
00126 CoinSort_2(depth+kDelete,depth+nNodes,nodeArray+kDelete);
00127 /*
00128 Work back from deepest to shallowest. In spite of the name, addCuts1 is
00129 just a preparatory step. When it returns, the following will be true:
00130 * all cuts are removed from the solver's copy of the constraint system;
00131 * lastws will be a basis appropriate for the specified node;
00132 * variable bounds will be adjusted to be appropriate for the specified
00133 node;
00134 * addedCuts_ (returned via addedCuts()) will contain a list of cuts that
00135 should be added to the constraint system at this node (but they have
00136 not actually been added).
00137 Then we scan the cut list for the node. Decrement the reference count
00138 for the cut, and if it's gone to 0, really delete it.
00139
00140 I don't yet see why the checks for status != basic and addedCuts_[i] != 0
00141 are necessary. When reconstructing a node, these checks are used to skip
00142 over loose cuts, excluding them from the reconstituted basis. But here
00143 we're just interested in correcting the reference count. Tight/loose should
00144 make no difference.
00145
00146 Arguably a separate routine should be used in place of addCuts1. It's doing
00147 more work than needed, modifying the model to match a subproblem at a node
00148 that will be discarded. Then again, we seem to need the basis.
00149 */
00150 for (j=nNodes-1;j >= kDelete;j--) {
00151 SbbNode * node = nodeArray[j];
00152 CoinWarmStartBasis *lastws = model->getEmptyBasis() ;
00153
00154 model->addCuts1(node,lastws);
00155 // Decrement cut counts
00156 int numberLeft = node->nodeInfo()->numberBranchesLeft();
00157 int i;
00158 for (i=0;i<model->currentNumberCuts();i++) {
00159 // take off node
00160 CoinWarmStartBasis::Status status =
00161 lastws->getArtifStatus(i+model->numberRowsAtContinuous());
00162 if (status != CoinWarmStartBasis::basic&&
00163 model->addedCuts()[i]) {
00164 if (!model->addedCuts()[i]->decrement(numberLeft))
00165 delete model->addedCuts()[i];
00166 }
00167 }
00168 // node should not have anything pointing to it
00169 node->nodeInfo()->throwAway();
00170 delete node ;
00171 delete lastws ;
00172 }
00173 delete [] nodeArray;
00174 delete [] depth;
00175 };
|
1.3.5