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 Alps_h_ 28 #define Alps_h_ 29 30 #include <cfloat> 31 #include <cstdio> 32 33 #include "AlpsConfig.h" 34 #include "CoinFinite.hpp" 35 36 37 //! \page handle MyPage 38 39 /*! \mainpage 40 41 Description here is a brief introduction to Abstract Library for Parallel 42 tree Search (Alps). For theoretical details of parallel tree search see 43 44 <ul> 45 46 <li> <a href="http://coral.ie.lehigh.edu/~ted/files/papers/JSC02.pdf"> A 47 Library Hierarchy for Implementing Scalable Parallel Search Algorithms</a> 48 49 <li> <a href="http://coral.ie.lehigh.edu/~ted/files/papers/ALPS04.pdf"> ALPS: 50 A Framework for Implementing Parallel Search Algorithms</a> 51 52 <li> <a href="http://coral.ie.lehigh.edu/~ted/files/papers/CHiPPS-Rev.pdf"> 53 Computational Experience with a Software Framework for Parallel Integer 54 Programming</a> 55 56 <li> <a 57 href="http://coral.ie.lehigh.edu/~ted/files/papers/YanXuDissertation07.pdf">Yan 58 Xu's dissertation</a>. 59 60 </ul> 61 62 Documentation here can be considered as a condensed summary of all the work 63 listed. It is also more focused in the implementation of the ideas presented 64 in the listed publications. 65 66 67 ## Alps Design 68 69 Alps is designed to conduct parallel tree search. It is an abstract library 70 for this purpose, i.e., it does not assume much (hence flexible) on the tree 71 search problem of its user. Any tree search problem can be implemented as an 72 application on top of the Alps, ie. DFS, BFS, Dijkstra's algorithm or Branch 73 and Bound search for discrete optimization problems. 74 75 ### Task granularity 76 77 A basic unit of work in ALPS is an entire subtree. This means that each 78 worker is capable of processing an entire subtree autonomously. Each broker 79 is responsible for tracking a list of subtrees that it is responsible 80 for. The hub broker dispenses new candidate nodes (leaves of one of the 81 subtrees it is responsible for) to the workers (worker broker receives it) as 82 needed and track their progress. When a worker receives a new node, it treats 83 this node as the root of a subtree and begins processing that subtree, 84 stopping only when the work is completed or the hub broker instructs it to 85 stop. Periodically, the worker informs the hub broker of its progress. 86 87 ### Asynchronous messaging 88 89 ### Building Apps 90 91 A tree search can be abstracted as defining the following, 92 93 <ul> 94 <li> representing problem in a form of data (#AlpsModel), 95 <li> representing nodes in some of data (#AlpsNodeDesc), 96 <li> processing a node (AlpsTreeNode::process), 97 <li> which node to process next, 98 <li> creating of new nodes from a given one (AlpsTreeNode::branch, 99 AlpsTreeNode::createNewTreeNode), 100 <li> a solution and its quality (#AlpsSolution). 101 </ul> 102 103 To define these, user need to inherit corresponding Alps classes and implement 104 related virtual functions, given in the paranthesis. Once these are 105 defined Alps has different strategies to cary the search related tasks, which 106 node to process next, which node to branch, etc. 107 108 Alps comes with two examples, Abc and Knap. Abc is a branch and cut solver, 109 Knap is a knapsack solver. Both of them are implemented on top of Alps, where 110 Alps carries a classical branch and bound/cut type of search to find optimal 111 solutions. 112 113 ## How does parallel search work? 114 115 For parallel search to work, user should implement encode/decode virtual 116 functions in the corresponding user types, 117 118 <ul> 119 <li> model inherited from #AlpsModel, 120 <li> node, inherited from #AlpsTreeNode, 121 <li> node description, inherited from #AlpsNodeDesc, 122 <li> solution, inherited from #AlpsSolution. 123 </ul> 124 125 #AlpsNodeDesc holds subproblem data specific to the node, tree node has other 126 infromation related to tree search (index, depth, branching 127 info). AlpsTreeNode::desc_ is of type #AlpsNodeDesc and keeps the problem 128 data of the node. This design is intended to keep problem data separated from 129 the node data related to tree search. It is for convenience. 130 131 #AlpsModel, #AlpsTreeNode and #AlpsSolution all have #AlpsKnowledge as a base 132 class. Instances of these classes are considered as knowledges generated 133 during a search for the optimal solution and they are traded between 134 different processors. 135 136 All #AlpsModel, #AlpsTreeNode, #AlpsNodeDesc and #AlpsSolution have virtual 137 encode() and decode() funtions. Corresponding sub-classes of user app should 138 implement these virtual functions. encode() function encodes the object into 139 an #AlpsEncoded object. decode() function decodes information from a given 140 #AlpsEncoded object. Alps knowledge brokers sends/receives these #AlpsEncoded 141 instances. 142 143 Each processor has an AlpsKnowledgeBroker instance responsible with 144 coordinating search with other processors' brokers. 145 146 ## Ideas for future 147 Each #AlpsKnowledge instance has a pointer that points to its broker. 148 149 Knowledge broker should be able to follow created knowledges. In current 150 design user apps can create knowledges in TreeNode::branch() functions. Do we 151 want that? 152 153 What about a mechanism where user app requests broker to create a new 154 AlpsKnowledge object and then fills the data. This way knowledge broker can 155 keep an account of the knowledges created. 156 157 ## Fix 158 159 AlpsKnowledgeBroker::getBestNode returns the most promising node, i.e. best 160 quality node. AlpsKnowledgeBroker::getBestQuality() returns to the quality of 161 the best solution found (quality of incumbent solution). This should be 162 fixed. Moreover AlpsKnowledgeBroker::getBestNode does a search to locate the 163 best node, this is not necessary and should be fixed (just update the best 164 node whenever new nodes are created). 165 166 */ 167 168 //############################################################################# 169 170 #if defined(__linux__) 171 #define ALPS_MEMORY_USAGE 1 172 #endif 173 174 typedef int AlpsNodeIndex_t; 175 176 //############################################################################# 177 /** The possible values for clock type. */ 178 //############################################################################# 179 180 enum AlpsClockType { 181 AlpsClockTypeCpu, 182 AlpsClockTypeWallClock 183 }; 184 185 //############################################################################# 186 /** The possible values for static load balancing scheme. */ 187 //############################################################################# 188 189 enum AlpsStaticBalanceScheme { 190 AlpsRootInit = 0, 191 AlpsSpiral 192 }; 193 194 //############################################################################# 195 /** The possible stati for the search nodes. */ 196 //############################################################################# 197 198 enum AlpsNodeStatus { 199 AlpsNodeStatusCandidate, 200 AlpsNodeStatusEvaluated, 201 AlpsNodeStatusPregnant, 202 AlpsNodeStatusBranched, 203 AlpsNodeStatusFathomed, 204 AlpsNodeStatusDiscarded 205 }; 206 207 //############################################################################# 208 /** Search Strategies. */ 209 //############################################################################# 210 211 enum AlpsSearchType { 212 AlpsSearchTypeBestFirst = 0, 213 AlpsSearchTypeBreadthFirst, 214 AlpsSearchTypeDepthFirst, 215 AlpsSearchTypeBestEstimate, 216 AlpsSearchTypeHybrid 217 }; 218 219 //############################################################################# 220 /** Type of knowledge like solution, node, cut...*/ 221 //############################################################################# 222 223 enum AlpsKnowledgeType{ 224 AlpsKnowledgeTypeModel = 0, 225 AlpsKnowledgeTypeModelGen, 226 AlpsKnowledgeTypeNode, 227 AlpsKnowledgeTypeNodeDesc, 228 AlpsKnowledgeTypeSolution, 229 AlpsKnowledgeTypeSubTree, 230 AlpsKnowledgeTypeUndefined 231 }; 232 233 enum AlpsKnowledgePoolType{ 234 AlpsKnowledgePoolTypeNode = 0, 235 AlpsKnowledgePoolTypeSolution, 236 AlpsKnowledgePoolTypeSubTree, 237 AlpsKnowledgePoolTypeUndefined 238 }; 239 240 //############################################################################# 241 // Search return status 242 //############################################################################# 243 244 enum AlpsExitStatus { 245 AlpsExitStatusUnknown = -1, 246 AlpsExitStatusOptimal, 247 AlpsExitStatusTimeLimit, 248 AlpsExitStatusNodeLimit, 249 AlpsExitStatusSolLimit, 250 AlpsExitStatusFeasible, 251 AlpsExitStatusInfeasible, 252 AlpsExitStatusNoMemory, 253 AlpsExitStatusFailed, 254 AlpsExitStatusUnbounded 255 }; 256 257 //############################################################################# 258 // Return code. 259 //############################################################################# 260 261 enum AlpsReturnStatus { 262 AlpsReturnStatusOk = 0, 263 AlpsReturnStatusErr, 264 AlpsReturnStatusErrNoInt, /* No integer variable.*/ 265 AlpsReturnStatusErrNoMem 266 }; 267 268 //############################################################################# 269 // Seach phase 270 //############################################################################# 271 272 enum AlpsPhase { 273 AlpsPhaseRampup = 0, 274 AlpsPhaseSearch, 275 AlpasPhaseRampdown 276 }; 277 278 #define ALPS_NODE_PROCESS_TIME 0.0123 279 #define ALPS_NONE 0 280 #define ALPS_NOT_SET -1 281 282 //############################################################################# 283 // Big number 284 //############################################################################# 285 286 #define ALPS_DBL_MAX COIN_DBL_MAX 287 #define ALPS_INC_MAX 1.0e80 288 #define ALPS_OBJ_MAX 1.0e75 289 #define ALPS_OBJ_MAX_LESS 1.0e70 290 #define ALPS_BND_MAX 1.0e20 291 #define ALPS_INFINITY 1.0e20 292 293 #define ALPS_INT_MAX COIN_INT_MAX 294 295 //############################################################################# 296 // Small number 297 //############################################################################# 298 299 #define ALPS_ZERO 1.0e-14 300 #define ALPS_GEN_TOL 1.0e-6 301 #define ALPS_QUALITY_TOL 1.0e-5 302 #define ALPS_SMALL_3 1.0e-3 303 #define ALPS_SMALL_4 1.0e-4 304 #define ALPS_SMALL_5 1.0e-5 305 306 //############################################################################# 307 308 #define ALPS_PRINTF printf 309 310 #define ALPS_DMSG printf 311 312 313 //############################################################################# 314 315 #define ALPS_MAX( x, y ) ( ( (x) > (y) ) ? (x) : (y) ) 316 #define ALPS_MIN( x, y ) ( ( (x) < (y) ) ? (x) : (y) ) 317 #define ALPS_FABS(x) ( (x < 0.0) ? -(x) : (x) ) 318 #define ALPS_ABS(x) ( (x < 0) ? -(x) : (x) ) 319 320 //############################################################################# 321 322 typedef struct ALPS_PS_STATS 323 { 324 int qualityBalance_; 325 int quantityBalance_; 326 int interBalance_; 327 int intraBalance_; 328 int workerAsk_; 329 int donateSuccess_; 330 int donateFail_; 331 int subtreeSplit_; 332 int subtreeWhole_; 333 int subtreeChange_; 334 } AlpsPsStats; 335 336 //############################################################################# 337 338 339 #endif 340