- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

# /home/coin/svn-release/Bcps-0.93.10/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 //#############################################################################