/home/coin/SVN-release/Blis-0.91.1/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 Common 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-2009, 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 & depth);            /* Output */
00247     
00253     AlpsReturnStatus exploreUnitWork(bool leaveAsIt,
00254                                      int unitWork,
00255                                      double unitTime,
00256                                      AlpsExitStatus & solStatus,/*not for parallel*/
00257                                      int & numNodesProcessed, /* Output */
00258                                      int & numNodesBranched,  /* Output */
00259                                      int & numNodesDiscarded, /* Output */
00260                                      int & depth,             /* Output */
00261                                      bool & betterSolution);  /* Output */
00262     
00265     virtual int rampUp(int minNumNodes,
00266                        int requiredNumNodes,
00267                        int& depth,
00268                        AlpsTreeNode* root = NULL);
00269 
00270     using  AlpsKnowledge::encode ;
00273     virtual AlpsEncoded* encode() const;
00274     
00279     virtual AlpsKnowledge* decode(AlpsEncoded& encoded) const;
00280 
00283     virtual AlpsSubTree* newSubTree() const {
00284         return new AlpsSubTree;
00285     }
00286 
00288     void clearNodePools() {
00289         if (nodePool_) {
00290             nodePool_->clear();
00291         }
00292         if (diveNodePool_) {
00293             diveNodePool_->clear();
00294         }
00295     }
00296 
00298     void nullRootActiveNode() {
00299         root_ = NULL;
00300         activeNode_ = NULL;
00301     }
00302 
00304     void reset() {
00305         // Move nodes in diving pool to normal pool.
00306         AlpsTreeNode *tempNode = NULL;
00307         while (diveNodePool_->getNumKnowledges() > 0) {
00308             tempNode = dynamic_cast<AlpsTreeNode *>
00309                 (diveNodePool_->getKnowledge().first);
00310             diveNodePool_->popKnowledge();
00311             nodePool_->addKnowledge(tempNode, tempNode->getQuality());
00312         }
00313         if (activeNode_) {   
00314             nodePool_->addKnowledge(activeNode_, activeNode_->getQuality());
00315             activeNode_ = NULL;
00316         }
00317 
00318         diveDepth_ = 0;
00319     }
00320     
00321 };
00322 #endif
00323 
00324 //#############################################################################
00325 // The way to create children:
00326 //-----------------------------------------------------------------------------
00327 // In AlpsSubTree::exploreSubTree(root)
00328 // If (pregnant) 
00329 // => KnapTreeNode::branch() 
00330 // => AlpsSubTree::createChildren(...)  {
00331 //   AlpsTreeNode::setNumChildren(...) (allocate memory if not);
00332 //   KnapTreeNode:: createNewTreeNode(...); 
00333 //   AlpsSubTree::setChildren;
00334 //   AlspSubTree::setStatus }
00335 //#############################################################################
00336 
00337 //#############################################################################
00338 // The way to remove nodes:
00339 //-----------------------------------------------------------------------------
00340 // In AlpsSubTree::exploreSubTree(root)
00341 // If (fathomed)
00342 // => AlpsSubTree::removeDeadNode(node) {
00343 //      AlpsTreeNode::removeChild(node) {
00344 //        AlpsTreeNode::removeDescendants();
00345 //      }
00346 //    Check whether parent has children; 
00347 //      if (yes), recursively removeDeadNode(parent) 
00348 //#############################################################################

Generated on Thu Oct 8 03:19:44 2009 by  doxygen 1.4.7