Alps  1.5.3
AlpsSubTree.h
Go to the documentation of this file.
1 /*===========================================================================*
2  * This file is part of the Abstract Library for Parallel Search (ALPS). *
3  * *
4  * ALPS is distributed under the Eclipse Public License as part of the *
5  * COIN-OR repository (http://www.coin-or.org). *
6  * *
7  * Authors: *
8  * *
9  * Yan Xu, Lehigh University *
10  * Ted Ralphs, Lehigh University *
11  * *
12  * Conceptual Design: *
13  * *
14  * Yan Xu, Lehigh University *
15  * Ted Ralphs, Lehigh University *
16  * Laszlo Ladanyi, IBM T.J. Watson Research Center *
17  * Matthew Saltzman, Clemson University *
18  * *
19  * *
20  * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs. *
21  *===========================================================================*/
22 
23 #ifndef AlpsSubTree_h_
24 #define AlpsSubTree_h_
25 
26 #include <cassert>
27 #include <list>
28 
29 #include "CoinError.hpp"
30 #include "CoinSort.hpp"
31 
32 #include "AlpsSearchStrategy.h"
33 #include "AlpsKnowledge.h"
34 #include "AlpsNodePool.h"
35 #include "AlpsPriorityQueue.h"
36 #include "AlpsTreeNode.h"
37 
39 
40 //#############################################################################
41 
47 class AlpsSubTree : public AlpsKnowledge {
48 
49  protected:
50 
53 
56 
59 
61  AlpsSearchStrategy<AlpsTreeNode*> * diveNodeRule_;
62 
65 
66  // /** The next index to be assigned to a new search tree node */
67  // AlpsNodeIndex_t nextIndex_;
68 
72 
74  double quality_;
75 
78  // Need broker to query model && parameters.
80 
81  protected:
82 
89  void removeDeadNodes(AlpsTreeNode*& node);
90 
92  void replaceNode(AlpsTreeNode* oldNode, AlpsTreeNode* newNode);
93 
97  void fathomAllNodes();
98 
99  public:
100 
102  AlpsSubTree();
103 
106 
108  virtual ~AlpsSubTree();
109 
110  public:
111 
113  inline AlpsTreeNode* activeNode() { return activeNode_; }
114 
117  { activeNode_ = activeNode; }
118 
120  void createChildren(AlpsTreeNode* parent,
121  std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus,
122  double> >& children,
123  AlpsNodePool *kidNodePool = NULL);
124 
129  inline AlpsTreeNode* getRoot() const { return root_; }
130 
132  inline void setRoot(AlpsTreeNode* r) { root_ = r; }
133 
135  inline AlpsNodePool* nodePool() { return nodePool_; }
136 
139 
141  inline void setNodePool(AlpsNodePool* np) {
142  if (nodePool_ != NULL) {
143  delete nodePool_;
144  nodePool_ = NULL;
145  }
146  nodePool_ = np;
147  }
148 
150  inline void changeNodePool(AlpsNodePool* np) {
151  if (nodePool_ != NULL) {
152  // Remove all elements first.
153  nodePool_->clear();
154  // Delete an empty pool.
155  assert(nodePool_->hasKnowledge() == false);
156  delete nodePool_;
157  nodePool_ = NULL;
158  }
159  nodePool_ = np;
160  }
161 
163  double getBestKnowledgeValue() const;
164 
166  AlpsTreeNode *getBestNode() const;
167 
169  inline AlpsKnowledgeBroker* getKnowledgeBroker() const { return broker_; }
170 
173  assert(kb);
174  broker_ = kb;
175  }
176 
178  inline double getQuality() const { return quality_; }
179 
181  inline double getSolEstimate() const {
182  if (root_) {
183  return root_->getSolEstimate();
184  }
185  else {
186  return ALPS_OBJ_MAX;
187  };
188  }
189 
191  void incDiveDepth(int num=1) { diveDepth_ += num; }
192 
194  int getDiveDepth() { return diveDepth_; }
195 
197  void setDiveDepth(int num) { diveDepth_ = num; }
198 
201  double calculateQuality();
202 
203  /* Get the index of the next generated node and increment next index
204  by one.*/
205  int nextIndex();
206 
208  int getNextIndex() const;
209 
211  void setNextIndex(int next);
212 
214  int getNumNodes() const {
215  assert(nodePool_ && diveNodePool_);
216  int nn = 0;
217  if (activeNode_) {
218  if ( (activeNode_->getStatus() != AlpsNodeStatusFathomed) &&
219  (activeNode_->getStatus() != AlpsNodeStatusBranched) ) {
220  ++nn;
221  }
222  }
223  return (nn + nodePool_->getNumKnowledges() +
224  diveNodePool_->getNumKnowledges());
225  }
226 
228  void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
229  nodePool_->setNodeSelection(*nc);
230  }
232 
235  AlpsSubTree* splitSubTree(int& returnSize, int size = 10);
236 
241  int nodeLimit,
242  double timeLimit,
243  int & numNodesProcessed, /* Output */
244  int & numNodesBranched, /* Output */
245  int & numNodesDiscarded, /* Output */
246  int & numNodesPartial, /* Output */
247  int & depth); /* Output */
248 
254  AlpsReturnStatus exploreUnitWork(bool leaveAsIt,
255  int unitWork,
256  double unitTime,
257  AlpsExitStatus & solStatus,/*not for parallel*/
258  int & numNodesProcessed, /* Output */
259  int & numNodesBranched, /* Output */
260  int & numNodesDiscarded, /* Output */
261  int & numNodesPartial, /* Output */
262  int & depth, /* Output */
263  bool & betterSolution); /* Output */
264 
267  virtual int rampUp(int minNumNodes,
268  int requiredNumNodes,
269  int& depth,
270  AlpsTreeNode* root = NULL);
271 
272  using AlpsKnowledge::encode ;
275  virtual AlpsEncoded* encode() const;
276 
281  virtual AlpsKnowledge* decode(AlpsEncoded& encoded) const;
282 
285  virtual AlpsSubTree* newSubTree() const {
286  return new AlpsSubTree;
287  }
288 
290  void clearNodePools() {
291  if (nodePool_) {
292  nodePool_->clear();
293  }
294  if (diveNodePool_) {
295  diveNodePool_->clear();
296  }
297  }
298 
301  root_ = NULL;
302  activeNode_ = NULL;
303  }
304 
306  void reset() {
307  // Move nodes in diving pool to normal pool.
308  AlpsTreeNode *tempNode = NULL;
309  while (diveNodePool_->getNumKnowledges() > 0) {
310  tempNode = dynamic_cast<AlpsTreeNode *>
311  (diveNodePool_->getKnowledge().first);
312  diveNodePool_->popKnowledge();
313  nodePool_->addKnowledge(tempNode, tempNode->getQuality());
314  }
315  if (activeNode_) {
316  nodePool_->addKnowledge(activeNode_, activeNode_->getQuality());
317  activeNode_ = NULL;
318  }
319 
320  diveDepth_ = 0;
321  }
322 
323 };
324 #endif
325 
326 //#############################################################################
327 // The way to create children:
328 //-----------------------------------------------------------------------------
329 // In AlpsSubTree::exploreSubTree(root)
330 // If (pregnant)
331 // => KnapTreeNode::branch()
332 // => AlpsSubTree::createChildren(...) {
333 // AlpsTreeNode::setNumChildren(...) (allocate memory if not);
334 // KnapTreeNode:: createNewTreeNode(...);
335 // AlpsSubTree::setChildren;
336 // AlspSubTree::setStatus }
337 //#############################################################################
338 
339 //#############################################################################
340 // The way to remove nodes:
341 //-----------------------------------------------------------------------------
342 // In AlpsSubTree::exploreSubTree(root)
343 // If (fathomed)
344 // => AlpsSubTree::removeDeadNode(node) {
345 // AlpsTreeNode::removeChild(node) {
346 // AlpsTreeNode::removeDescendants();
347 // }
348 // Check whether parent has children;
349 // if (yes), recursively removeDeadNode(parent)
350 //#############################################################################
double getBestKnowledgeValue() const
Get the quality of the best node in the subtree.
AlpsNodePool * diveNodePool_
A node pool used when diving.
Definition: AlpsSubTree.h:58
void fathomAllNodes()
Fathom all nodes on this subtree.
AlpsNodePool * nodePool()
Access the node pool.
Definition: AlpsSubTree.h:135
double getQuality() const
Query/set the quality of the node.
Definition: AlpsTreeNode.h:222
void setRoot(AlpsTreeNode *r)
Set the root node of this subtree.
Definition: AlpsSubTree.h:132
void changeNodePool(AlpsNodePool *np)
Set node pool.
Definition: AlpsSubTree.h:150
void clearNodePools()
Remove nodes in pools in the subtree.
Definition: AlpsSubTree.h:290
void setNextIndex(int next)
Set the index of the next generated node.
int getDiveDepth()
Get dive depth.
Definition: AlpsSubTree.h:194
virtual AlpsSubTree * newSubTree() const
Create a AlpsSubtree object dynamically.
Definition: AlpsSubTree.h:285
AlpsReturnStatus
Definition: Alps.h:118
AlpsTreeNode * getBestNode() const
Get the "best" node in the subtree.
AlpsExitStatus
Definition: Alps.h:101
int getNumKnowledges() const
Query the number of nodes in the node pool.
Definition: AlpsNodePool.h:55
void setKnowledgeBroker(AlpsKnowledgeBroker *kb)
Set a pointer to the knowledge broker.
Definition: AlpsSubTree.h:172
void setActiveNode(AlpsTreeNode *activeNode)
Set pointer to active node.
Definition: AlpsSubTree.h:116
The abstract base class of any user-defined class that Alps has to know about in order to encode/deco...
Definition: AlpsKnowledge.h:51
void addKnowledge(AlpsKnowledge *node, double priority)
Remove the node with highest priority from the pool and the elite list.
Definition: AlpsNodePool.h:110
void nullRootActiveNode()
Set root and active node to null.
Definition: AlpsSubTree.h:300
void removeDeadNodes(AlpsTreeNode *&node)
The purpose of this method is to remove nodes that are not needed in the description of the subtree...
void incDiveDepth(int num=1)
Increment dive depth.
Definition: AlpsSubTree.h:191
The base class of knowledge broker class.
AlpsSearchStrategy< AlpsTreeNode * > * diveNodeRule_
Diving node comparing rule.
Definition: AlpsSubTree.h:61
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
This data structure is to contain the packed form of an encodable knowledge.
Definition: AlpsEncoded.h:25
int getNextIndex() const
Get the index of the next generated node.
A class to refer to the description of a search tree node.
Definition: AlpsNodeDesc.h:35
AlpsKnowledgeBroker * broker_
A pointer to the knowledge broker of the process where this subtree is processed. ...
Definition: AlpsSubTree.h:79
virtual ~AlpsSubTree()
Destructor.
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > *nc)
Set the node comparision rule.
Definition: AlpsSubTree.h:228
double calculateQuality()
Calcuate and return the quality of this subtree, which is measured by the quality of the specified nu...
AlpsKnowledgeBroker * getKnowledgeBroker() const
Get the knowledge broker.
Definition: AlpsSubTree.h:169
AlpsNodeStatus
The possible stati for the search nodes.
Definition: Alps.h:61
double quality_
A quantity indicating how good this subtree is.
Definition: AlpsSubTree.h:74
Node pool is used to store the nodes to be processed.
Definition: AlpsNodePool.h:37
virtual int rampUp(int minNumNodes, int requiredNumNodes, int &depth, AlpsTreeNode *root=NULL)
Generate required number (specified by a parameter) of nodes.
double getSolEstimate() const
Get the emtimated quality of this subtree.
Definition: AlpsSubTree.h:181
virtual AlpsReturnStatus exploreSubTree(AlpsTreeNode *root, int nodeLimit, double timeLimit, int &numNodesProcessed, int &numNodesBranched, int &numNodesDiscarded, int &numNodesPartial, int &depth)
Explore the subtree from root as the root of the subtree for given number of nodes or time...
std::pair< AlpsKnowledge *, double > getKnowledge() const
Get the node with highest priority.
Definition: AlpsNodePool.h:96
bool hasKnowledge() const
Check whether there are still nodes in the node pool.
Definition: AlpsNodePool.h:93
void createChildren(AlpsTreeNode *parent, std::vector< CoinTriple< AlpsNodeDesc *, AlpsNodeStatus, double > > &children, AlpsNodePool *kidNodePool=NULL)
Create children nodes from the given parent node.
int getNumNodes() const
Return the number of nodes on this subtree.
Definition: AlpsSubTree.h:214
AlpsTreeNode * root_
The root of the sub tree.
Definition: AlpsSubTree.h:52
AlpsTreeNode * activeNode()
Get pointer to active node.
Definition: AlpsSubTree.h:113
AlpsNodePool * nodePool_
A node pool containing the leaf nodes awaiting processing.
Definition: AlpsSubTree.h:55
double getSolEstimate() const
Query/set the solution estimate of the node.
Definition: AlpsTreeNode.h:216
AlpsTreeNode * getRoot() const
Get the root node of this subtree.
Definition: AlpsSubTree.h:129
void reset()
Move nodes in node pool, null active node.
Definition: AlpsSubTree.h:306
virtual AlpsEncoded * encode() const
This method should encode the content of the subtree and return a pointer to the encoded form...
int diveDepth_
Diving depth.
Definition: AlpsSubTree.h:64
void setNodePool(AlpsNodePool *np)
Set node pool.
Definition: AlpsSubTree.h:141
virtual AlpsEncoded * encode() const
This method should encode the content of the object and return a pointer to the encoded form...
int nextIndex()
AlpsReturnStatus exploreUnitWork(bool leaveAsIt, int unitWork, double unitTime, AlpsExitStatus &solStatus, int &numNodesProcessed, int &numNodesBranched, int &numNodesDiscarded, int &numNodesPartial, int &depth, bool &betterSolution)
Explore the subtree for certain amount of work/time.
#define ALPS_OBJ_MAX
Definition: Alps.h:145
AlpsSubTree()
Default constructor.
void popKnowledge()
Remove the node with highest priority from the pool.
Definition: AlpsNodePool.h:103
AlpsSubTree * splitSubTree(int &returnSize, int size=10)
The function split the subtree and return a subtree of the specified size or available size...
virtual AlpsKnowledge * decode(AlpsEncoded &encoded) const
This method should decode and return a pointer to a brand new object, i.e., the method must create a ...
void setDiveDepth(int num)
Set dive depth.
Definition: AlpsSubTree.h:197
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > &compare)
Set strategy and resort heap.
Definition: AlpsNodePool.h:127
AlpsNodeStatus getStatus() const
Query/set the current status.
Definition: AlpsTreeNode.h:176
AlpsTreeNode * activeNode_
The next index to be assigned to a new search tree node.
Definition: AlpsSubTree.h:71
This class contains the data pertaining to a particular subtree in the search tree.
Definition: AlpsSubTree.h:47
double getQuality() const
Get the quality of this subtree.
Definition: AlpsSubTree.h:178
AlpsNodePool * diveNodePool()
Access the node pool.
Definition: AlpsSubTree.h:138
void replaceNode(AlpsTreeNode *oldNode, AlpsTreeNode *newNode)
This function replaces oldNode with newNode in the tree.
void clear()
Remove all the nodes in the pool (does not free memory).
Definition: AlpsNodePool.h:142