1 /* $Id: CoinSearchTree.hpp 2083 2019-01-06 19:38:09Z unxusr $ */ 2 // Copyright (C) 2006, 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 CoinSearchTree_H 7 #define CoinSearchTree_H 8 9 #include <vector> 10 #include <algorithm> 11 #include <cmath> 12 #include <string> 13 14 #include "CoinFinite.hpp" 15 #include "CoinHelperFunctions.hpp" 16 17 // #define DEBUG_PRINT 18 19 //############################################################################# 20 21 class BitVector128 { 22 friend bool operator<(const BitVector128 &b0, const BitVector128 &b1); 23 24 private: 25 unsigned int bits_[4]; 26 27 public: 28 BitVector128(); 29 BitVector128(unsigned int bits[4]); ~BitVector128()30 ~BitVector128() {} 31 void set(unsigned int bits[4]); 32 void setBit(int i); 33 void clearBit(int i); 34 std::string str() const; 35 }; 36 37 bool operator<(const BitVector128 &b0, const BitVector128 &b1); 38 39 //############################################################################# 40 41 /** A class from which the real tree nodes should be derived from. Some of the 42 data that undoubtedly exist in the real tree node is replicated here for 43 fast access. This class is used in the various comparison functions. */ 44 class CoinTreeNode { 45 protected: CoinTreeNode()46 CoinTreeNode() 47 : depth_(-1) 48 , fractionality_(-1) 49 , quality_(-COIN_DBL_MAX) 50 , true_lower_bound_(-COIN_DBL_MAX) 51 , preferred_() 52 { 53 } CoinTreeNode(int d,int f=-1,double q=-COIN_DBL_MAX,double tlb=-COIN_DBL_MAX,BitVector128 p=BitVector128 ())54 CoinTreeNode(int d, 55 int f = -1, 56 double q = -COIN_DBL_MAX, 57 double tlb = -COIN_DBL_MAX, 58 BitVector128 p = BitVector128()) 59 : depth_(d) 60 , fractionality_(f) 61 , quality_(q) 62 , true_lower_bound_(tlb) 63 , preferred_(p) 64 { 65 } CoinTreeNode(const CoinTreeNode & x)66 CoinTreeNode(const CoinTreeNode &x) 67 : depth_(x.depth_) 68 , fractionality_(x.fractionality_) 69 , quality_(x.quality_) 70 , true_lower_bound_(x.true_lower_bound_) 71 , preferred_(x.preferred_) 72 { 73 } operator =(const CoinTreeNode & x)74 CoinTreeNode &operator=(const CoinTreeNode &x) 75 { 76 if (this != &x) { 77 depth_ = x.depth_; 78 fractionality_ = x.fractionality_; 79 quality_ = x.quality_; 80 true_lower_bound_ = x.true_lower_bound_; 81 preferred_ = x.preferred_; 82 } 83 return *this; 84 } 85 86 private: 87 /// The depth of the node in the tree 88 int depth_; 89 /** A measure of fractionality, e.g., the number of unsatisfied 90 integrality requirements */ 91 int fractionality_; 92 /** Some quality for the node. For normal branch-and-cut problems the LP 93 relaxation value will do just fine. It is probably an OK approximation 94 even if column generation is done. */ 95 double quality_; 96 /** A true lower bound on the node. May be -infinity. For normal 97 branch-and-cut problems the LP relaxation value is OK. It is different 98 when column generation is done. */ 99 double true_lower_bound_; 100 /** */ 101 BitVector128 preferred_; 102 103 public: ~CoinTreeNode()104 virtual ~CoinTreeNode() {} 105 getDepth() const106 inline int getDepth() const { return depth_; } getFractionality() const107 inline int getFractionality() const { return fractionality_; } getQuality() const108 inline double getQuality() const { return quality_; } getTrueLB() const109 inline double getTrueLB() const { return true_lower_bound_; } getPreferred() const110 inline BitVector128 getPreferred() const { return preferred_; } 111 setDepth(int d)112 inline void setDepth(int d) { depth_ = d; } setFractionality(int f)113 inline void setFractionality(int f) { fractionality_ = f; } setQuality(double q)114 inline void setQuality(double q) { quality_ = q; } setTrueLB(double tlb)115 inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; } setPreferred(BitVector128 p)116 inline void setPreferred(BitVector128 p) { preferred_ = p; } 117 }; 118 119 //============================================================================== 120 121 class CoinTreeSiblings { 122 private: 123 CoinTreeSiblings(); 124 CoinTreeSiblings &operator=(const CoinTreeSiblings &); 125 126 private: 127 int current_; 128 int numSiblings_; 129 CoinTreeNode **siblings_; 130 131 public: CoinTreeSiblings(const int n,CoinTreeNode ** nodes)132 CoinTreeSiblings(const int n, CoinTreeNode **nodes) 133 : current_(0) 134 , numSiblings_(n) 135 , siblings_(new CoinTreeNode *[n]) 136 { 137 CoinDisjointCopyN(nodes, n, siblings_); 138 } CoinTreeSiblings(const CoinTreeSiblings & s)139 CoinTreeSiblings(const CoinTreeSiblings &s) 140 : current_(s.current_) 141 , numSiblings_(s.numSiblings_) 142 , siblings_(new CoinTreeNode *[s.numSiblings_]) 143 { 144 CoinDisjointCopyN(s.siblings_, s.numSiblings_, siblings_); 145 } ~CoinTreeSiblings()146 ~CoinTreeSiblings() { delete[] siblings_; } currentNode() const147 inline CoinTreeNode *currentNode() const { return siblings_[current_]; } 148 /** returns false if cannot be advanced */ advanceNode()149 inline bool advanceNode() { return ++current_ != numSiblings_; } toProcess() const150 inline int toProcess() const { return numSiblings_ - current_; } size() const151 inline int size() const { return numSiblings_; } printPref() const152 inline void printPref() const 153 { 154 for (int i = 0; i < numSiblings_; ++i) { 155 std::string pref = siblings_[i]->getPreferred().str(); 156 printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str()); 157 } 158 } 159 }; 160 161 //############################################################################# 162 163 /** Function objects to compare search tree nodes. The comparison function 164 must return true if the first argument is "better" than the second one, 165 i.e., it should be processed first. */ 166 /*@{*/ 167 /** Depth First Search. */ 168 struct CoinSearchTreeComparePreferred { nameCoinSearchTreeComparePreferred169 static inline const char *name() { return "CoinSearchTreeComparePreferred"; } operator ()CoinSearchTreeComparePreferred170 inline bool operator()(const CoinTreeSiblings *x, 171 const CoinTreeSiblings *y) const 172 { 173 const CoinTreeNode *xNode = x->currentNode(); 174 const CoinTreeNode *yNode = y->currentNode(); 175 const BitVector128 xPref = xNode->getPreferred(); 176 const BitVector128 yPref = yNode->getPreferred(); 177 bool retval = true; 178 if (xPref < yPref) { 179 retval = true; 180 } else if (yPref < xPref) { 181 retval = false; 182 } else { 183 retval = xNode->getQuality() < yNode->getQuality(); 184 } 185 #ifdef DEBUG_PRINT 186 printf("Comparing xpref (%s) and ypref (%s) : %s\n", 187 xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F"); 188 #endif 189 return retval; 190 } 191 }; 192 193 //----------------------------------------------------------------------------- 194 /** Depth First Search. */ 195 struct CoinSearchTreeCompareDepth { nameCoinSearchTreeCompareDepth196 static inline const char *name() { return "CoinSearchTreeCompareDepth"; } operator ()CoinSearchTreeCompareDepth197 inline bool operator()(const CoinTreeSiblings *x, 198 const CoinTreeSiblings *y) const 199 { 200 #if 1 201 return x->currentNode()->getDepth() >= y->currentNode()->getDepth(); 202 #else 203 if (x->currentNode()->getDepth() > y->currentNode()->getDepth()) 204 return 1; 205 if (x->currentNode()->getDepth() == y->currentNode()->getDepth() && x->currentNode()->getQuality() <= y->currentNode()->getQuality()) 206 return 1; 207 return 0; 208 #endif 209 } 210 }; 211 212 //----------------------------------------------------------------------------- 213 /* Breadth First Search */ 214 struct CoinSearchTreeCompareBreadth { nameCoinSearchTreeCompareBreadth215 static inline const char *name() { return "CoinSearchTreeCompareBreadth"; } operator ()CoinSearchTreeCompareBreadth216 inline bool operator()(const CoinTreeSiblings *x, 217 const CoinTreeSiblings *y) const 218 { 219 return x->currentNode()->getDepth() < y->currentNode()->getDepth(); 220 } 221 }; 222 223 //----------------------------------------------------------------------------- 224 /** Best first search */ 225 struct CoinSearchTreeCompareBest { nameCoinSearchTreeCompareBest226 static inline const char *name() { return "CoinSearchTreeCompareBest"; } operator ()CoinSearchTreeCompareBest227 inline bool operator()(const CoinTreeSiblings *x, 228 const CoinTreeSiblings *y) const 229 { 230 return x->currentNode()->getQuality() < y->currentNode()->getQuality(); 231 } 232 }; 233 234 //############################################################################# 235 236 class CoinSearchTreeBase { 237 private: 238 CoinSearchTreeBase(const CoinSearchTreeBase &); 239 CoinSearchTreeBase &operator=(const CoinSearchTreeBase &); 240 241 protected: 242 std::vector< CoinTreeSiblings * > candidateList_; 243 int numInserted_; 244 int size_; 245 246 protected: CoinSearchTreeBase()247 CoinSearchTreeBase() 248 : candidateList_() 249 , numInserted_(0) 250 , size_(0) 251 { 252 } 253 254 virtual void realpop() = 0; 255 virtual void realpush(CoinTreeSiblings *s) = 0; 256 virtual void fixTop() = 0; 257 258 public: ~CoinSearchTreeBase()259 virtual ~CoinSearchTreeBase() {} 260 virtual const char *compName() const = 0; 261 getCandidates() const262 inline const std::vector< CoinTreeSiblings * > &getCandidates() const 263 { 264 return candidateList_; 265 } empty() const266 inline bool empty() const { return candidateList_.empty(); } size() const267 inline int size() const { return size_; } numInserted() const268 inline int numInserted() const { return numInserted_; } top() const269 inline CoinTreeNode *top() const 270 { 271 if (size_ == 0 || candidateList_.size() == 0) 272 return NULL; 273 #ifdef DEBUG_PRINT 274 char output[44]; 275 output[43] = 0; 276 candidateList_.front()->currentNode()->getPreferred().print(output); 277 printf("top's pref: %s\n", output); 278 #endif 279 return candidateList_.front()->currentNode(); 280 } 281 /** pop will advance the \c next pointer among the siblings on the top and 282 then moves the top to its correct position. #realpop is the method 283 that actually removes the element from the heap */ pop()284 inline void pop() 285 { 286 CoinTreeSiblings *s = candidateList_.front(); 287 if (!s->advanceNode()) { 288 realpop(); 289 delete s; 290 } else { 291 fixTop(); 292 } 293 --size_; 294 } push(int numNodes,CoinTreeNode ** nodes,const bool incrInserted=true)295 inline void push(int numNodes, CoinTreeNode **nodes, 296 const bool incrInserted = true) 297 { 298 CoinTreeSiblings *s = new CoinTreeSiblings(numNodes, nodes); 299 realpush(s); 300 if (incrInserted) { 301 numInserted_ += numNodes; 302 } 303 size_ += numNodes; 304 } push(const CoinTreeSiblings & sib,const bool incrInserted=true)305 inline void push(const CoinTreeSiblings &sib, 306 const bool incrInserted = true) 307 { 308 CoinTreeSiblings *s = new CoinTreeSiblings(sib); 309 #ifdef DEBUG_PRINT 310 s->printPref(); 311 #endif 312 realpush(s); 313 if (incrInserted) { 314 numInserted_ += sib.toProcess(); 315 } 316 size_ += sib.toProcess(); 317 } 318 }; 319 320 //############################################################################# 321 322 // #define CAN_TRUST_STL_HEAP 323 #ifdef CAN_TRUST_STL_HEAP 324 325 template < class Comp > 326 class CoinSearchTree : public CoinSearchTreeBase { 327 private: 328 Comp comp_; 329 330 protected: realpop()331 virtual void realpop() 332 { 333 candidateList_.pop_back(); 334 } fixTop()335 virtual void fixTop() 336 { 337 CoinTreeSiblings *s = top(); 338 realpop(); 339 push(s, false); 340 } realpush(CoinTreeSiblings * s)341 virtual void realpush(CoinTreeSiblings *s) 342 { 343 nodes_.push_back(s); 344 std::push_heap(candidateList_.begin(), candidateList_.end(), comp_); 345 } 346 347 public: CoinSearchTree()348 CoinSearchTree() 349 : CoinSearchTreeBase() 350 , comp_() 351 { 352 } CoinSearchTree(const CoinSearchTreeBase & t)353 CoinSearchTree(const CoinSearchTreeBase &t) 354 : CoinSearchTreeBase() 355 , comp_() 356 { 357 candidateList_ = t.getCandidates(); 358 std::make_heap(candidateList_.begin(), candidateList_.end(), comp_); 359 numInserted_ = t.numInserted_; 360 size_ = t.size_; 361 } ~CoinSearchTree()362 ~CoinSearchTree() {} compName() const363 const char *compName() const { return Comp::name(); } 364 }; 365 366 #else 367 368 template < class Comp > 369 class CoinSearchTree : public CoinSearchTreeBase { 370 private: 371 Comp comp_; 372 373 protected: realpop()374 virtual void realpop() 375 { 376 candidateList_[0] = candidateList_.back(); 377 candidateList_.pop_back(); 378 fixTop(); 379 } 380 /** After changing data in the top node, fix the heap */ fixTop()381 virtual void fixTop() 382 { 383 const size_t size = candidateList_.size(); 384 if (size > 1) { 385 CoinTreeSiblings **candidates = &candidateList_[0]; 386 CoinTreeSiblings *s = candidates[0]; 387 --candidates; 388 size_t pos = 1; 389 size_t ch; 390 for (ch = 2; ch < size; pos = ch, ch *= 2) { 391 if (comp_(candidates[ch + 1], candidates[ch])) 392 ++ch; 393 if (comp_(s, candidates[ch])) 394 break; 395 candidates[pos] = candidates[ch]; 396 } 397 if (ch == size) { 398 if (comp_(candidates[ch], s)) { 399 candidates[pos] = candidates[ch]; 400 pos = ch; 401 } 402 } 403 candidates[pos] = s; 404 } 405 } realpush(CoinTreeSiblings * s)406 virtual void realpush(CoinTreeSiblings *s) 407 { 408 candidateList_.push_back(s); 409 CoinTreeSiblings **candidates = &candidateList_[0]; 410 --candidates; 411 size_t pos = candidateList_.size(); 412 size_t ch; 413 for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) { 414 if (comp_(candidates[ch], s)) 415 break; 416 candidates[pos] = candidates[ch]; 417 } 418 candidates[pos] = s; 419 } 420 421 public: CoinSearchTree()422 CoinSearchTree() 423 : CoinSearchTreeBase() 424 , comp_() 425 { 426 } CoinSearchTree(const CoinSearchTreeBase & t)427 CoinSearchTree(const CoinSearchTreeBase &t) 428 : CoinSearchTreeBase() 429 , comp_() 430 { 431 candidateList_ = t.getCandidates(); 432 std::sort(candidateList_.begin(), candidateList_.end(), comp_); 433 numInserted_ = t.numInserted(); 434 size_ = t.size(); 435 } ~CoinSearchTree()436 virtual ~CoinSearchTree() {} compName() const437 const char *compName() const { return Comp::name(); } 438 }; 439 440 #endif 441 442 //############################################################################# 443 444 enum CoinNodeAction { 445 CoinAddNodeToCandidates, 446 CoinTestNodeForDiving, 447 CoinDiveIntoNode 448 }; 449 450 class CoinSearchTreeManager { 451 private: 452 CoinSearchTreeManager(const CoinSearchTreeManager &); 453 CoinSearchTreeManager &operator=(const CoinSearchTreeManager &); 454 455 private: 456 CoinSearchTreeBase *candidates_; 457 int numSolution; 458 /** Whether there is an upper bound or not. The upper bound may have come 459 as input, not necessarily from a solution */ 460 bool hasUB_; 461 462 /** variable used to test whether we need to reevaluate search strategy */ 463 bool recentlyReevaluatedSearchStrategy_; 464 465 public: CoinSearchTreeManager()466 CoinSearchTreeManager() 467 : candidates_(NULL) 468 , numSolution(0) 469 , recentlyReevaluatedSearchStrategy_(true) 470 { 471 } ~CoinSearchTreeManager()472 virtual ~CoinSearchTreeManager() 473 { 474 delete candidates_; 475 } 476 setTree(CoinSearchTreeBase * t)477 inline void setTree(CoinSearchTreeBase *t) 478 { 479 delete candidates_; 480 candidates_ = t; 481 } getTree() const482 inline CoinSearchTreeBase *getTree() const 483 { 484 return candidates_; 485 } 486 empty() const487 inline bool empty() const { return candidates_->empty(); } size() const488 inline size_t size() const { return candidates_->size(); } numInserted() const489 inline size_t numInserted() const { return candidates_->numInserted(); } top() const490 inline CoinTreeNode *top() const { return candidates_->top(); } pop()491 inline void pop() { candidates_->pop(); } push(CoinTreeNode * node,const bool incrInserted=true)492 inline void push(CoinTreeNode *node, const bool incrInserted = true) 493 { 494 candidates_->push(1, &node, incrInserted); 495 } push(const CoinTreeSiblings & s,const bool incrInserted=true)496 inline void push(const CoinTreeSiblings &s, const bool incrInserted = true) 497 { 498 candidates_->push(s, incrInserted); 499 } push(const int n,CoinTreeNode ** nodes,const bool incrInserted=true)500 inline void push(const int n, CoinTreeNode **nodes, 501 const bool incrInserted = true) 502 { 503 candidates_->push(n, nodes, incrInserted); 504 } 505 bestQualityCandidate() const506 inline CoinTreeNode *bestQualityCandidate() const 507 { 508 return candidates_->top(); 509 } bestQuality() const510 inline double bestQuality() const 511 { 512 return candidates_->top()->getQuality(); 513 } 514 void newSolution(double solValue); 515 void reevaluateSearchStrategy(); 516 }; 517 518 //############################################################################# 519 520 #endif 521 522 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 523 */ 524