Alps 1.5.11
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-2023, 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...
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.
Node pool is used to store the nodes to be processed.
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > &compare)
Set strategy and resort heap.
void popKnowledge()
Remove the node with highest priority from the pool.
int getNumKnowledges() const
Query the number of nodes in the node pool.
void addKnowledge(AlpsKnowledge *node, double priority)
Remove the node with highest priority from the pool and the elite list.
void clear()
Remove all the nodes in the pool (does not free memory).
bool hasKnowledge() const
Check whether there are still nodes in the node pool.
std::pair< AlpsKnowledge *, double > getKnowledge() const
Get the node with highest priority.
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.
int getNextIndex() const
Get the index of the next generated node.
void clearNodePools()
Remove nodes in pools in the subtree.
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.
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.
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.
void setKnowledgeBroker(AlpsKnowledgeBroker *kb)
Set a pointer to the knowledge broker.
AlpsTreeNode * getBestNode() const
Get the "best" node in the subtree.
void setActiveNode(AlpsTreeNode *activeNode)
Set pointer to active node.
AlpsNodePool * diveNodePool()
Access the node pool.
double getSolEstimate() const
Get the emtimated quality of this subtree.
bool doDive()
Check whether we should keep diving or not.
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.
AlpsTreeNode * getRoot() const
Get the root node of this subtree.
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.
virtual ~AlpsSubTree()
Destructor.
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > *nc)
Set the node comparision rule.
int getNumNodes() const
Return the number of nodes on this subtree.
void reset()
Move nodes in node pool, null active node.
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.
double getBestKnowledgeValue() const
Get the quality of the best node in the subtree.
void nullRootActiveNode()
Set root and active node to null.
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.
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.
AlpsNodeStatus getStatus() const
Query/set the current status.
double getQuality() const
Query/set the quality of the node.
double getSolEstimate() const
Query/set the solution estimate of the node.