00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef AlpsSubTree_h_
00024 #define AlpsSubTree_h_
00025
00026 #include <cassert>
00027 #include <list>
00028
00029 #include "CoinError.hpp"
00030 #include "CoinSort.hpp"
00031
00032 #include "AlpsSearchStrategy.h"
00033 #include "AlpsKnowledge.h"
00034 #include "AlpsNodePool.h"
00035 #include "AlpsPriorityQueue.h"
00036 #include "AlpsTreeNode.h"
00037
00038 class AlpsKnowledgeBroker;
00039
00040
00041
00047 class AlpsSubTree : public AlpsKnowledge {
00048
00049 protected:
00050
00052 AlpsTreeNode* root_;
00053
00055 AlpsNodePool* nodePool_;
00056
00058 AlpsNodePool* diveNodePool_;
00059
00061 AlpsSearchStrategy<AlpsTreeNode*> * diveNodeRule_;
00062
00064 int diveDepth_;
00065
00066
00067
00068
00071 AlpsTreeNode* activeNode_;
00072
00074 double quality_;
00075
00078
00079 AlpsKnowledgeBroker* broker_;
00080
00081 protected:
00082
00089 void removeDeadNodes(AlpsTreeNode*& node);
00090
00092 void replaceNode(AlpsTreeNode* oldNode, AlpsTreeNode* newNode);
00093
00094 public:
00095
00097 AlpsSubTree();
00098
00100 AlpsSubTree(AlpsKnowledgeBroker* kb);
00101
00103 virtual ~AlpsSubTree();
00104
00105 public:
00106
00108 inline AlpsTreeNode* activeNode() { return activeNode_; }
00109
00111 inline void setActiveNode(AlpsTreeNode *activeNode)
00112 { activeNode_ = activeNode; }
00113
00115 void createChildren(AlpsTreeNode* parent,
00116 std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus,
00117 double> >& children,
00118 AlpsNodePool *kidNodePool = NULL);
00119
00124 inline AlpsTreeNode* getRoot() const { return root_; }
00125
00127 inline void setRoot(AlpsTreeNode* r) { root_ = r; }
00128
00130 inline AlpsNodePool* nodePool() { return nodePool_; }
00131
00133 inline AlpsNodePool* diveNodePool() { return diveNodePool_; }
00134
00136 inline void setNodePool(AlpsNodePool* np) {
00137 if (nodePool_ != NULL) {
00138 delete nodePool_;
00139 nodePool_ = NULL;
00140 }
00141 nodePool_ = np;
00142 }
00143
00145 inline void changeNodePool(AlpsNodePool* np) {
00146 if (nodePool_ != NULL) {
00147
00148 nodePool_->clear();
00149
00150 assert(nodePool_->hasKnowledge() == false);
00151 delete nodePool_;
00152 nodePool_ = NULL;
00153 }
00154 nodePool_ = np;
00155 }
00156
00158 double getBestKnowledgeValue() const;
00159
00161 AlpsTreeNode *getBestNode() const;
00162
00164 inline AlpsKnowledgeBroker* getKnowledgeBroker() const { return broker_; }
00165
00167 inline void setKnowledgeBroker(AlpsKnowledgeBroker* kb) {
00168 assert(kb);
00169 broker_ = kb;
00170 }
00171
00173 inline double getQuality() const { return quality_; }
00174
00176 inline double getSolEstimate() const {
00177 if (root_) {
00178 return root_->getSolEstimate();
00179 }
00180 else {
00181 return ALPS_OBJ_MAX;
00182 };
00183 }
00184
00186 void incDiveDepth(int num=1) { diveDepth_ += num; }
00187
00189 int getDiveDepth() { return diveDepth_; }
00190
00192 void setDiveDepth(int num) { diveDepth_ = num; }
00193
00196 double calculateQuality();
00197
00198
00199
00200 int nextIndex();
00201
00203 int getNextIndex() const;
00204
00206 void setNextIndex(int next);
00207
00209 int getNumNodes() const {
00210 assert(nodePool_ && diveNodePool_);
00211 int nn = 0;
00212 if (activeNode_) {
00213 if ( (activeNode_->getStatus() != AlpsNodeStatusFathomed) &&
00214 (activeNode_->getStatus() != AlpsNodeStatusBranched) ) {
00215 ++nn;
00216 }
00217 }
00218 return (nn + nodePool_->getNumKnowledges() +
00219 diveNodePool_->getNumKnowledges());
00220 }
00221
00223 void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
00224 nodePool_->setNodeSelection(*nc);
00225 }
00227
00230 AlpsSubTree* splitSubTree(int& returnSize, int size = 10);
00231
00235 virtual AlpsReturnStatus exploreSubTree(AlpsTreeNode* root,
00236 int nodeLimit,
00237 double timeLimit,
00238 int & numNodesProcesse,
00239 int & depth);
00240
00246 AlpsReturnStatus exploreUnitWork(bool leaveAsIt,
00247 int unitWork,
00248 double unitTime,
00249 AlpsExitStatus & solStatus,
00250 int & numNodesProcessed,
00251 int & depth,
00252 bool & betterSolution);
00253
00256 virtual int rampUp(int minNumNodes,
00257 int requiredNumNodes,
00258 int& depth,
00259 AlpsTreeNode* root = NULL);
00260
00261 using AlpsKnowledge::encode ;
00264 virtual AlpsEncoded* encode() const;
00265
00270 virtual AlpsKnowledge* decode(AlpsEncoded& encoded) const;
00271
00274 virtual AlpsSubTree* newSubTree() const {
00275 return new AlpsSubTree;
00276 }
00277
00279 void clearNodePools() {
00280 if (nodePool_) {
00281 nodePool_->clear();
00282 }
00283 if (diveNodePool_) {
00284 diveNodePool_->clear();
00285 }
00286 }
00287
00289 void nullRootActiveNode() {
00290 root_ = NULL;
00291 activeNode_ = NULL;
00292 }
00293
00295 void reset() {
00296
00297 AlpsTreeNode *tempNode = NULL;
00298 while (diveNodePool_->getNumKnowledges() > 0) {
00299 tempNode = dynamic_cast<AlpsTreeNode *>
00300 (diveNodePool_->getKnowledge().first);
00301 diveNodePool_->popKnowledge();
00302 nodePool_->addKnowledge(tempNode, tempNode->getQuality());
00303 }
00304 if (activeNode_) {
00305 nodePool_->addKnowledge(activeNode_, activeNode_->getQuality());
00306 activeNode_ = NULL;
00307 }
00308
00309 diveDepth_ = 0;
00310 }
00311
00312 };
00313 #endif
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339