Alps 1.5.7
AlpsKnowledgeBroker.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 AlpsKnowledgeBroker_h_
24#define AlpsKnowledgeBroker_h_
25
26#include <cmath>
27#include <iosfwd>
28#include <map>
29#include <string>
30
32
33#include "AlpsSearchStrategy.h"
34#include "AlpsEnumProcessT.h"
35#include "AlpsKnowledge.h"
36#include "AlpsKnowledgePool.h"
37#include "AlpsMessage.h"
38#include "AlpsParams.h"
39#include "AlpsSolutionPool.h"
40#include "AlpsSubTree.h"
41#include "AlpsSubTreePool.h"
42#include "AlpsModel.h"
43#include "AlpsTime.h"
44
45//#############################################################################
46
49
50 private:
51
54
56 std::map<int, AlpsKnowledge*> decodeMap_;
57
58 protected:
59
61 std::string instanceName_;
62
65
68
76
79
81 std::map<AlpsKnowledgeType, AlpsKnowledgePool*>* pools_;
83
90
93
96
100
105 /***/
108
111
114
117
120
123
126
129
133
136
139
142
145
149
155 AlpsSearchStrategy<AlpsSubTree*>* treeSelection_;
156
158 AlpsSearchStrategy<AlpsTreeNode*>* nodeSelection_;
159
161 AlpsSearchStrategy<AlpsTreeNode*>* rampUpNodeSelection_;
163
170
173
177
181
185
189
191 std::string logfile_;
193
196
199
202
205
208
209 public:
210
213
216
219
220 //-------------------------------------------------------------------------
233 void registerClass(int name, AlpsKnowledge* userKnowledge) {
234 // Check if alread have one.
235 std::map<int, AlpsKnowledge*>::iterator pos, pos1;
236 pos = decodeMap_.find(name);
237 pos1 = decodeMap_.end();
238
239 if (pos != pos1) {
240 AlpsKnowledge* kl = pos->second;
241 decodeMap_.erase(pos);
242 delete kl;
243 }
244
245 decodeMap_[name] = userKnowledge;
246 }
247
256 const AlpsKnowledge* decoderObject(int name) {
257 return decodeMap_[name];
258 }
260
261 //------------------------------------------------------
262
268 virtual void initializeSearch(int argc,
269 char* argv[],
270 AlpsModel& model) = 0;
271
273 virtual void rootSearch(AlpsTreeNode* root) = 0;
274
276 virtual void search(AlpsModel *model) {
277 AlpsTreeNode* root = model->createRoot();
278 rootSearch(root);
279 }
281
282 //------------------------------------------------------
283
289 void setPhase(AlpsPhase ph) { phase_ = ph; }
291
293 AlpsModel *getModel() { return model_; }
294 void setModel(AlpsModel *m) { model_ = m; }
296
298 int getTreeDepth() { return treeDepth_; }
299
301 void setPeakMemory(double size) { peakMemory_ = size; }
302
304 double getPeakMemory() { return peakMemory_; }
305
312
316 // AlpsKnowledgePool* akp = static_cast<AlpsKnowledgePool*>(kp);
317 pools_->insert
318 (std::pair<AlpsKnowledgeType, AlpsKnowledgePool*>(kt, kp));
319 }
320 else {
321 throw CoinError("Broker doesn't manage this type of knowledge",
322 "addKnowledgePool()", "AlpsKnowledgeBroker");
323 }
324 }
325
329 return (*pools_)[kt];
330 }
331 else {
332 throw CoinError("Broker doesn't manage this type of knowledge",
333 "getKnowledgePool()", "AlpsKnowledgeBroker");
334 }
335 }
336
338 virtual int getNumKnowledges(AlpsKnowledgeType kt) const;
339
345 }
346 else {
347 throw CoinError("Broker doesn't manage this type of knowledge",
348 "getMaxNumKnowledges()", "AlpsKnowledgeBroker");
349 }
350 }
351
354 virtual void setMaxNumKnowledges(AlpsKnowledgeType kt, int num) {
357 }
358 else {
359 throw CoinError("Broker doesn't manage this type of knowledge",
360 "setMaxNumKnowledges()", "AlpsKnowledgeBroker");
361 }
362 }
363
366 virtual bool hasKnowledge(AlpsKnowledgeType kt) const {
368 return getKnowledgePool(kt)->hasKnowledge();
369 else
370 throw CoinError("Broker doesn't manage this type of knowledge",
371 "hasKnowledge()", "AlpsKnowledgeBroker");
372 }
373
375 virtual std::pair<AlpsKnowledge*, double>
378 return getKnowledgePool(kt)->getKnowledge();
379 }
380 else {
381 throw CoinError("Broker doesn't manage this type of knowledge",
382 "getKnowledge()", "AlpsKnowledgeBroker");
383 }
384 }
385
390 }
391 else {
392 throw CoinError("Broker doesn't manage this type of knowledge",
393 "popKnowledge()", "AlpsKnowledgeBroker");
394 }
395 }
396
398 virtual std::pair<AlpsKnowledge*, double>
400
403 std::vector<std::pair<AlpsKnowledge*,
404 double> >& kls) const {
407 }
408 else {
409 throw CoinError("Broker doesn't manage this type of knowledge",
410 "popKnowledge()", "AlpsKnowledgeBroker");
411 }
412 }
413
416 AlpsKnowledge* kl,
417 double value ) {
419 getKnowledgePool(kt)->addKnowledge(kl, value);
420 }
421 else {
422 throw CoinError("Broker doesn't manage this type of knowledge",
423 "popKnowledge()", "AlpsKnowledgeBroker");
424 }
425 }
427
433 return nodeProcessedNum_;
434 }
435
438 return nodeBranchedNum_;
439 }
440
443 return nodeDiscardedNum_;
444 }
445
447 int getNumNodesPartial() const {
448 return nodePartialNum_;
449 }
450
454 }
455
457 virtual int updateNumNodesLeft();
458
460 virtual AlpsTreeNode* getBestNode() const;
461
464 return exitStatus_;
465 }
466
469 exitStatus_ = status;
470 }
471
474 return timer_;
475 }
476
479 return subTreeTimer_;
480 }
481
484 return tempTimer_;
485 }
486
488 virtual void searchLog() = 0;
490
495 int getNodeMemSize() { return nodeMemSize_; }
496 void setNodeMemSize(int ms) { nodeMemSize_ = ms; }
498
504 void setNodeProcessingTime(double npTime) { nodeProcessingTime_ = npTime; }
506
507 int getLargeSize() const { return largeSize_; }
508
515 virtual double getIncumbentValue() const = 0;
516
519 virtual double getBestQuality() const = 0;
520
522 virtual double getBestEstimateQuality() { return ALPS_OBJ_MAX; }
523
524 virtual int getNumNodeLeftSystem(){ return nodeLeftNum_; }
525
528 virtual void printBestSolution(char* outputFile = 0) const = 0;
530
532 virtual int getProcRank() const { return 0; }
533
535 virtual int getMasterRank() const { return 0; }
536
539 { return AlpsProcessTypeSerial; } /* Default is serial */
540
548
551
554
557
561
566 AlpsSearchStrategy<AlpsSubTree*>* getSubTreeSelection() const {
567 return treeSelection_;
568 }
569 void setSubTreeSelection(AlpsSearchStrategy<AlpsSubTree*>* tc) {
570 if (treeSelection_) delete treeSelection_;
571 treeSelection_ = tc;
573 }
574 AlpsSearchStrategy<AlpsTreeNode*>* getNodeSelection() const {
575 return nodeSelection_;
576 }
577 void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
578 if (nodeSelection_) delete nodeSelection_;
579 nodeSelection_ = nc;
580 }
581 AlpsSearchStrategy<AlpsTreeNode*>* getRampUpNodeSelection() const {
583 }
584 void setRampUpNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
587 }
589
594
598 { newLanguage(language); }
599
602
605
608
610 int getMsgLevel() { return msgLevel_; }
611
613 int getHubMsgLevel() { return hubMsgLevel_; }
614
617
620
622 int getNumNodeLog() const { return numNodeLog_; }
623
625 void setNumNodeLog(int num) { numNodeLog_ = num; }
627};
628#endif
AlpsProcessType
This enumerative constant describes the various process types.
@ AlpsProcessTypeSerial
Serial.
int AlpsNodeIndex_t
Definition: AlpsTreeNode.h:37
AlpsKnowledgeType
Definition: Alps.h:88
@ AlpsKnowledgeTypeSolution
Definition: Alps.h:92
@ AlpsKnowledgeTypeSubTree
Definition: Alps.h:93
AlpsPhase
Definition: Alps.h:129
AlpsExitStatus
Definition: Alps.h:101
#define ALPS_OBJ_MAX
Definition: Alps.h:145
The base class of knowledge broker class.
virtual void searchLog()=0
Search statistics log.
bool userBalancePeriod_
Has user input balance period.
virtual bool hasKnowledge(AlpsKnowledgeType kt) const
Query whether there are knowledges in the given type of knowledge pools.
virtual int updateNumNodesLeft()
Update the number of left nodes on this process.
int nodeProcessedNum_
The number of nodes that have been processed.
AlpsSubTree * workingSubTree_
Point to the subtree that being explored.
void passInMessageHandler(CoinMessageHandler *handler)
Pass in Message handler (not deleted at end).
AlpsKnowledgePool * getKnowledgePool(AlpsKnowledgeType kt) const
Retrieve a knowledge pool in the Knowledge base.
std::string logfile_
The log file.
virtual void search(AlpsModel *model)
Search best solution for a given model.
void setNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > *nc)
void setExitStatus(AlpsExitStatus status)
Set terminate status.
virtual void addKnowledge(AlpsKnowledgeType kt, AlpsKnowledge *kl, double value)
Add a knowledge in the given type of knowledge pools.
virtual int getNumKnowledges(AlpsKnowledgeType kt) const
Query the number of knowledge in the given type of a knowledge pool.
AlpsSearchStrategy< AlpsSubTree * > * treeSelection_
Tree selection criterion.
AlpsNodeIndex_t getMaxNodeIndex() const
Queriy the upper bound of node indices.
void newLanguage(CoinMessages::Language language)
Set language.
AlpsSearchStrategy< AlpsTreeNode * > * getNodeSelection() const
virtual int getNumNodeLeftSystem()
void setModel(AlpsModel *m)
AlpsKnowledgeBroker()
Default constructor.
int getlogFileLevel()
Return log file level.
AlpsExitStatus getSolStatus() const
Query search termination status.
AlpsModel * model_
Pointer to model.
double getPeakMemory()
Get peak memory usage.
double nodeProcessingTime_
The approximately CPU time to process a node.
void setMaxNodeIndex(AlpsNodeIndex_t s)
Set the upper bound of node indices.
bool needWorkingSubTree_
Indicate whether need a new subtree.
void setupKnowledgePools()
Set up knowledge pools for this broker.
int getNumNodesProcessedSystem() const
Query the number of node processed by the system.
AlpsSearchStrategy< AlpsTreeNode * > * rampUpNodeSelection_
Node selection criterion.
int nodeDiscardedNum_
The number of nodes that have been discarded before processing.
CoinMessageHandler * handler_
Message handler.
AlpsKnowledgeBroker(AlpsModel &model)
Constructor passing in model.
virtual void initializeSearch(int argc, char *argv[], AlpsModel &model)=0
Do some initialization for search.
virtual int getProcRank() const
Qeury the global rank of process.
CoinMessageHandler * messageHandler() const
Return handler.
CoinMessages * messagesPointer()
Return pointer to messages.
CoinMessages messages()
Return messages.
int nodeLeftNum_
The number of nodes left.
AlpsSubTreePool * subTreePool_
A subtree pool holding a collection of subtrees.
AlpsSearchStrategy< AlpsSubTree * > * getSubTreeSelection() const
AlpsSearchStrategy< AlpsTreeNode * > * nodeSelection_
Node selection criterion.
CoinMessages messages_
Alps messages.
void addKnowledgePool(AlpsKnowledgeType kt, AlpsKnowledgePool *kp)
Add a knowledge pool into the Knowledge pools.
AlpsNodeIndex_t nextNodeIndex()
Query the next index assigned to a newly created node, and then increment the nextIndex_ by 1.
AlpsNodeIndex_t getNextNodeIndex() const
Query the next index assigned to a newly created node.
virtual std::pair< AlpsKnowledge *, double > getKnowledge(AlpsKnowledgeType kt) const
Get a knowledge, but doesn't remove it from the pool.
int getHubMsgLevel()
Return msg level.
int logFileLevel_
The degree of log file.
AlpsNodeIndex_t nextIndex_
The index to be assigned to a new search tree node.
virtual void popKnowledge(AlpsKnowledgeType kt)
Remove the a knowledge from the given type of knowledge pools.
virtual double getBestEstimateQuality()
Get best estimalted quality in system.
virtual void rootSearch(AlpsTreeNode *root)=0
Explore the tree rooted as the given root.
AlpsTimer & subTreeTimer()
Query subtree timer.
int numNodeLog_
Times that node log is printed.
AlpsNodeIndex_t maxIndex_
The maximum index can been assigned on this process.
AlpsTimer subTreeTimer_
Subtree timer.
AlpsPhase phase_
Alps phase.
virtual ~AlpsKnowledgeBroker()
Destructor.
int getNumNodesPartial() const
Query the number of node in the queue that are pregnant.
int nodeBranchedNum_
The number of nodes that have been branched.
virtual double getIncumbentValue() const =0
The process queries the objective value of the incumbent that it stores.
virtual AlpsProcessType getProcType() const
Query the type (master, hub, or worker) of the process.
int nodeMemSize_
The approximate memory size (bytes) of a node with full description.
int workerMsgLevel_
The leve of printing message to screen of workers.
virtual AlpsTreeNode * getBestNode() const
Query the best node in the subtree pool.
AlpsSolutionPool * solPool_
A solution pool containing the solutions found.
AlpsTimer & tempTimer()
Query secondary timer.
AlpsTimer timer_
Main timer.
AlpsExitStatus exitStatus_
The status of search when terminated.
void setNumNodeLog(int num)
Get times that node log has been printed.
std::map< AlpsKnowledgeType, AlpsKnowledgePool * > * pools_
The collection of pools managed by the knowledge broker.
int getMasterMsgLevel()
Return msg level.
const AlpsKnowledge * decoderObject(int name)
This method returns the pointer to an empty object of the registered class name.
virtual void getAllKnowledges(AlpsKnowledgeType kt, std::vector< std::pair< AlpsKnowledge *, double > > &kls) const
Get all knowledges in the given type of knowledge pools.
void registerClass(int name, AlpsKnowledge *userKnowledge)
Every user derived knowledge class must register.
virtual void printBestSolution(char *outputFile=0) const =0
The process (serial) / the master (parallel) outputs the best solution that it knows to a file or std...
int hubMsgLevel_
The leve of printing message to screen of hubs.
int getMsgLevel()
Return msg level.
void setPeakMemory(double size)
Set peak memory usage.
virtual double getBestQuality() const =0
The process (serial) / the master (parallel) queries the quality of the best solution that it knows.
int getNumNodeLog() const
Get times that node log has been printed.
void setRampUpNodeSelection(AlpsSearchStrategy< AlpsTreeNode * > *nc)
int getTreeDepth()
Get tree depth.
int getNumNodesProcessed() const
Query the number of node processed by this process.
virtual int getMaxNumKnowledges(AlpsKnowledgeType kt) const
Query the max number of knowledge can be stored in a given type of knowledge pools.
double peakMemory_
Peak memory usage.
int getNumNodesBranched() const
Query the number of node processed by this process.
virtual void setMaxNumKnowledges(AlpsKnowledgeType kt, int num)
Set the max number of knowledge can be stored in a given type o fknowledge pools.
virtual int getMasterRank() const
Query the global rank of the Master.
virtual std::pair< AlpsKnowledge *, double > getBestKnowledge(AlpsKnowledgeType kt) const
Get the best knowledge in the given type of knowledge pools.
std::string instanceName_
The instance name.
void setNextNodeIndex(AlpsNodeIndex_t s)
Set nextIndex_.
AlpsTimer & timer()
Query timer.
AlpsSearchStrategy< AlpsTreeNode * > * getRampUpNodeSelection() const
AlpsTimer tempTimer_
Secondary timer.
int getNumNodesDiscarded() const
Query the number of node processed by this process.
int largeSize_
The size of largest message buffer can be sent or received.
void setLanguage(CoinMessages::Language language)
int msgLevel_
The leve of printing message to screen of the master and general message.
void setSubTreeSelection(AlpsSearchStrategy< AlpsSubTree * > *tc)
int systemNodeProcessed_
To record how many nodes processed by the system (used in parallel code).
void setNodeProcessingTime(double npTime)
int treeDepth_
The depth of the tree.
int bestSolNode_
The number of nodes pocessed to find the solution.
void setPhase(AlpsPhase ph)
int nodePartialNum_
The number of nodes that are pregnant.
int solNum_
The number of solutions found.
virtual void setMaxNumKnowledges(int num)
Set the quantity limit of knowledges that can be stored in the pool.
virtual void addKnowledge(AlpsKnowledge *nk, double priority)=0
Add a knowledge to pool.
virtual void getAllKnowledges(std::vector< std::pair< AlpsKnowledge *, double > > &kls) const
Get a reference to all the knowledges in the pool.
virtual void popKnowledge()
Remove the queried knowledge from the pool.
virtual bool hasKnowledge() const
Check whether the pool has knowledge.
virtual int getMaxNumKnowledges() const
Query the quantity limit of knowledges.
virtual std::pair< AlpsKnowledge *, double > getKnowledge() const =0
Query a knowledge, but doesn't remove it from the pool.
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 AlpsTreeNode * createRoot()
Create the root node.
Definition: AlpsModel.h:102
In the solution pool we assume that the lower the priority value the more desirable the solution is.
The subtree pool is used to store subtrees.
void setComparison(AlpsSearchStrategy< AlpsSubTree * > &compare)
Set comparison function and resort heap.
This class contains the data pertaining to a particular subtree in the search tree.
Definition: AlpsSubTree.h:47
This class holds one node of the search tree.
Definition: AlpsTreeNode.h:50