1 /* $Id$ */ 2 // Copyright (C) 2004, International Business Machines 3 // Corporation and others. All Rights Reserved. 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 6 #ifndef CbcTree_H 7 #define CbcTree_H 8 9 #include <vector> 10 #include <algorithm> 11 #include <cmath> 12 13 #include "CoinHelperFunctions.hpp" 14 #include "CbcCompare.hpp" 15 16 /*! \brief Using MS heap implementation 17 18 It's unclear if this is needed any longer, or even if it should be allowed. 19 Cbc occasionally tries to do things to the tree (typically tweaking the 20 comparison predicate) that can cause a violation of the heap property (parent better 21 than either child). In a debug build, Microsoft's heap implementation does checks that 22 detect this and fail. This symbol switched to an alternate implementation of CbcTree, 23 and there are clearly differences, but no explanation as to why or what for. 24 25 As of 100921, the code is cleaned up to make it through `cbc -unitTest' without 26 triggering `Invalid heap' in an MSVS debug build. The method validateHeap() can 27 be used for debugging if this turns up again. 28 */ 29 //#define CBC_DUBIOUS_HEAP 30 #if defined(_MSC_VER) || defined(__MNO_CYGWIN) 31 //#define CBC_DUBIOUS_HEAP 32 #endif 33 #if 1 //ndef CBC_DUBIOUS_HEAP 34 35 /*! \brief Controls search tree debugging 36 37 In order to have validateHeap() available, set CBC_DEBUG_HEAP 38 to 1 or higher. 39 40 - 1 calls validateHeap() after each change to the heap 41 - 2 will print a line for major operations (clean, set comparison, etc.) 42 - 3 will print information about each push and pop 43 44 #define CBC_DEBUG_HEAP 1 45 */ 46 47 /*! \class CbcTree 48 \brief Implementation of the live set as a heap. 49 50 This class is used to hold the set of live nodes in the search tree. 51 */ 52 class CbcTree { 53 54 public: 55 /*! \name Constructors and related */ 56 //@{ 57 /// Default Constructor 58 CbcTree(); 59 60 /// Copy constructor 61 CbcTree(const CbcTree &rhs); 62 63 /// = operator 64 CbcTree &operator=(const CbcTree &rhs); 65 66 /// Destructor 67 virtual ~CbcTree(); 68 69 /// Clone 70 virtual CbcTree *clone() const; 71 72 /// Create C++ lines to get to current state generateCpp(FILE *)73 virtual void generateCpp(FILE *) {} 74 //@} 75 76 /*! \name Heap access and maintenance methods */ 77 //@{ 78 /// Set comparison function and resort heap 79 void setComparison(CbcCompareBase &compare); 80 81 /// Return the top node of the heap 82 virtual CbcNode *top() const; 83 84 /// Add a node to the heap 85 virtual void push(CbcNode *x); 86 87 /// Remove the top node from the heap 88 virtual void pop(); 89 90 /*! \brief Gets best node and takes off heap 91 92 Before returning the node from the top of the heap, the node 93 is offered an opportunity to reevaluate itself. Callers should 94 be prepared to check that the node returned is suitable for use. 95 */ 96 virtual CbcNode *bestNode(double cutoff); 97 98 /*! \brief Rebuild the heap */ 99 virtual void rebuild(); 100 //@} 101 102 /*! \name Direct node access methods */ 103 //@{ 104 /// Test for an empty tree 105 virtual bool empty(); 106 107 /// Return size size() const108 virtual int size() const { return static_cast< int >(nodes_.size()); } 109 110 /// Return a node pointer operator [](int i) const111 inline CbcNode *operator[](int i) const { return nodes_[i]; } 112 113 /// Return a node pointer nodePointer(int i) const114 inline CbcNode *nodePointer(int i) const { return nodes_[i]; } 115 void realpop(); 116 /** After changing data in the top node, fix the heap */ 117 void fixTop(); 118 void realpush(CbcNode *node); 119 //@} 120 121 /*! \name Search tree maintenance */ 122 //@{ 123 /*! \brief Prune the tree using an objective function cutoff 124 125 This routine removes all nodes with objective worse than the 126 specified cutoff value. It also sets bestPossibleObjective to 127 the best objective over remaining nodes. 128 */ 129 virtual void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective); 130 131 /// Get best on list using alternate method 132 CbcNode *bestAlternate(); 133 134 /// We may have got an intelligent tree so give it one more chance endSearch()135 virtual void endSearch() {} 136 137 /// Get best possible objective function in the tree 138 virtual double getBestPossibleObjective(); 139 140 /// Reset maximum node number resetNodeNumbers()141 inline void resetNodeNumbers() { maximumNodeNumber_ = 0; } 142 143 /// Get maximum node number maximumNodeNumber() const144 inline int maximumNodeNumber() const { return maximumNodeNumber_; } 145 146 /// Set number of branches setNumberBranching(int value)147 inline void setNumberBranching(int value) { numberBranching_ = value; } 148 149 /// Get number of branches getNumberBranching() const150 inline int getNumberBranching() const { return numberBranching_; } 151 152 /// Set maximum branches setMaximumBranching(int value)153 inline void setMaximumBranching(int value) { maximumBranching_ = value; } 154 155 /// Get maximum branches getMaximumBranching() const156 inline int getMaximumBranching() const { return maximumBranching_; } 157 158 /// Get branched variables branched() const159 inline unsigned int *branched() const { return branched_; } 160 161 /// Get bounds newBounds() const162 inline int *newBounds() const { return newBound_; } 163 164 /// Last objective in branch-and-cut search tree lastObjective() const165 inline double lastObjective() const 166 { 167 return lastObjective_; 168 } 169 /// Last depth in branch-and-cut search tree lastDepth() const170 inline int lastDepth() const 171 { 172 return lastDepth_; 173 } 174 /// Last number of objects unsatisfied lastUnsatisfied() const175 inline int lastUnsatisfied() const 176 { 177 return lastUnsatisfied_; 178 } 179 /// Adds branching information to complete state 180 void addBranchingInformation(const CbcModel *model, const CbcNodeInfo *nodeInfo, 181 const double *currentLower, 182 const double *currentUpper); 183 /// Increase space for data 184 void increaseSpace(); 185 //@} 186 187 #if CBC_DEBUG_HEAP > 0 188 /*! \name Debugging methods */ 189 //@{ 190 /*! \brief Check that the heap property is satisfied. */ 191 void validateHeap(); 192 //@} 193 #endif 194 195 protected: 196 /// Storage vector for the heap 197 std::vector< CbcNode * > nodes_; 198 /// Sort predicate for heap ordering. 199 CbcCompare comparison_; 200 /// Maximum "node" number so far to split ties 201 int maximumNodeNumber_; 202 /// Size of variable list 203 int numberBranching_; 204 /// Maximum size of variable list 205 int maximumBranching_; 206 /// Objective of last node pushed on tree 207 double lastObjective_; 208 /// Depth of last node pushed on tree 209 int lastDepth_; 210 /// Number unsatisfied of last node pushed on tree 211 int lastUnsatisfied_; 212 /** Integer variables branched or bounded 213 top bit set if new upper bound 214 next bit set if a branch 215 */ 216 unsigned int *branched_; 217 /// New bound 218 int *newBound_; 219 }; 220 221 #ifdef JJF_ZERO // not used 222 /*! \brief Implementation of live set as a managed array. 223 224 This class is used to hold the set of live nodes in the search tree. 225 */ 226 class CbcTreeArray : public CbcTree { 227 228 public: 229 // Default Constructor 230 CbcTreeArray(); 231 232 // Copy constructor 233 CbcTreeArray(const CbcTreeArray &rhs); 234 // = operator 235 CbcTreeArray &operator=(const CbcTreeArray &rhs); 236 237 virtual ~CbcTreeArray(); 238 239 /// Clone 240 virtual CbcTree *clone() const; 241 /// Create C++ lines to get to current state generateCpp(FILE *)242 virtual void generateCpp(FILE *) {} 243 244 /*! \name Heap access and maintenance methods */ 245 //@{ 246 247 /// Set comparison function and resort heap 248 void setComparison(CbcCompareBase &compare); 249 250 /// Add a node to the heap 251 virtual void push(CbcNode *x); 252 253 /// Gets best node and takes off heap 254 virtual CbcNode *bestNode(double cutoff); 255 256 //@} 257 /*! \name vector methods */ 258 //@{ 259 260 /// Test if empty *** note may be overridden 261 virtual bool empty(); 262 263 //@} 264 265 /*! \name Search tree maintenance */ 266 //@{ 267 268 /*! \brief Prune the tree using an objective function cutoff 269 270 This routine removes all nodes with objective worst than the 271 specified cutoff value. 272 It also sets bestPossibleObjective to best 273 of all on tree before deleting. 274 */ 275 276 void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective); 277 /// Get best possible objective function in the tree 278 virtual double getBestPossibleObjective(); 279 //@} 280 protected: 281 /// Returns 282 /// Last node 283 CbcNode *lastNode_; 284 /// Last node popped 285 CbcNode *lastNodePopped_; 286 /// Not used yet 287 int switches_; 288 }; 289 290 /// New style 291 #include "CoinSearchTree.hpp" 292 /*! \class tree 293 \brief Implementation of live set as a heap. 294 295 This class is used to hold the set of live nodes in the search tree. 296 */ 297 298 class CbcNewTree : public CbcTree, public CoinSearchTreeManager { 299 300 public: 301 // Default Constructor 302 CbcNewTree(); 303 304 // Copy constructor 305 CbcNewTree(const CbcNewTree &rhs); 306 // = operator 307 CbcNewTree &operator=(const CbcNewTree &rhs); 308 309 virtual ~CbcNewTree(); 310 311 /// Clone 312 virtual CbcNewTree *clone() const; 313 /// Create C++ lines to get to current state generateCpp(FILE *)314 virtual void generateCpp(FILE *) {} 315 316 /*! \name Heap access and maintenance methods */ 317 //@{ 318 319 /// Set comparison function and resort heap 320 void setComparison(CbcCompareBase &compare); 321 322 /// Return the top node of the heap 323 virtual CbcNode *top() const; 324 325 /// Add a node to the heap 326 virtual void push(CbcNode *x); 327 328 /// Remove the top node from the heap 329 virtual void pop(); 330 /// Gets best node and takes off heap 331 virtual CbcNode *bestNode(double cutoff); 332 333 //@} 334 /*! \name vector methods */ 335 //@{ 336 337 /// Test if empty *** note may be overridden 338 virtual bool empty(); 339 340 /// Return size size() const341 inline int size() const 342 { 343 return nodes_.size(); 344 } 345 346 /// [] operator operator [](int i) const347 inline CbcNode *operator[](int i) const 348 { 349 return nodes_[i]; 350 } 351 352 /// Return a node pointer nodePointer(int i) const353 inline CbcNode *nodePointer(int i) const 354 { 355 return nodes_[i]; 356 } 357 358 //@} 359 360 /*! \name Search tree maintenance */ 361 //@{ 362 363 /*! \brief Prune the tree using an objective function cutoff 364 365 This routine removes all nodes with objective worst than the 366 specified cutoff value. 367 It also sets bestPossibleObjective to best 368 of all on tree before deleting. 369 */ 370 371 void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective); 372 373 /// Get best on list using alternate method 374 CbcNode *bestAlternate(); 375 376 /// We may have got an intelligent tree so give it one more chance endSearch()377 virtual void endSearch() {} 378 //@} 379 protected: 380 }; 381 #endif 382 #else 383 /* CBC_DUBIOUS_HEAP is defined 384 385 See note at top of file. This code is highly suspect. 386 -- lh, 100921 -- 387 */ 388 class CbcTree { 389 390 public: 391 // Default Constructor 392 CbcTree(); 393 394 // Copy constructor 395 CbcTree(const CbcTree &rhs); 396 // = operator 397 CbcTree &operator=(const CbcTree &rhs); 398 399 virtual ~CbcTree(); 400 401 /// Clone 402 virtual CbcTree *clone() const; 403 /// Create C++ lines to get to current state generateCpp(FILE * fp)404 virtual void generateCpp(FILE *fp) {} 405 406 /*! \name Heap access and maintenance methods */ 407 //@{ 408 409 /// Set comparison function and resort heap 410 void setComparison(CbcCompareBase &compare); 411 412 /// Return the top node of the heap 413 virtual CbcNode *top() const; 414 415 /// Add a node to the heap 416 virtual void push(CbcNode *x); 417 418 /// Remove the top node from the heap 419 virtual void pop(); 420 /// Gets best node and takes off heap 421 virtual CbcNode *bestNode(double cutoff); 422 423 //@} 424 /*! \name vector methods */ 425 //@{ 426 427 /// Test if empty *** note may be overridden 428 //virtual bool empty() ; 429 430 /// Return size size() const431 inline int size() const 432 { 433 return nodes_.size(); 434 } 435 436 /// [] operator operator [](int i) const437 inline CbcNode *operator[](int i) const 438 { 439 return nodes_[i]; 440 } 441 442 /// Return a node pointer nodePointer(int i) const443 inline CbcNode *nodePointer(int i) const 444 { 445 return nodes_[i]; 446 } 447 448 virtual bool empty(); 449 //inline int size() const { return size_; } 450 void realpop(); 451 /** After changing data in the top node, fix the heap */ 452 void fixTop(); 453 void realpush(CbcNode *node); 454 //@} 455 456 /*! \name Search tree maintenance */ 457 //@{ 458 459 /*! \brief Prune the tree using an objective function cutoff 460 461 This routine removes all nodes with objective worst than the 462 specified cutoff value. 463 It also sets bestPossibleObjective to best 464 of all on tree before deleting. 465 */ 466 467 void cleanTree(CbcModel *model, double cutoff, double &bestPossibleObjective); 468 469 /// Get best on list using alternate method 470 CbcNode *bestAlternate(); 471 472 /// We may have got an intelligent tree so give it one more chance endSearch()473 virtual void endSearch() {} 474 /// Reset maximum node number resetNodeNumbers()475 inline void resetNodeNumbers() 476 { 477 maximumNodeNumber_ = 0; 478 } 479 480 /// Get maximum node number maximumNodeNumber() const481 inline int maximumNodeNumber() const { return maximumNodeNumber_; } 482 //@} 483 protected: 484 std::vector< CbcNode * > nodes_; 485 CbcCompare comparison_; ///> Sort function for heap ordering. 486 /// Maximum "node" number so far to split ties 487 int maximumNodeNumber_; 488 }; 489 #endif 490 #endif 491 492 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 493 */ 494