Alps 1.5.7
Loading...
Searching...
No Matches
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
47class 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
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
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.*/
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
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
279 if (nodePool_) {
280 nodePool_->clear();
281 }
282 if (diveNodePool_) {
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
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
std::pair< AlpsKnowledge *, double > getKnowledge() const
Get the node with highest priority.
Definition: AlpsNodePool.h:112
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.
AlpsTreeNode * activeNode()
Get pointer to active node.
Definition: AlpsSubTree.h:110
int getNextIndex() const
Get the index of the next generated node.
void clearNodePools()
Remove nodes in pools in the subtree.
Definition: AlpsSubTree.h:278
virtual AlpsEncoded * encode() const
This method should encode the content of the subtree and return a pointer to the encoded form.
AlpsTreeNode * activeNode_
This is the node that is currently being processed.
Definition: AlpsSubTree.h:68
AlpsKnowledgeBroker * getKnowledgeBroker() const
Get the knowledge broker.
Definition: AlpsSubTree.h:166
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 AlpsSubTree * newSubTree() const
Create a AlpsSubtree object dynamically.
Definition: AlpsSubTree.h:273
void setKnowledgeBroker(AlpsKnowledgeBroker *kb)
Set a pointer to the knowledge broker.
Definition: AlpsSubTree.h:169
AlpsTreeNode * getBestNode() const
Get the "best" node in the subtree.
void setActiveNode(AlpsTreeNode *activeNode)
Set pointer to active node.
Definition: AlpsSubTree.h:113
AlpsNodePool * diveNodePool()
Access the node pool.
Definition: AlpsSubTree.h:135
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
AlpsNodePool * nodePool()
Access the node pool.
Definition: AlpsSubTree.h:132
AlpsTreeNode * getRoot() const
Get the root node of this subtree.
Definition: AlpsSubTree.h:126
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
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
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 ...
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
AlpsSubTree * splitSubTree(int &returnSize, int size=10)
The function split the subtree and return a subtree of the specified size or available size.
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