Alps  1.5.7
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-2019, 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 
63  // /** The next index to be assigned to a new search tree node */
64  // AlpsNodeIndex_t nextIndex_;
65 
69 
71  double quality_;
72 
75  // Need broker to query model && parameters.
77 
78  protected:
79 
87 
89  void replaceNode(AlpsTreeNode* oldNode, AlpsTreeNode* newNode);
90 
95 
96  public:
97 
100 
103 
105  virtual ~AlpsSubTree();
106 
107  public:
108 
110  inline AlpsTreeNode* activeNode() { return activeNode_; }
111 
114  { activeNode_ = activeNode; }
115 
118  std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus,
119  double> >& children,
120  AlpsNodePool *kidNodePool = NULL);
121 
126  inline AlpsTreeNode* getRoot() const { return root_; }
127 
129  inline void setRoot(AlpsTreeNode* r) { root_ = r; }
130 
132  inline AlpsNodePool* nodePool() { return nodePool_; }
133 
136 
138  inline void setNodePool(AlpsNodePool* np) {
139  if (nodePool_ != NULL) {
140  delete nodePool_;
141  nodePool_ = NULL;
142  }
143  nodePool_ = np;
144  }
145 
147  inline void changeNodePool(AlpsNodePool* np) {
148  if (nodePool_ != NULL) {
149  // Remove all elements first.
150  nodePool_->clear();
151  // Delete an empty pool.
152  assert(nodePool_->hasKnowledge() == false);
153  delete nodePool_;
154  nodePool_ = NULL;
155  }
156  nodePool_ = np;
157  }
158 
160  double getBestKnowledgeValue() const;
161 
164 
166  inline AlpsKnowledgeBroker* getKnowledgeBroker() const { return broker_; }
167 
170  assert(kb);
171  broker_ = kb;
172  }
173 
175  inline double getQuality() const { return quality_; }
176 
178  inline double getSolEstimate() const {
179  if (root_) {
180  return root_->getSolEstimate();
181  }
182  else {
183  return ALPS_OBJ_MAX;
184  };
185  }
186 
190 
191  /* Get the index of the next generated node and increment next index
192  by one.*/
193  int nextIndex();
194 
196  int getNextIndex() const;
197 
199  void setNextIndex(int next);
200 
202  int getNumNodes() const {
203  assert(nodePool_ && diveNodePool_);
204  int nn = 0;
205  if (activeNode_) {
208  ++nn;
209  }
210  }
211  return (nn + nodePool_->getNumKnowledges() +
213  }
214 
216  void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
218  }
220 
223  AlpsSubTree* splitSubTree(int& returnSize, int size = 10);
224 
229  int nodeLimit,
230  double timeLimit,
231  int & numNodesProcessed, /* Output */
232  int & numNodesBranched, /* Output */
233  int & numNodesDiscarded, /* Output */
234  int & numNodesPartial, /* Output */
235  int & depth); /* Output */
236 
243  int unitWork,
244  double unitTime,
245  AlpsExitStatus & solStatus,/*not for parallel*/
246  int & numNodesProcessed, /* Output */
247  int & numNodesBranched, /* Output */
248  int & numNodesDiscarded, /* Output */
249  int & numNodesPartial, /* Output */
250  int & depth, /* Output */
251  bool & betterSolution); /* Output */
252 
255  virtual int rampUp(int minNumNodes,
256  int requiredNumNodes,
257  int& depth,
258  AlpsTreeNode* root = NULL);
259 
260  using AlpsKnowledge::encode ;
263  virtual AlpsEncoded* encode() const;
264 
269  virtual AlpsKnowledge* decode(AlpsEncoded& encoded) const;
270 
273  virtual AlpsSubTree* newSubTree() const {
274  return new AlpsSubTree;
275  }
276 
278  void clearNodePools() {
279  if (nodePool_) {
280  nodePool_->clear();
281  }
282  if (diveNodePool_) {
283  diveNodePool_->clear();
284  }
285  }
286 
289  root_ = NULL;
290  activeNode_ = NULL;
291  }
292 
294  bool doDive() {
295  return true;
296  }
297 
299  void reset() {
300  // Move nodes in diving pool to normal pool.
301  AlpsTreeNode *tempNode = NULL;
302  while (diveNodePool_->getNumKnowledges() > 0) {
303  tempNode = dynamic_cast<AlpsTreeNode *>
304  (diveNodePool_->getKnowledge().first);
306  nodePool_->addKnowledge(tempNode, tempNode->getQuality());
307  }
308  if (activeNode_) {
310  activeNode_ = NULL;
311  }
312  }
313 
314 };
315 #endif
316 
317 //#############################################################################
318 // The way to create children:
319 //-----------------------------------------------------------------------------
320 // In AlpsSubTree::exploreSubTree(root)
321 // If (pregnant)
322 // => KnapTreeNode::branch()
323 // => AlpsSubTree::createChildren(...) {
324 // AlpsTreeNode::setNumChildren(...) (allocate memory if not);
325 // KnapTreeNode:: createNewTreeNode(...);
326 // AlpsSubTree::setChildren;
327 // AlspSubTree::setStatus }
328 //#############################################################################
329 
330 //#############################################################################
331 // The way to remove nodes:
332 //-----------------------------------------------------------------------------
333 // In AlpsSubTree::exploreSubTree(root)
334 // If (fathomed)
335 // => AlpsSubTree::removeDeadNode(node) {
336 // AlpsTreeNode::removeChild(node) {
337 // AlpsTreeNode::removeDescendants();
338 // }
339 // Check whether parent has children;
340 // if (yes), recursively removeDeadNode(parent)
341 //#############################################################################
AlpsReturnStatus
Definition: Alps.h:118
AlpsNodeStatus
The possible stati for the search nodes.
Definition: Alps.h:61
@ AlpsNodeStatusFathomed
Definition: Alps.h:66
@ AlpsNodeStatusBranched
Definition: Alps.h:65
AlpsExitStatus
Definition: Alps.h:101
#define ALPS_OBJ_MAX
Definition: Alps.h:145
This data structure is to contain the packed form of an encodable knowledge.
Definition: AlpsEncoded.h:25
The base class of knowledge broker class.
The abstract base class of any user-defined class that Alps has to know about in order to encode/deco...
Definition: AlpsKnowledge.h:51
virtual AlpsEncoded * encode() const
This method should encode the content of the object and return a pointer to the encoded form.
A class to refer to the description of a search tree node.
Definition: AlpsNodeDesc.h:35
Node pool is used to store the nodes to be processed.
Definition: AlpsNodePool.h:37
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > &compare)
Set strategy and resort heap.
Definition: AlpsNodePool.h:143
void popKnowledge()
Remove the node with highest priority from the pool.
Definition: AlpsNodePool.h:119
int getNumKnowledges() const
Query the number of nodes in the node pool.
Definition: AlpsNodePool.h:60
void addKnowledge(AlpsKnowledge *node, double priority)
Remove the node with highest priority from the pool and the elite list.
Definition: AlpsNodePool.h:126
std::pair< AlpsKnowledge *, double > getKnowledge() const
Get the node with highest priority.
Definition: AlpsNodePool.h:112
void clear()
Remove all the nodes in the pool (does not free memory).
Definition: AlpsNodePool.h:158
bool hasKnowledge() const
Check whether there are still nodes in the node pool.
Definition: AlpsNodePool.h:109
This class contains the data pertaining to a particular subtree in the search tree.
Definition: AlpsSubTree.h:47
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.
void createChildren(AlpsTreeNode *parent, std::vector< CoinTriple< AlpsNodeDesc *, AlpsNodeStatus, double > > &children, AlpsNodePool *kidNodePool=NULL)
Create children nodes from the given parent node.
AlpsNodePool * nodePool_
A node pool containing the leaf nodes awaiting processing.
Definition: AlpsSubTree.h:55
AlpsSubTree(AlpsKnowledgeBroker *kb)
Useful constructor.
virtual AlpsSubTree * newSubTree() const
Create a AlpsSubtree object dynamically.
Definition: AlpsSubTree.h:273
int getNextIndex() const
Get the index of the next generated node.
void clearNodePools()
Remove nodes in pools in the subtree.
Definition: AlpsSubTree.h:278
AlpsTreeNode * activeNode_
This is the node that is currently being processed.
Definition: AlpsSubTree.h:68
AlpsTreeNode * getBestNode() const
Get the "best" node in the subtree.
void removeDeadNodes(AlpsTreeNode *&node)
The purpose of this method is to remove nodes that are not needed in the description of the subtree.
void changeNodePool(AlpsNodePool *np)
Set node pool.
Definition: AlpsSubTree.h:147
double quality_
A quantity indicating how good this subtree is.
Definition: AlpsSubTree.h:71
double calculateQuality()
Calcuate and return the quality of this subtree, which is measured by the quality of the specified nu...
AlpsSubTree()
Default constructor.
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 ...
AlpsNodePool * diveNodePool()
Access the node pool.
Definition: AlpsSubTree.h:135
void setKnowledgeBroker(AlpsKnowledgeBroker *kb)
Set a pointer to the knowledge broker.
Definition: AlpsSubTree.h:169
AlpsKnowledgeBroker * getKnowledgeBroker() const
Get the knowledge broker.
Definition: AlpsSubTree.h:166
void setActiveNode(AlpsTreeNode *activeNode)
Set pointer to active node.
Definition: AlpsSubTree.h:113
AlpsTreeNode * getRoot() const
Get the root node of this subtree.
Definition: AlpsSubTree.h:126
virtual AlpsEncoded * encode() const
This method should encode the content of the subtree and return a pointer to the encoded form.
double getSolEstimate() const
Get the emtimated quality of this subtree.
Definition: AlpsSubTree.h:178
bool doDive()
Check whether we should keep diving or not.
Definition: AlpsSubTree.h:294
AlpsKnowledgeBroker * broker_
A pointer to the knowledge broker of the process where this subtree is processed.
Definition: AlpsSubTree.h:76
AlpsTreeNode * root_
The root of the sub tree.
Definition: AlpsSubTree.h:52
void fathomAllNodes()
Fathom all nodes on this subtree.
AlpsSearchStrategy< AlpsTreeNode * > * diveNodeRule_
Diving node comparing rule.
Definition: AlpsSubTree.h:61
AlpsTreeNode * activeNode()
Get pointer to active node.
Definition: AlpsSubTree.h:110
AlpsNodePool * nodePool()
Access the node pool.
Definition: AlpsSubTree.h:132
AlpsNodePool * diveNodePool_
A node pool used when diving.
Definition: AlpsSubTree.h:58
void setNextIndex(int next)
Set the index of the next generated node.
void setRoot(AlpsTreeNode *r)
Set the root node of this subtree.
Definition: AlpsSubTree.h:129
virtual ~AlpsSubTree()
Destructor.
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > *nc)
Set the node comparision rule.
Definition: AlpsSubTree.h:216
int getNumNodes() const
Return the number of nodes on this subtree.
Definition: AlpsSubTree.h:202
void reset()
Move nodes in node pool, null active node.
Definition: AlpsSubTree.h:299
AlpsSubTree * splitSubTree(int &returnSize, int size=10)
The function split the subtree and return a subtree of the specified size or available size.
int nextIndex()
virtual int rampUp(int minNumNodes, int requiredNumNodes, int &depth, AlpsTreeNode *root=NULL)
Generate required number (specified by a parameter) of nodes.
double getQuality() const
Get the quality of this subtree.
Definition: AlpsSubTree.h:175
double getBestKnowledgeValue() const
Get the quality of the best node in the subtree.
void nullRootActiveNode()
Set root and active node to null.
Definition: AlpsSubTree.h:288
void replaceNode(AlpsTreeNode *oldNode, AlpsTreeNode *newNode)
This function replaces oldNode with newNode in the tree.
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,...
void setNodePool(AlpsNodePool *np)
Set node pool.
Definition: AlpsSubTree.h:138
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
AlpsNodeStatus getStatus() const
Query/set the current status.
Definition: AlpsTreeNode.h:172
double getQuality() const
Query/set the quality of the node.
Definition: AlpsTreeNode.h:218
double getSolEstimate() const
Query/set the solution estimate of the node.
Definition: AlpsTreeNode.h:212