AlpsSubTree.h

Go to the documentation of this file.

/*===========================================================================*
 * This file is part of the Abstract Library for Parallel Search (ALPS).     *
 *                                                                           *
 * ALPS is distributed under the Eclipse Public License as part of the       *
 * COIN-OR repository (http://www.coin-or.org).                              *
 *                                                                           *
 * Authors:                                                                  *
 *                                                                           *
 *          Yan Xu, Lehigh University                                        *
 *          Ted Ralphs, Lehigh University                                    *
 *                                                                           *
 * Conceptual Design:                                                        *
 *                                                                           *
 *          Yan Xu, Lehigh University                                        *
 *          Ted Ralphs, Lehigh University                                    *
 *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
 *          Matthew Saltzman, Clemson University                             *
 *                                                                           * 
 *                                                                           *
 * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs.       *
 *===========================================================================*/

#ifndef AlpsSubTree_h_
#define AlpsSubTree_h_

#include <cassert>
#include <list>

#include "CoinError.hpp"
#include "CoinSort.hpp"

#include "AlpsSearchStrategy.h"
#include "AlpsKnowledge.h"
#include "AlpsNodePool.h"
#include "AlpsPriorityQueue.h"
#include "AlpsTreeNode.h"

class AlpsKnowledgeBroker;

//#############################################################################

class AlpsSubTree : public AlpsKnowledge {

 protected:

    AlpsTreeNode* root_;
   
    AlpsNodePool* nodePool_;

    AlpsNodePool* diveNodePool_;
    
    AlpsSearchStrategy<AlpsTreeNode*> * diveNodeRule_;

    int diveDepth_;
    
    //   /** The next index to be assigned to a new search tree node */
    //   AlpsNodeIndex_t nextIndex_;

    AlpsTreeNode* activeNode_;

    double quality_;

    // Need broker to query model && parameters.
    AlpsKnowledgeBroker*  broker_;
    
 protected:

    void removeDeadNodes(AlpsTreeNode*& node);

    void replaceNode(AlpsTreeNode* oldNode, AlpsTreeNode* newNode);

    void fathomAllNodes();

 public:
    
    AlpsSubTree();
    
    AlpsSubTree(AlpsKnowledgeBroker* kb);
        
    virtual ~AlpsSubTree();

 public:

    inline AlpsTreeNode* activeNode() { return activeNode_; }

    inline void setActiveNode(AlpsTreeNode *activeNode)
    { activeNode_ = activeNode; }

    void createChildren(AlpsTreeNode* parent,
                        std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus, 
                        double> >& children,
                        AlpsNodePool *kidNodePool = NULL);
    
    inline AlpsTreeNode* getRoot() const { return root_; }

    inline void setRoot(AlpsTreeNode* r) { root_ = r; }

    inline AlpsNodePool* nodePool() { return nodePool_; }

    inline AlpsNodePool* diveNodePool() { return diveNodePool_; }

    inline void setNodePool(AlpsNodePool* np) { 
        if (nodePool_ != NULL) {
            delete nodePool_; 
            nodePool_ = NULL;
        }
        nodePool_ = np;
    }

    inline void changeNodePool(AlpsNodePool* np) { 
        if (nodePool_ != NULL) {
            // Remove all elements first.
            nodePool_->clear();
            // Delete an empty pool.
            assert(nodePool_->hasKnowledge() == false);
            delete nodePool_;
            nodePool_ = NULL;
        }
        nodePool_ = np;
    }

    double getBestKnowledgeValue() const;

    AlpsTreeNode *getBestNode() const;

    inline AlpsKnowledgeBroker*  getKnowledgeBroker() const { return broker_; }
    
    inline void setKnowledgeBroker(AlpsKnowledgeBroker* kb) {
        assert(kb);
        broker_ = kb;
    }
    
    inline double getQuality() const { return quality_; }

    inline double getSolEstimate() const { 
        if (root_) {
            return root_->getSolEstimate();
        }
        else {
            return ALPS_OBJ_MAX;
        };
    }

    void incDiveDepth(int num=1) {  diveDepth_ += num; }

