/usr/src/RPM/BUILD/CoinAlps-1.4.4/Alps/src/AlpsSubTree.h
Go to the documentation of this file.
00001 /*===========================================================================*
00002  * This file is part of the Abstract Library for Parallel Search (ALPS).     *
00003  *                                                                           *
00004  * ALPS is distributed under the Eclipse Public License as part of the       *
00005  * COIN-OR repository (http://www.coin-or.org).                              *
00006  *                                                                           *
00007  * Authors:                                                                  *
00008  *                                                                           *
00009  *          Yan Xu, Lehigh University                                        *
00010  *          Ted Ralphs, Lehigh University                                    *
00011  *                                                                           *
00012  * Conceptual Design:                                                        *
00013  *                                                                           *
00014  *          Yan Xu, Lehigh University                                        *
00015  *          Ted Ralphs, Lehigh University                                    *
00016  *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
00017  *          Matthew Saltzman, Clemson University                             *
00018  *                                                                           * 
00019  *                                                                           *
00020  * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs.       *
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     //   /** The next index to be assigned to a new search tree node */
00067     //   AlpsNodeIndex_t nextIndex_;
00068 
00071     AlpsTreeNode* activeNode_;
00072 
00074     double quality_;
00075 
00078     // Need broker to query model && parameters.
00079     AlpsKnowledgeBroker*  broker_;
00080     
00081  protected:
00082 
00089     void removeDeadNodes(AlpsTreeNode*& node);
00090 
00092     void replaceNode(AlpsTreeNode* oldNode, AlpsTreeNode* newNode);
00093 
00097     void fathomAllNodes();
00098 
00099  public:
00100     
00102     AlpsSubTree();
00103     
00105     AlpsSubTree(AlpsKnowledgeBroker* kb);
00106         
00108     virtual ~AlpsSubTree();
00109 
00110  public:
00111 
00113     inline AlpsTreeNode* activeNode() { return activeNode_; }
00114 
00116     inline void setActiveNode(AlpsTreeNode *activeNode)
00117     { activeNode_ = activeNode; }
00118 
00120     void createChildren(AlpsTreeNode* parent,
00121                         std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus, 
00122                         double> >& children,
00123                         AlpsNodePool *kidNodePool = NULL);
00124     
00129     inline AlpsTreeNode* getRoot() const { return root_; }
00130 
00132     inline void setRoot(AlpsTreeNode* r) { root_ = r; }
00133 
00135     inline AlpsNodePool* nodePool() { return nodePool_; }
00136 
00138     inline AlpsNodePool* diveNodePool() { return diveNodePool_; }
00139 
00141     inline void setNodePool(AlpsNodePool* np) { 
00142         if (nodePool_ != NULL) {
00143             delete nodePool_; 
00144             nodePool_ = NULL;
00145         }
00146         nodePool_ = np;
00147     }
00148 
00150     inline void changeNodePool(AlpsNodePool* np) { 
00151         if (nodePool_ != NULL) {
00152             // Remove all elements first.
00153             nodePool_->clear();
00154             // Delete an empty pool.
00155             assert(nodePool_->hasKnowledge() == false);
00156             delete nodePool_;
00157             nodePool_ = NULL;
00158         }
00159         nodePool_ = np;
00160     }
00161 
00163     double getBestKnowledgeValue() const;
00164 
00166     AlpsTreeNode *getBestNode() const;
00167 
00169     inline AlpsKnowledgeBroker*  getKnowledgeBroker() const { return broker_; }
00170     
00172     inline void setKnowledgeBroker(AlpsKnowledgeBroker* kb) {
00173         assert(kb);
00174         broker_ = kb;
00175     }
00176     
00178     inline double getQuality() const { return quality_; }
00179 
00181     inline double getSolEstimate() const { 
00182         if (root_) {
00183             return root_->getSolEstimate();
00184         }
00185         else {
00186             return ALPS_OBJ_MAX;
00187         };
00188     }
00189 
00191     void incDiveDepth(int num=1) {  diveDepth_ += num; }
00192 
00194     int getDiveDepth() { return diveDepth_; }
00195 
00197     void setDiveDepth(int num) { diveDepth_ = num; }
00198     
00201     double calculateQuality();
00202  
00203     /* Get the index of the next generated node and increment next index
00204        by one.*/ 
00205     int nextIndex();
00206 
00208     int getNextIndex() const;
00209     
00211     void setNextIndex(int next);
00212 
00214     int getNumNodes() const {
00215         assert(nodePool_ && diveNodePool_);
00216         int nn = 0;
00217         if (activeNode_) {
00218             if ( (activeNode_->getStatus() != AlpsNodeStatusFathomed) &&
00219                  (activeNode_->getStatus() != AlpsNodeStatusBranched) ) {
00220                 ++nn;
00221             }
00222         }
00223         return (nn + nodePool_->getNumKnowledges() + 
00224                 diveNodePool_->getNumKnowledges());
00225     }
00226 
00228     void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
00229         nodePool_->setNodeSelection(*nc);
00230     }
00232 
00235     AlpsSubTree* splitSubTree(int& returnSize, int size = 10);
00236     
00240     virtual AlpsReturnStatus exploreSubTree(AlpsTreeNode* root,
00241                                             int nodeLimit,  
00242                                             double timeLimit,
00243                                             int & numNodesProcessed, /* Output */
00244                                             int & numNodesBranched,  /* Output */
00245                                             int & numNodesDiscarded, /* Output */
00246                                             int & numNodesPartial,  /* Output */
00247                                             int & depth);            /* Output */
00248     
00254     AlpsReturnStatus exploreUnitWork(bool leaveAsIt,
00255                                      int unitWork,
00256                                      double unitTime,
00257                                      AlpsExitStatus & solStatus,/*not for parallel*/
00258                                      int & numNodesProcessed, /* Output */
00259                                      int & numNodesBranched,  /* Output */
00260                                      int & numNodesDiscarded, /* Output */
00261                                      int & numNodesPartial,  /* Output */
00262                                      int & depth,             /* Output */
00263                                      bool & betterSolution);  /* Output */
00264     
00267     virtual int rampUp(int minNumNodes,
00268                        int requiredNumNodes,
00269                        int& depth,
00270                        AlpsTreeNode* root = NULL);
00271 
00272     using  AlpsKnowledge::encode ;
00275     virtual AlpsEncoded* encode() const;
00276     
00281     virtual AlpsKnowledge* decode(AlpsEncoded& encoded) const;
00282 
00285     virtual AlpsSubTree* newSubTree() const {
00286         return new AlpsSubTree;
00287     }
00288 
00290     void clearNodePools() {
00291         if (nodePool_) {
00292             nodePool_->clear();
00293         }
00294         if (diveNodePool_) {
00295             diveNodePool_->clear();
00296         }
00297     }
00298 
00300     void nullRootActiveNode() {
00301         root_ = NULL;
00302         activeNode_ = NULL;
00303     }
00304 
00306     void reset() {
00307         // Move nodes in diving pool to normal pool.
00308         AlpsTreeNode *tempNode = NULL;
00309         while (diveNodePool_->getNumKnowledges() > 0) {
00310             tempNode = dynamic_cast<AlpsTreeNode *>
00311                 (diveNodePool_->getKnowledge().first);
00312             diveNodePool_->popKnowledge();
00313             nodePool_->addKnowledge(tempNode, tempNode->getQuality());
00314         }
00315         if (activeNode_) {   
00316             nodePool_->addKnowledge(activeNode_, activeNode_->getQuality());
00317             activeNode_ = NULL;
00318         }
00319 
00320         diveDepth_ = 0;
00321     }
00322     
00323 };
00324 #endif
00325 
00326 //#############################################################################
00327 // The way to create children:
00328 //-----------------------------------------------------------------------------
00329 // In AlpsSubTree::exploreSubTree(root)
00330 // If (pregnant) 
00331 // => KnapTreeNode::branch() 
00332 // => AlpsSubTree::createChildren(...)  {
00333 //   AlpsTreeNode::setNumChildren(...) (allocate memory if not);
00334 //   KnapTreeNode:: createNewTreeNode(...); 
00335 //   AlpsSubTree::setChildren;
00336 //   AlspSubTree::setStatus }
00337 //#############################################################################
00338 
00339 //#############################################################################
00340 // The way to remove nodes:
00341 //-----------------------------------------------------------------------------
00342 // In AlpsSubTree::exploreSubTree(root)
00343 // If (fathomed)
00344 // => AlpsSubTree::removeDeadNode(node) {
00345 //      AlpsTreeNode::removeChild(node) {
00346 //        AlpsTreeNode::removeDescendants();
00347 //      }
00348 //    Check whether parent has children; 
00349 //      if (yes), recursively removeDeadNode(parent) 
00350 //#############################################################################