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 * Aykut Bulut, Lehigh University * 11 * Ted Ralphs, Lehigh University * 12 * * 13 * Conceptual Design: * 14 * * 15 * Yan Xu, Lehigh University * 16 * Ted Ralphs, Lehigh University * 17 * Laszlo Ladanyi, IBM T.J. Watson Research Center * 18 * Matthew Saltzman, Clemson University * 19 * * 20 * * 21 * Copyright (C) 2001-2019, Lehigh University, Yan Xu, Aykut Bulut, and * 22 * Ted Ralphs. * 23 * All Rights Reserved. * 24 *===========================================================================*/ 25 26 27 #ifndef AlpsKnowledgeBroker_h_ 28 #define AlpsKnowledgeBroker_h_ 29 30 #include <cmath> 31 #include <iosfwd> 32 #include <map> 33 #include <string> 34 35 #include "CoinMessageHandler.hpp" 36 37 #include "AlpsSearchStrategy.h" 38 #include "AlpsEnumProcessT.h" 39 #include "AlpsKnowledge.h" 40 #include "AlpsKnowledgePool.h" 41 #include "AlpsMessage.h" 42 #include "AlpsParams.h" 43 #include "AlpsSolutionPool.h" 44 #include "AlpsSubTree.h" 45 #include "AlpsSubTreePool.h" 46 #include "AlpsModel.h" 47 #include "AlpsTime.h" 48 49 //############################################################################# 50 51 /** The base class of knowledge broker class. */ 52 class AlpsKnowledgeBroker { 53 /** Stores registered knowledge. */ 54 std::map<int, AlpsKnowledge*> decodeMap_; 55 56 protected: 57 58 /** The instance name. */ 59 std::string instanceName_; 60 /** Pointer to model. */ 61 AlpsModel *model_; 62 /** Alps phase. (RAMPUP, SEARCH, RAMPDOWN)*/ 63 AlpsPhase phase_; 64 65 /// @name knowledge pools 66 //@{ 67 /** A subtree pool holding a collection of subtrees. For serial version, 68 there is only one subtree in the pool. */ 69 AlpsSubTreePool* subTreePool_; 70 /** A solution pool containing the solutions found. */ 71 AlpsSolutionPool* solPool_; 72 /** The collection of pools managed by the knowledge broker. */ 73 std::map<AlpsKnowledgeType, AlpsKnowledgePool*>* pools_; 74 //@} 75 76 /// @name Exploring subtree 77 //@{ 78 /** Point to the subtree that being explored. */ 79 AlpsSubTree* workingSubTree_; 80 /** Indicate whether need a new subtree. */ 81 bool needWorkingSubTree_; 82 /** The index to be assigned to a new search tree node. */ 83 AlpsNodeIndex_t nextIndex_; 84 /** The maximum index can been assigned on this process. */ 85 AlpsNodeIndex_t maxIndex_; 86 //@} 87 88 /// @name Statistics 89 //@{ 90 /** Main timer. Do not touch. */ 91 AlpsTimer timer_; 92 /** Subtree timer. Do not touch.*/ 93 AlpsTimer subTreeTimer_; 94 /** Secondary timer. */ 95 AlpsTimer tempTimer_; 96 /** The number of solutions found. */ 97 int solNum_; 98 /** The number of nodes that have been processed. */ 99 int nodeProcessedNum_; 100 /** The number of nodes that have been branched. */ 101 int nodeBranchedNum_; 102 /** The number of nodes that have been discarded before processing. */ 103 int nodeDiscardedNum_; 104 /** The number of nodes that are pregnant. */ 105 int nodePartialNum_; 106 /** To record how many nodes processed by the system 107 (used in parallel code). */ 108 int systemNodeProcessed_; 109 /** The number of nodes left. */ 110 int nodeLeftNum_; 111 /** The depth of the tree. */ 112 int treeDepth_; 113 /** The number of nodes pocessed to find the solution. */ 114 int bestSolNode_; 115 /** Peak memory usage. */ 116 double peakMemory_; 117 /** The status of search when terminated. */ 118 AlpsExitStatus exitStatus_; 119 //@} 120 121 /// @name Search strategy 122 //@{ 123 /** Tree selection criterion. */ 124 AlpsSearchStrategy<AlpsSubTree*>* treeSelection_; 125 /** Node selection criterion. */ 126 AlpsSearchStrategy<AlpsTreeNode*>* nodeSelection_; 127 /** Node selection criterion. */ 128 AlpsSearchStrategy<AlpsTreeNode*>* rampUpNodeSelection_; 129 //@} 130 131 /// @name message handling 132 //@{ 133 /** Message handler. */ 134 CoinMessageHandler * handler_; 135 /** Alps messages. */ 136 CoinMessages messages_; 137 /** The leve of printing message to screen of the master and general message. 138 (0: no; 1: basic; 2: moderate, 3: verbose) */ 139 int msgLevel_; 140 /** The leve of printing message to screen of hubs. 141 (0: no; 1: basic; 2: moderate, 3: verbose) */ 142 int hubMsgLevel_; 143 /** The leve of printing message to screen of workers. 144 (0: no; 1: basic; 2: moderate, 3: verbose) */ 145 int workerMsgLevel_; 146 /** The degree of log file. 147 (0: no; 1: basic; 2: moderate, 3: verbose) */ 148 int logFileLevel_; 149 /** The log file. */ 150 std::string logfile_; 151 //@} 152 153 /** The approximate memory size (bytes) of a node with full description. */ 154 int nodeMemSize_; 155 /** The approximately CPU time to process a node. */ 156 double nodeProcessingTime_; 157 /** The size of largest message buffer can be sent or received. */ 158 int largeSize_; 159 /** Has user input balance period */ 160 bool userBalancePeriod_; 161 /** Times that node log is printed. */ 162 int numNodeLog_; 163 164 public: 165 ///@name Constructor and Destructor. 166 //@{ 167 /** Default constructor. */ 168 AlpsKnowledgeBroker(); 169 /** Constructor that sets the model. */ 170 AlpsKnowledgeBroker(AlpsModel& model); 171 /** Destructor. */ 172 virtual ~AlpsKnowledgeBroker(); 173 //@} 174 175 /// @name Funcitons related to register knowledge. 176 //@{ 177 /** Every user derived knowledge class must register. 178 The register methods register the decode method of the class so that 179 later on we can decode objects from buffers. Invoking this 180 registration for class <code>foo</code> is a single line:<br> 181 <code>foo().registerClass(name, userKnowledge)</code>. 182 NOTE: take over user knowledge's memory ownership, user doesn't 183 need free memory. 184 */ registerClass(int name,AlpsKnowledge * userKnowledge)185 void registerClass(int name, AlpsKnowledge* userKnowledge) { 186 // Check if alread have one. 187 std::map<int, AlpsKnowledge*>::iterator pos, pos1; 188 pos = decodeMap_.find(name); 189 pos1 = decodeMap_.end(); 190 191 if (pos != pos1) { 192 AlpsKnowledge* kl = pos->second; 193 decodeMap_.erase(pos); 194 delete kl; 195 } 196 197 decodeMap_[name] = userKnowledge; 198 userKnowledge->setBroker(this); 199 } 200 /** This method returns the pointer to an empty object of the registered 201 class <code>name</code>. Then the <code>decode()</code> method of that 202 object can be used to decode a new object of the same type from the 203 buffer. This method will be invoked as follows to decode an object 204 whose type is <code>name</code>:<br> 205 <code>obj = AlpsKnowledge::decoderObject(name)->decode(buf) </code> 206 */ decoderObject(int name)207 AlpsKnowledge const * decoderObject(int name) const { 208 // todo(aykut) convert this to .at() once C++11 standard is available. 209 std::map<int,AlpsKnowledge*>::const_iterator it = decodeMap_.find(name); 210 if (it == decodeMap_.end()) { 211 // this should not happen. 212 throw std::exception(); 213 } 214 return it->second; 215 } 216 //@} 217 218 /// @name Funcitons related to exploring subtree. 219 //@{ 220 /** Do some initialization for search. */ 221 virtual void initializeSearch(int argc, 222 char* argv[], 223 AlpsModel& model) = 0; 224 225 /** Explore the tree rooted as the given root. */ 226 virtual void rootSearch(AlpsTreeNode* root) = 0; 227 228 /** Search best solution for a given model. */ search(AlpsModel * model)229 virtual void search(AlpsModel *model) { 230 AlpsTreeNode* root = model->createRoot(); 231 root->setBroker(this); 232 root->modifyDesc()->setBroker(this); 233 rootSearch(root); 234 } 235 //@} 236 237 /// @name Get/set phase. 238 //@{ getPhase()239 AlpsPhase getPhase() { return phase_; } setPhase(AlpsPhase ph)240 void setPhase(AlpsPhase ph) { phase_ = ph; } 241 //@} 242 243 //@{ getModel()244 AlpsModel *getModel() { return model_; } setModel(AlpsModel * m)245 void setModel(AlpsModel *m) { model_ = m; } 246 //@} 247 248 /** Get tree depth */ getTreeDepth()249 int getTreeDepth() { return treeDepth_; } 250 /** Set peak memory usage. */ setPeakMemory(double size)251 void setPeakMemory(double size) { peakMemory_ = size; } 252 /** Get peak memory usage. */ getPeakMemory()253 double getPeakMemory() { return peakMemory_; } 254 255 /** @name Interface with the knowledge pools 256 * 257 */ 258 //@{ 259 /** Set up knowledge pools for this broker. */ 260 void setupKnowledgePools(); 261 /** Add a knowledge pool into the Knowledge pools */ addKnowledgePool(AlpsKnowledgeType kt,AlpsKnowledgePool * kp)262 inline void addKnowledgePool(AlpsKnowledgeType kt, AlpsKnowledgePool* kp) { 263 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) { 264 // AlpsKnowledgePool* akp = static_cast<AlpsKnowledgePool*>(kp); 265 pools_->insert 266 (std::pair<AlpsKnowledgeType, AlpsKnowledgePool*>(kt, kp)); 267 } 268 else { 269 throw CoinError("Broker doesn't manage this type of knowledge", 270 "addKnowledgePool()", "AlpsKnowledgeBroker"); 271 } 272 } 273 /** Retrieve a knowledge pool in the Knowledge base */ getKnowledgePool(AlpsKnowledgeType kt)274 inline AlpsKnowledgePool* getKnowledgePool(AlpsKnowledgeType kt) const { 275 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) { 276 return (*pools_)[kt]; 277 } 278 else { 279 throw CoinError("Broker doesn't manage this type of knowledge", 280 "getKnowledgePool()", "AlpsKnowledgeBroker"); 281 } 282 } 283 /** Query the number of knowledge in the given type of a knowledge pool. */ 284 virtual int getNumKnowledges(AlpsKnowledgeType kt) const; 285 /** Query the max number of knowledge can be stored in a given 286 type of knowledge pools. */ getMaxNumKnowledges(AlpsKnowledgeType kt)287 virtual int getMaxNumKnowledges(AlpsKnowledgeType kt) const { 288 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) { 289 return getKnowledgePool(kt)->getMaxNumKnowledges(); 290 } 291 else { 292 throw CoinError("Broker doesn't manage this type of knowledge", 293 "getMaxNumKnowledges()", "AlpsKnowledgeBroker"); 294 } 295 } 296 /** Set the max number of knowledge can be stored in a given 297 type o fknowledge pools. */ setMaxNumKnowledges(AlpsKnowledgeType kt,int num)298 virtual void setMaxNumKnowledges(AlpsKnowledgeType kt, int num) { 299 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) { 300 getKnowledgePool(kt)->setMaxNumKnowledges(num); 301 } 302 else { 303 throw CoinError("Broker doesn't manage this type of knowledge", 304 "setMaxNumKnowledges()", "AlpsKnowledgeBroker"); 305 } 306 } 307 308 /** Query whether there are knowledges in the given type of 309 knowledge pools. */ hasKnowledge(AlpsKnowledgeType kt)310 virtual bool hasKnowledge(AlpsKnowledgeType kt) const { 311 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) 312 return getKnowledgePool(kt)->hasKnowledge(); 313 else 314 throw CoinError("Broker doesn't manage this type of knowledge", 315 "hasKnowledge()", "AlpsKnowledgeBroker"); 316 } 317 318 /** Get a knowledge, but doesn't remove it from the pool*/ 319 virtual std::pair<AlpsKnowledge*, double> getKnowledge(AlpsKnowledgeType kt)320 getKnowledge(AlpsKnowledgeType kt) const { 321 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) { 322 return getKnowledgePool(kt)->getKnowledge(); 323 } 324 else { 325 throw CoinError("Broker doesn't manage this type of knowledge", 326 "getKnowledge()", "AlpsKnowledgeBroker"); 327 } 328 } 329 330 /** Remove the a knowledge from the given type of knowledge pools.*/ popKnowledge(AlpsKnowledgeType kt)331 virtual void popKnowledge(AlpsKnowledgeType kt) { 332 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) { 333 getKnowledgePool(kt)->popKnowledge(); 334 } 335 else { 336 throw CoinError("Broker doesn't manage this type of knowledge", 337 "popKnowledge()", "AlpsKnowledgeBroker"); 338 } 339 } 340 341 /** Get the best knowledge in the given type of knowledge pools. */ 342 virtual std::pair<AlpsKnowledge*, double> 343 getBestKnowledge(AlpsKnowledgeType kt) const; 344 345 /** Get all knowledges in the given type of knowledge pools. */ getAllKnowledges(AlpsKnowledgeType kt,std::vector<std::pair<AlpsKnowledge *,double>> & kls)346 virtual void getAllKnowledges (AlpsKnowledgeType kt, 347 std::vector<std::pair<AlpsKnowledge*, 348 double> >& kls) const { 349 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) { 350 getKnowledgePool(kt)->getAllKnowledges(kls); 351 } 352 else { 353 throw CoinError("Broker doesn't manage this type of knowledge", 354 "popKnowledge()", "AlpsKnowledgeBroker"); 355 } 356 } 357 358 /** Add a knowledge in the given type of knowledge pools. */ addKnowledge(AlpsKnowledgeType kt,AlpsKnowledge * kl,double value)359 virtual void addKnowledge(AlpsKnowledgeType kt, 360 AlpsKnowledge* kl, 361 double value ) { 362 if(kt == AlpsKnowledgeTypeSolution || kt == AlpsKnowledgeTypeSubTree) { 363 //todo(aykut) is this the right place to do this? 364 //kl->setType(kt); 365 getKnowledgePool(kt)->addKnowledge(kl, value); 366 } 367 else { 368 throw CoinError("Broker doesn't manage this type of knowledge", 369 "popKnowledge()", "AlpsKnowledgeBroker"); 370 } 371 } 372 //@} 373 374 /** @name Querty and set statistics 375 * 376 */ 377 /** Query the number of node processed by this process. */ getNumNodesProcessed()378 int getNumNodesProcessed() const { 379 return nodeProcessedNum_; 380 } 381 /** Query the number of node processed by this process. */ getNumNodesBranched()382 int getNumNodesBranched() const { 383 return nodeBranchedNum_; 384 } 385 /** Query the number of node processed by this process. */ getNumNodesDiscarded()386 int getNumNodesDiscarded() const { 387 return nodeDiscardedNum_; 388 } 389 /** Query the number of node in the queue that are pregnant. */ getNumNodesPartial()390 int getNumNodesPartial() const { 391 return nodePartialNum_; 392 } 393 /** Query the number of node processed by the system. */ getNumNodesProcessedSystem()394 int getNumNodesProcessedSystem() const { 395 return systemNodeProcessed_; 396 } 397 /** Update the number of left nodes on this process. */ 398 virtual int updateNumNodesLeft(); 399 /** Query the best node in the subtree pool. Return NULL if no node exits. */ 400 virtual AlpsTreeNode* getBestNode() const; 401 /** Query search termination status. */ getSolStatus()402 AlpsExitStatus getSolStatus() const { 403 return exitStatus_; 404 } 405 /** Set terminate status. */ setExitStatus(AlpsExitStatus status)406 void setExitStatus(AlpsExitStatus status) { 407 exitStatus_ = status; 408 } 409 /** Query timer. */ timer()410 AlpsTimer & timer() { 411 return timer_; 412 } 413 /** Query subtree timer. */ subTreeTimer()414 AlpsTimer & subTreeTimer() { 415 return subTreeTimer_; 416 } 417 /** Query secondary timer. */ tempTimer()418 AlpsTimer & tempTimer() { 419 return tempTimer_; 420 } 421 /** Search statistics log. */ 422 virtual void searchLog() = 0; 423 //@} 424 425 /// @name Query and set the approximate memory size of a tree node 426 //@{ getNodeMemSize()427 int getNodeMemSize() { return nodeMemSize_; } setNodeMemSize(int ms)428 void setNodeMemSize(int ms) { nodeMemSize_ = ms; } 429 //@} 430 431 /// @name Query and set the approximate node processing time 432 //@{ getNodeProcessingTime()433 double getNodeProcessingTime() { return nodeProcessingTime_; } setNodeProcessingTime(double npTime)434 void setNodeProcessingTime(double npTime) { nodeProcessingTime_ = npTime; } 435 //@} 436 getLargeSize()437 int getLargeSize() const { return largeSize_; } 438 439 /// @name Report the best result 440 //@{ 441 /** The process queries the objective value of the incumbent that 442 it stores.*/ 443 virtual double getIncumbentValue() const = 0; 444 445 /** The process (serial) / the master (parallel) queries the quality 446 of the best solution that it knows. */ 447 virtual double getBestQuality() const = 0; 448 449 /** Get best estimalted quality in system. */ getBestEstimateQuality()450 virtual double getBestEstimateQuality() { return ALPS_OBJ_MAX; } 451 getNumNodeLeftSystem()452 virtual int getNumNodeLeftSystem(){ return nodeLeftNum_; } 453 454 /** The process (serial) / the master (parallel) outputs the best 455 solution that it knows to a file or std::out. */ 456 virtual void printBestSolution(char* outputFile = 0) const = 0; 457 //@} 458 459 /** Qeury the global rank of process. Note: not useful for serial code.*/ getProcRank()460 virtual int getProcRank() const { return 0; } 461 462 /** Query the global rank of the Master. */ getMasterRank()463 virtual int getMasterRank() const { return 0; } 464 465 /** Query the type (master, hub, or worker) of the process */ getProcType()466 virtual AlpsProcessType getProcType() const 467 { return AlpsProcessTypeSerial; } /* Default is serial */ 468 469 /// @name Query and set node index 470 //@{ 471 /** Query the next index assigned to a newly created node, and then 472 increment the nextIndex_ by 1. */ nextNodeIndex()473 AlpsNodeIndex_t nextNodeIndex() { return nextIndex_++; } 474 /** Query the next index assigned to a newly created node. */ getNextNodeIndex()475 AlpsNodeIndex_t getNextNodeIndex() const { return nextIndex_; } 476 /** Set nextIndex_. */ setNextNodeIndex(AlpsNodeIndex_t s)477 void setNextNodeIndex(AlpsNodeIndex_t s) { nextIndex_ = s; } 478 /** Queriy the upper bound of node indices. */ getMaxNodeIndex()479 AlpsNodeIndex_t getMaxNodeIndex() const { return maxIndex_; } 480 /** Set the upper bound of node indices. */ setMaxNodeIndex(AlpsNodeIndex_t s)481 void setMaxNodeIndex(AlpsNodeIndex_t s) { maxIndex_ = s; } 482 //@} 483 484 /// @name Query and set comparision 485 //@{ getSubTreeSelection()486 AlpsSearchStrategy<AlpsSubTree*>* getSubTreeSelection() const { 487 return treeSelection_; 488 } setSubTreeSelection(AlpsSearchStrategy<AlpsSubTree * > * tc)489 void setSubTreeSelection(AlpsSearchStrategy<AlpsSubTree*>* tc) { 490 if (treeSelection_) delete treeSelection_; 491 treeSelection_ = tc; 492 subTreePool_->setComparison(*treeSelection_); 493 } getNodeSelection()494 AlpsSearchStrategy<AlpsTreeNode*>* getNodeSelection() const { 495 return nodeSelection_; 496 } setNodeSelection(AlpsSearchStrategy<AlpsTreeNode * > * nc)497 void setNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) { 498 if (nodeSelection_) delete nodeSelection_; 499 nodeSelection_ = nc; 500 } getRampUpNodeSelection()501 AlpsSearchStrategy<AlpsTreeNode*>* getRampUpNodeSelection() const { 502 return rampUpNodeSelection_; 503 } setRampUpNodeSelection(AlpsSearchStrategy<AlpsTreeNode * > * nc)504 void setRampUpNodeSelection(AlpsSearchStrategy<AlpsTreeNode*>* nc) { 505 if (rampUpNodeSelection_) delete rampUpNodeSelection_; 506 rampUpNodeSelection_ = nc; 507 } 508 //@} 509 510 ///@name Message and log file handling 511 //@{ 512 /** Pass in Message handler (not deleted at end). */ 513 void passInMessageHandler(CoinMessageHandler * handler); 514 /** Set language. */ 515 void newLanguage(CoinMessages::Language language); setLanguage(CoinMessages::Language language)516 void setLanguage(CoinMessages::Language language) 517 { newLanguage(language); } 518 /** Return handler. */ messageHandler()519 CoinMessageHandler * messageHandler() const { return handler_; } 520 /** Return messages. */ messages()521 CoinMessages messages() { return messages_; } 522 /** Return pointer to messages. */ messagesPointer()523 CoinMessages * messagesPointer() { return &messages_; } 524 /** Return msg level. */ getMsgLevel()525 int getMsgLevel() { return msgLevel_; } 526 /** Return msg level. */ getHubMsgLevel()527 int getHubMsgLevel() { return hubMsgLevel_; } 528 /** Return msg level. */ getMasterMsgLevel()529 int getMasterMsgLevel() { return workerMsgLevel_; } 530 /** Return log file level. */ getlogFileLevel()531 int getlogFileLevel() { return logFileLevel_; } 532 /** Get times that node log has been printed */ getNumNodeLog()533 int getNumNodeLog() const { return numNodeLog_; } 534 /** Get times that node log has been printed */ setNumNodeLog(int num)535 void setNumNodeLog(int num) { numNodeLog_ = num; } 536 //@} 537 538 private: 539 AlpsKnowledgeBroker(const AlpsKnowledgeBroker&); 540 AlpsKnowledgeBroker& operator=(const AlpsKnowledgeBroker&); 541 }; 542 #endif 543