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                                        *
 *          Aykut Bulut, 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-2023, Lehigh University, Yan Xu, Aykut Bulut, and      *
 *                          Ted Ralphs.                                      *
 * All Rights Reserved.                                                      *
 *===========================================================================*/
 
 
#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_;
 
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 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;
  // Encode this into the given AlpsEncoded object.
  virtual AlpsReturnStatus encode(AlpsEncoded * encoded) const;
  // Decode the given AlpsEncoded object into a new object and return a
  // pointer to it.
  virtual AlpsKnowledge * decode(AlpsEncoded & encoded) const;
  virtual AlpsReturnStatus decodeToSelf(AlpsEncoded & encoded);
 
  virtual AlpsSubTree* newSubTree() const {
    return new AlpsSubTree(broker_);
  }
 
  void clearNodePools() {
    if (nodePool_) {
      nodePool_->clear();
    }
    if (diveNodePool_) {
      diveNodePool_->clear();
    }
  }
 
  void nullRootActiveNode() {
    root_ = NULL;
    activeNode_ = NULL;
  }
 
  bool doDive() {
     return true;
  }
 
  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)
//#############################################################################