    int getDiveDepth() { return diveDepth_; }

    void setDiveDepth(int num) { diveDepth_ = num; }
    
    double calculateQuality();
 
    /* Get the index of the next generated node and increment next index
       by one.*/ 
    int nextIndex();

    int getNextIndex() const;
    
    void setNextIndex(int next);

    int getNumNodes() const {
        assert(nodePool_ && diveNodePool_);
        int nn = 0;
        if (activeNode_) {
            if ( (activeNode_->getStatus() != AlpsNodeStatusFathomed) &&
                 (activeNode_->getStatus() != AlpsNodeStatusBranched) ) {
                ++nn;
            }
        }
        return (nn + nodePool_->getNumKnowledges() + 
                diveNodePool_->getNumKnowledges());
    }

    void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
        nodePool_->setNodeSelection(*nc);
    }

    AlpsSubTree* splitSubTree(int& returnSize, int size = 10);
    
    virtual AlpsReturnStatus exploreSubTree(AlpsTreeNode* root,
                                            int nodeLimit,  
                                            double timeLimit,
                                            int & numNodesProcessed, /* Output */
                                            int & numNodesBranched,  /* Output */
                                            int & numNodesDiscarded, /* Output */
                                            int & numNodesPartial,  /* Output */
                                            int & depth);            /* Output */
    
    AlpsReturnStatus exploreUnitWork(bool leaveAsIt,
                                     int unitWork,
                                     double unitTime,
                                     AlpsExitStatus & solStatus,/*not for parallel*/
                                     int & numNodesProcessed, /* Output */
                                     int & numNodesBranched,  /* Output */
                                     int & numNodesDiscarded, /* Output */
                                     int & numNodesPartial,  /* Output */
                                     int & depth,             /* Output */
                                     bool & betterSolution);  /* Output */
    
    virtual int rampUp(int minNumNodes,
                       int requiredNumNodes,
                       int& depth,
                       AlpsTreeNode* root = NULL);

    using  AlpsKnowledge::encode ;
    virtual AlpsEncoded* encode() const;
    
    virtual AlpsKnowledge* decode(AlpsEncoded& encoded) const;

    virtual AlpsSubTree* newSubTree() const {
        return new AlpsSubTree;
    }

    void clearNodePools() {
        if (nodePool_) {
            nodePool_->clear();
        }
        if (diveNodePool_) {
            diveNodePool_->clear();
        }
    }

    void nullRootActiveNode() {
        root_ = NULL;
        activeNode_ = NULL;
    }

    void reset() {
        // Move nodes in diving pool to normal pool.
        AlpsTreeNode *tempNode = NULL;
        while (diveNodePool_->getNumKnowledges() > 0) {
            tempNode = dynamic_cast<AlpsTreeNode *>
                (diveNodePool_->getKnowledge().first);
            diveNodePool_->popKnowledge();
            nodePool_->addKnowledge(tempNode, tempNode->getQuality());
        }
        if (activeNode_) {   
            nodePool_->addKnowledge(activeNode_, activeNode_->getQuality());
            activeNode_ = NULL;
        }

        diveDepth_ = 0;
    }
    
};
#endif

//#############################################################################
// The way to create children:
//-----------------------------------------------------------------------------
// In AlpsSubTree::exploreSubTree(root)
// If (pregnant) 
// => KnapTreeNode::branch() 
// => AlpsSubTree::createChildren(...)  {
//   AlpsTreeNode::setNumChildren(...) (allocate memory if not);
//   KnapTreeNode:: createNewTreeNode(...); 
//   AlpsSubTree::setChildren;
//   AlspSubTree::setStatus }
//#############################################################################

//#############################################################################
// The way to remove nodes:
//-----------------------------------------------------------------------------
// In AlpsSubTree::exploreSubTree(root)
// If (fathomed)
// => AlpsSubTree::removeDeadNode(node) {
//      AlpsTreeNode::removeChild(node) {
//        AlpsTreeNode::removeDescendants();
//      }
//    Check whether parent has children; 
//      if (yes), recursively removeDeadNode(parent) 
//#############################################################################