Alps 1.5.12
Loading...
Searching...
No Matches
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-2023, 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
54
56 std::map<int, AlpsKnowledge*> decodeMap_;
57
58 protected:
59
61 std::string instanceName_;
62
65
68
73
76
79
81 std::map<AlpsKnowledgeType, AlpsKnowledgePool*>* pools_;
83
88
90
93
96
100
105 /***/
108
111
114
117
120
123
126
129
133
136
139
142
145
149
154
155 AlpsSearchStrategy<AlpsSubTree*>* treeSelection_;
156
158 AlpsSearchStrategy<AlpsTreeNode*>* nodeSelection_;
159
161 AlpsSearchStrategy<AlpsTreeNode*>* rampUpNodeSelection_;
163
168
169 CoinMessageHandler * handler_;
170
172 CoinMessages messages_;
173
177
181
185
189
191 std::string logfile_;
193
196
199
202
205
208
209 public:
210
213
216
219
220 //-------------------------------------------------------------------------
225
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
255
256 const AlpsKnowledge* decoderObject(int name) {
257 return decodeMap_[name];
258 }
259
260
261 //------------------------------------------------------
262
267
268 virtual void initializeSearch(int argc,
269 char* argv[],
270 AlpsModel& model,
271 bool showBanner = true) = 0;
272
274 virtual void rootSearch(AlpsTreeNode* root) = 0;
275
277 virtual void search(AlpsModel *model) {
278 AlpsTreeNode* root = model->createRoot();
279 rootSearch(root);
280 }
281
282
283 //------------------------------------------------------
284
290 void setPhase(AlpsPhase ph) { phase_ = ph; }
292
294 AlpsModel *getModel() { return model_; }
295 void setModel(AlpsModel *m) { model_ = m; }
297
299 int getTreeDepth() { return treeDepth_; }
300
302 void setPeakMemory(double size) { peakMemory_ = size; }
303
305 double getPeakMemory() { return peakMemory_; }
306
311
313
317 // AlpsKnowledgePool* akp = static_cast<AlpsKnowledgePool*>(kp);
318 pools_->insert
319 (std::pair<AlpsKnowledgeType, AlpsKnowledgePool*>(kt, kp));
320 }
321 else {
322 throw CoinError("Broker doesn't manage this type of knowledge",
323 "addKnowledgePool()", "AlpsKnowledgeBroker");
324 }
325 }
326
330 return (*pools_)[kt];
331 }
332 else {
333 throw CoinError("Broker doesn't manage this type of knowledge",
334 "getKnowledgePool()", "AlpsKnowledgeBroker");
335 }
336 }
337
339 virtual int getNumKnowledges(AlpsKnowledgeType kt) const;
340
346 }
347 else {
348 throw CoinError("Broker doesn't manage this type of knowledge",
349 "getMaxNumKnowledges()", "AlpsKnowledgeBroker");
350 }
351 }
352
355 virtual void setMaxNumKnowledges(AlpsKnowledgeType kt, int num) {
358 }
359 else {
360 throw CoinError("Broker doesn't manage this type of knowledge",
361 "setMaxNumKnowledges()", "AlpsKnowledgeBroker");
362 }
363 }
364
367 virtual bool hasKnowledge(AlpsKnowledgeType kt) const {
369 return getKnowledgePool(kt)->hasKnowledge();
370 else
371 throw CoinError("Broker doesn't manage this type of knowledge",
372 "hasKnowledge()", "AlpsKnowledgeBroker");
373 }
374
376 virtual std::pair<AlpsKnowledge*, double>
379 return getKnowledgePool(kt)->getKnowledge();
380 }
381 else {
382 throw CoinError("Broker doesn't manage this type of knowledge",
383 "getKnowledge()", "AlpsKnowledgeBroker");
384 }
385 }
386
391 }
392 else {
393 throw CoinError("Broker doesn't manage this type of knowledge",
394 "popKnowledge()", "AlpsKnowledgeBroker");
395 }
396 }
397
399 virtual std::pair<AlpsKnowledge*, double>
401
404 std::vector<std::pair<AlpsKnowledge*,
405 double> >& kls) const {
408 }
409 else {
410 throw CoinError("Broker doesn't manage this type of knowledge",
411 "popKnowledge()", "AlpsKnowledgeBroker");
412 }
413 }
414
417 AlpsKnowledge* kl,
418 double value ) {
420 getKnowledgePool(kt)->addKnowledge(kl, value);
421 }
422 else {
423 throw CoinError("Broker doesn't manage this type of knowledge",
424 "popKnowledge()", "AlpsKnowledgeBroker");
425 }
426 }
427
428
434 return nodeProcessedNum_;
435 }
436
439 return nodeBranchedNum_;
440 }
441
444 return nodeDiscardedNum_;
445 }
446
448 int getNumNodesPartial() const {
449 return nodePartialNum_;
450 }
451
455 }
456
458 virtual int updateNumNodesLeft();
459
461 virtual AlpsTreeNode* getBestNode() const;
462
465 return exitStatus_;
466 }
467
470 exitStatus_ = status;
471 }
472
475 return timer_;
476 }
477
480 return subTreeTimer_;
481 }
482
485 return tempTimer_;
486 }
487
489 virtual void searchLog() = 0;
491
496 int getNodeMemSize() { return nodeMemSize_; }
497 void setNodeMemSize(int ms) { nodeMemSize_ = ms; }
499
505 void setNodeProcessingTime(double npTime) { nodeProcessingTime_ = npTime; }
507
508 int getLargeSize() const { return largeSize_; }
509
514
516 virtual double getIncumbentValue() const = 0;
517
520 virtual double getBestQuality() const = 0;
521
523 virtual double getBestEstimateQuality() { return ALPS_OBJ_MAX; }
524
525 virtual int getNumNodeLeftSystem(){ return nodeLeftNum_; }
526
529 virtual void printBestSolution(char* outputFile = 0) const = 0;
531
533 virtual int getProcRank() const { return 0; }
534
536 virtual int getMasterRank() const { return 0; }
537
540 { return AlpsProcessTypeSerial; } /* Default is serial */
541
546
549
552
555
558
562
567 AlpsSearchStrategy<AlpsSubTree*>* getSubTreeSelection() const {
568 return treeSelection_;
569 }
570 void setSubTreeSelection(AlpsSearchStrategy<AlpsSubTree*>* tc) {
571 if (treeSelection_) delete treeSelection_;
572 treeSelection_ = tc;
573 subTreePool_->setComparison(*treeSelection_);
574 }
575 AlpsSearchStrategy<AlpsTreeNode*>* getNodeSelection() const {
576 return nodeSelection_;
577 }
578 void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
579 if (nodeSelection_) delete nodeSelection_;
580 nodeSelection_ = nc;
581 }
582 AlpsSearchStrategy<AlpsTreeNode*>* getRampUpNodeSelection() const {
584 }
585 void setRampUpNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) {
588 }
589
590
593
594 void passInMessageHandler(CoinMessageHandler * handler);
595
597 void newLanguage(CoinMessages::Language language);
598 void setLanguage(CoinMessages::Language language)
599 { newLanguage(language); }
600
602 CoinMessageHandler * messageHandler() const { return handler_; }
603
605 CoinMessages messages() { return messages_; }
606
608 CoinMessages * messagesPointer() { return &messages_; }
609
611 int getMsgLevel() { return msgLevel_; }
612
614 int getHubMsgLevel() { return hubMsgLevel_; }
615
618
621
623 int getNumNodeLog() const { return numNodeLog_; }
624
626 void setNumNodeLog(int num) { numNodeLog_ = num; }
628
629 //Suresh: added temporarily for warm starting
631};
632#endif
AlpsProcessType
This enumerative constant describes the various process types.
@ AlpsProcessTypeSerial
Serial.
int AlpsNodeIndex_t
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
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.
std::map< int, AlpsKnowledge * > decodeMap_
Stores registered knowledge.
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 int getProcRank() const
Qeury the global rank of process.
CoinMessageHandler * messageHandler() const
Return handler.
CoinMessages * messagesPointer()
Return pointer to messages.
CoinMessages messages()
Return messages.
AlpsKnowledgeBroker(const AlpsKnowledgeBroker &)
int nodeLeftNum_
The number of nodes left.
AlpsSubTreePool * subTreePool_
A subtree pool holding a collection of subtrees.
AlpsSubTree * getWorkingSubTree()
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.
virtual void initializeSearch(int argc, char *argv[], AlpsModel &model, bool showBanner=true)=0
Do some initialization for search.
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.
AlpsKnowledgeBroker & operator=(const AlpsKnowledgeBroker &)
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...
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.
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.