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

- File List
- File Members

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
38 class AlpsKnowledgeBroker;
39
40 //#############################################################################
41
47 class AlpsSubTree : public AlpsKnowledge {
48
49 protected:
50
52 AlpsTreeNode* root_;
53
55 AlpsNodePool* nodePool_;
56
58 AlpsNodePool* diveNodePool_;
59
61 AlpsSearchStrategy<AlpsTreeNode*> * diveNodeRule_;
62
64 int diveDepth_;
65
66 // /** The next index to be assigned to a new search tree node */
67 // AlpsNodeIndex_t nextIndex_;
68
71 AlpsTreeNode* activeNode_;
72
74 double quality_;
75
78 // Need broker to query model && parameters.
79 AlpsKnowledgeBroker* broker_;
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
105 AlpsSubTree(AlpsKnowledgeBroker* kb);
106
108 virtual ~AlpsSubTree();
109
110 public:
111
113 inline AlpsTreeNode* activeNode() { return activeNode_; }
114
116 inline void setActiveNode(AlpsTreeNode *activeNode)
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
138 inline AlpsNodePool* diveNodePool() { return diveNodePool_; }
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
172 inline void setKnowledgeBroker(AlpsKnowledgeBroker* kb) {
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
240 virtual AlpsReturnStatus exploreSubTree(AlpsTreeNode* root,
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
300 void nullRootActiveNode() {
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 //#############################################################################
AlpsKnowledgeBroker
The base class of knowledge broker class.
Definition: AlpsKnowledgeBroker.h:48
AlpsNodePool.h
AlpsSubTree::getBestKnowledgeValue
double getBestKnowledgeValue() const
Get the quality of the best node in the subtree.
AlpsSubTree::fathomAllNodes
void fathomAllNodes()
Fathom all nodes on this subtree.
AlpsNodePool::getNumKnowledges
int getNumKnowledges() const
Query the number of nodes in the node pool.
Definition: AlpsNodePool.h:55
AlpsSubTree::getNextIndex
int getNextIndex() const
Get the index of the next generated node.
AlpsTreeNode::getSolEstimate
double getSolEstimate() const
Query/set the solution estimate of the node.
Definition: AlpsTreeNode.h:216
AlpsSubTree::reset
void reset()
Move nodes in node pool, null active node.
Definition: AlpsSubTree.h:306
AlpsSubTree::broker_
AlpsKnowledgeBroker * broker_
A pointer to the knowledge broker of the process where this subtree is processed. ...
Definition: AlpsSubTree.h:79
AlpsSubTree::createChildren
void createChildren(AlpsTreeNode *parent, std::vector< CoinTriple< AlpsNodeDesc *, AlpsNodeStatus, double > > &children, AlpsNodePool *kidNodePool=NULL)
Create children nodes from the given parent node.
AlpsReturnStatus
AlpsReturnStatus
Definition: Alps.h:118
AlpsNodePool::setNodeSelection
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > &compare)
Set strategy and resort heap.
Definition: AlpsNodePool.h:127
AlpsSubTree::setNodeSelection
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > *nc)
Set the node comparision rule.
Definition: AlpsSubTree.h:228
AlpsNodePool::getKnowledge
std::pair< AlpsKnowledge *, double > getKnowledge() const
Get the node with highest priority.
Definition: AlpsNodePool.h:96
CoinError.hpp
AlpsSubTree::getKnowledgeBroker
AlpsKnowledgeBroker * getKnowledgeBroker() const
Get the knowledge broker.
Definition: AlpsSubTree.h:169
AlpsNodeStatusBranched
Definition: Alps.h:65
AlpsNodeStatus
AlpsNodeStatus
The possible stati for the search nodes.
Definition: Alps.h:61
AlpsSubTree::rampUp
virtual int rampUp(int minNumNodes, int requiredNumNodes, int &depth, AlpsTreeNode *root=NULL)
Generate required number (specified by a parameter) of nodes.
AlpsSubTree::nullRootActiveNode
void nullRootActiveNode()
Set root and active node to null.
Definition: AlpsSubTree.h:300
AlpsSubTree::~AlpsSubTree
virtual ~AlpsSubTree()
Destructor.
AlpsSubTree
This class contains the data pertaining to a particular subtree in the search tree.
Definition: AlpsSubTree.h:47
AlpsSubTree::activeNode_
AlpsTreeNode * activeNode_
The next index to be assigned to a new search tree node.
Definition: AlpsSubTree.h:71
AlpsSubTree::replaceNode
void replaceNode(AlpsTreeNode *oldNode, AlpsTreeNode *newNode)
This function replaces oldNode with newNode in the tree.
AlpsNodePool::clear
void clear()
Remove all the nodes in the pool (does not free memory).
Definition: AlpsNodePool.h:142
AlpsNodeStatusFathomed
Definition: Alps.h:66
AlpsSubTree::clearNodePools
void clearNodePools()
Remove nodes in pools in the subtree.
Definition: AlpsSubTree.h:290
AlpsSubTree::nextIndex
int nextIndex()
Get the root node of this subtree.
AlpsSubTree::removeDeadNodes
void removeDeadNodes(AlpsTreeNode *&node)
The purpose of this method is to remove nodes that are not needed in the description of the subtree...
AlpsEncoded
This data structure is to contain the packed form of an encodable knowledge.
Definition: AlpsEncoded.h:25
AlpsSubTree::getSolEstimate
double getSolEstimate() const
Get the emtimated quality of this subtree.
Definition: AlpsSubTree.h:181
AlpsSubTree::exploreSubTree
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...
AlpsPriorityQueue.h
AlpsSubTree::encode
virtual AlpsEncoded * encode() const
This method should encode the content of the subtree and return a pointer to the encoded form...
AlpsSubTree::nodePool_
AlpsNodePool * nodePool_
A node pool containing the leaf nodes awaiting processing.
Definition: AlpsSubTree.h:55
AlpsSubTree::diveNodePool_
AlpsNodePool * diveNodePool_
A node pool used when diving.
Definition: AlpsSubTree.h:58
CoinTriple
Definition: CoinSort.hpp:459
AlpsNodePool::addKnowledge
void addKnowledge(AlpsKnowledge *node, double priority)
Remove the node with highest priority from the pool and the elite list.
Definition: AlpsNodePool.h:110
AlpsTreeNode
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50
AlpsSubTree::getQuality
double getQuality() const
Get the quality of this subtree.
Definition: AlpsSubTree.h:178
AlpsSubTree::getDiveDepth
int getDiveDepth()
Get dive depth.
Definition: AlpsSubTree.h:194
AlpsNodePool::popKnowledge
void popKnowledge()
Remove the node with highest priority from the pool.
Definition: AlpsNodePool.h:103
AlpsExitStatus
AlpsExitStatus
Definition: Alps.h:101
AlpsSubTree::diveDepth_
int diveDepth_
Diving depth.
Definition: AlpsSubTree.h:64
AlpsSubTree::getRoot
AlpsTreeNode * getRoot() const
Get the root node of this subtree.
Definition: AlpsSubTree.h:129
AlpsSubTree::diveNodePool
AlpsNodePool * diveNodePool()
Access the node pool.
Definition: AlpsSubTree.h:138
ALPS_OBJ_MAX
#define ALPS_OBJ_MAX
Definition: Alps.h:145
AlpsSubTree::setNextIndex
void setNextIndex(int next)
Set the index of the next generated node.
AlpsSubTree::nodePool
AlpsNodePool * nodePool()
Access the node pool.
Definition: AlpsSubTree.h:135
AlpsKnowledge.h
AlpsKnowledge
The abstract base class of any user-defined class that Alps has to know about in order to encode/deco...
Definition: AlpsKnowledge.h:51
AlpsSubTree::getNumNodes
int getNumNodes() const
Return the number of nodes on this subtree.
Definition: AlpsSubTree.h:214
AlpsSubTree::exploreUnitWork
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.
CoinSort.hpp
AlpsTreeNode.h
AlpsTreeNode::getStatus
AlpsNodeStatus getStatus() const
Query/set the current status.
Definition: AlpsTreeNode.h:176
AlpsSubTree::setActiveNode
void setActiveNode(AlpsTreeNode *activeNode)
Set pointer to active node.
Definition: AlpsSubTree.h:116
AlpsSubTree::setRoot
void setRoot(AlpsTreeNode *r)
Set the root node of this subtree.
Definition: AlpsSubTree.h:132
AlpsSearchStrategy.h
AlpsSubTree::root_
AlpsTreeNode * root_
The root of the sub tree.
Definition: AlpsSubTree.h:52
AlpsNodePool
Node pool is used to store the nodes to be processed.
Definition: AlpsNodePool.h:37
AlpsNodePool::hasKnowledge
bool hasKnowledge() const
Check whether there are still nodes in the node pool.
Definition: AlpsNodePool.h:93
AlpsSubTree::splitSubTree
AlpsSubTree * splitSubTree(int &returnSize, int size=10)
The function split the subtree and return a subtree of the specified size or available size...
AlpsSubTree::decode
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 ...
AlpsSubTree::setKnowledgeBroker
void setKnowledgeBroker(AlpsKnowledgeBroker *kb)
Set a pointer to the knowledge broker.
Definition: AlpsSubTree.h:172
AlpsSubTree::newSubTree
virtual AlpsSubTree * newSubTree() const
Create a AlpsSubtree object dynamically.
Definition: AlpsSubTree.h:285
AlpsSubTree::quality_
double quality_
A quantity indicating how good this subtree is.
Definition: AlpsSubTree.h:74
AlpsSubTree::incDiveDepth
void incDiveDepth(int num=1)
Increment dive depth.
Definition: AlpsSubTree.h:191
AlpsSubTree::activeNode
AlpsTreeNode * activeNode()
Get pointer to active node.
Definition: AlpsSubTree.h:113
AlpsSubTree::AlpsSubTree
AlpsSubTree()
Default constructor.
AlpsSubTree::setDiveDepth
void setDiveDepth(int num)
Set dive depth.
Definition: AlpsSubTree.h:197
AlpsKnowledge::encode
virtual AlpsEncoded * encode() const
This method should encode the content of the object and return a pointer to the encoded form...
AlpsSubTree::calculateQuality
double calculateQuality()
Calcuate and return the quality of this subtree, which is measured by the quality of the specified nu...
AlpsSubTree::diveNodeRule_
AlpsSearchStrategy< AlpsTreeNode * > * diveNodeRule_
Diving node comparing rule.
Definition: AlpsSubTree.h:61
AlpsNodeDesc
A class to refer to the description of a search tree node.
Definition: AlpsNodeDesc.h:35
AlpsSubTree::changeNodePool
void changeNodePool(AlpsNodePool *np)
Set node pool.
Definition: AlpsSubTree.h:150
AlpsSubTree::getBestNode
AlpsTreeNode * getBestNode() const
Get the &quot;best&quot; node in the subtree.
AlpsSubTree::setNodePool
void setNodePool(AlpsNodePool *np)
Set node pool.
Definition: AlpsSubTree.h:141
AlpsTreeNode::getQuality
double getQuality() const
Query/set the quality of the node.
Definition: AlpsTreeNode.h:222