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 
31 #include "CoinMessageHandler.hpp"
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 
53  AlpsKnowledgeBroker& operator=(const AlpsKnowledgeBroker&);
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 
116  int solNum_;
117 
120 
123 
126 
129 
133 
136 
139 
142 
144  double peakMemory_;
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 
288  AlpsPhase getPhase() { return phase_; }
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 
342  virtual int getMaxNumKnowledges(AlpsKnowledgeType kt) const {
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 
387  virtual void popKnowledge(AlpsKnowledgeType kt) {
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 
415  virtual void addKnowledge(AlpsKnowledgeType kt,
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 
432  int getNumNodesProcessed() const {
433  return nodeProcessedNum_;
434  }
435 
437  int getNumNodesBranched() const {
438  return nodeBranchedNum_;
439  }
440 
442  int getNumNodesDiscarded() const {
443  return nodeDiscardedNum_;
444  }
445 
447  int getNumNodesPartial() const {
448  return nodePartialNum_;
449  }
450 
453  return systemNodeProcessed_;
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 
538  virtual AlpsProcessType getProcType() const
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 {
582  return rampUpNodeSelection_;
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 
619  int getlogFileLevel() { return logFileLevel_; }
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.
CoinMessages * messagesPointer()
Return pointer to messages.
void passInMessageHandler(CoinMessageHandler *handler)
Pass in Message handler (not deleted at end).
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.
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.
virtual AlpsTreeNode * getBestNode() const
Query the best node in the subtree pool.
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.
AlpsTimer & tempTimer()
Query secondary timer.
CoinMessages messages()
Return messages.
int nodeLeftNum_
The number of nodes left.
AlpsSubTreePool * subTreePool_
A subtree pool holding a collection of subtrees.
AlpsSearchStrategy< AlpsTreeNode * > * nodeSelection_
Node selection criterion.
CoinMessages messages_
Alps messages.
AlpsTimer & subTreeTimer()
Query subtree timer.
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.
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 std::pair< AlpsKnowledge *, double > getBestKnowledge(AlpsKnowledgeType kt) const
Get the best knowledge in the given type of knowledge pools.
virtual double getBestEstimateQuality()
Get best estimalted quality in system.
virtual std::pair< AlpsKnowledge *, double > getKnowledge(AlpsKnowledgeType kt) const
Get a knowledge, but doesn't remove it from the pool.
virtual void rootSearch(AlpsTreeNode *root)=0
Explore the tree rooted as the given root.
int numNodeLog_
Times that node log is printed.
AlpsSearchStrategy< AlpsSubTree * > * getSubTreeSelection() const
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.
AlpsSearchStrategy< AlpsTreeNode * > * getNodeSelection() const
int workerMsgLevel_
The leve of printing message to screen of workers.
AlpsSolutionPool * solPool_
A solution pool containing the solutions found.
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.
std::string instanceName_
The instance name.
void setNextNodeIndex(AlpsNodeIndex_t s)
Set nextIndex_.
AlpsKnowledgePool * getKnowledgePool(AlpsKnowledgeType kt) const
Retrieve a knowledge pool in the Knowledge base.
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.
AlpsTimer & timer()
Query timer.
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.
CoinMessageHandler * messageHandler() const
Return handler.
void setPhase(AlpsPhase ph)
int nodePartialNum_
The number of nodes that are pregnant.
AlpsSearchStrategy< AlpsTreeNode * > * getRampUpNodeSelection() const
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