diff options
Diffstat (limited to 'thirdparty/linux/include/coin1/CoinSearchTree.hpp')
| -rw-r--r-- | thirdparty/linux/include/coin1/CoinSearchTree.hpp | 465 |
1 files changed, 465 insertions, 0 deletions
diff --git a/thirdparty/linux/include/coin1/CoinSearchTree.hpp b/thirdparty/linux/include/coin1/CoinSearchTree.hpp new file mode 100644 index 0000000..a0ce8e3 --- /dev/null +++ b/thirdparty/linux/include/coin1/CoinSearchTree.hpp @@ -0,0 +1,465 @@ +/* $Id: CoinSearchTree.hpp 1685 2014-01-27 03:05:07Z tkr $ */ +// Copyright (C) 2006, International Business Machines +// Corporation and others. All Rights Reserved. +// This code is licensed under the terms of the Eclipse Public License (EPL). + +#ifndef CoinSearchTree_H +#define CoinSearchTree_H + +#include <vector> +#include <algorithm> +#include <cmath> +#include <string> + +#include "CoinFinite.hpp" +#include "CoinHelperFunctions.hpp" + +// #define DEBUG_PRINT + +//############################################################################# + +class BitVector128 { + friend bool operator<(const BitVector128& b0, const BitVector128& b1); +private: + unsigned int bits_[4]; +public: + BitVector128(); + BitVector128(unsigned int bits[4]); + ~BitVector128() {} + void set(unsigned int bits[4]); + void setBit(int i); + void clearBit(int i); + std::string str() const; +}; + +bool operator<(const BitVector128& b0, const BitVector128& b1); + +//############################################################################# + +/** A class from which the real tree nodes should be derived from. Some of the + data that undoubtedly exist in the real tree node is replicated here for + fast access. This class is used in the various comparison functions. */ +class CoinTreeNode { +protected: + CoinTreeNode() : + depth_(-1), + fractionality_(-1), + quality_(-COIN_DBL_MAX), + true_lower_bound_(-COIN_DBL_MAX), + preferred_() {} + CoinTreeNode(int d, + int f = -1, + double q = -COIN_DBL_MAX, + double tlb = -COIN_DBL_MAX, + BitVector128 p = BitVector128()) : + depth_(d), + fractionality_(f), + quality_(q), + true_lower_bound_(tlb), + preferred_(p) {} + CoinTreeNode(const CoinTreeNode& x) : + depth_(x.depth_), + fractionality_(x.fractionality_), + quality_(x.quality_), + true_lower_bound_(x.true_lower_bound_), + preferred_(x.preferred_) {} + CoinTreeNode& operator=(const CoinTreeNode& x) { + if (this != &x) { + depth_ = x.depth_; + fractionality_ = x.fractionality_; + quality_ = x.quality_; + true_lower_bound_ = x.true_lower_bound_; + preferred_ = x.preferred_; + } + return *this; + } +private: + /// The depth of the node in the tree + int depth_; + /** A measure of fractionality, e.g., the number of unsatisfied + integrality requirements */ + int fractionality_; + /** Some quality for the node. For normal branch-and-cut problems the LP + relaxation value will do just fine. It is probably an OK approximation + even if column generation is done. */ + double quality_; + /** A true lower bound on the node. May be -infinity. For normal + branch-and-cut problems the LP relaxation value is OK. It is different + when column generation is done. */ + double true_lower_bound_; + /** */ + BitVector128 preferred_; +public: + virtual ~CoinTreeNode() {} + + inline int getDepth() const { return depth_; } + inline int getFractionality() const { return fractionality_; } + inline double getQuality() const { return quality_; } + inline double getTrueLB() const { return true_lower_bound_; } + inline BitVector128 getPreferred() const { return preferred_; } + + inline void setDepth(int d) { depth_ = d; } + inline void setFractionality(int f) { fractionality_ = f; } + inline void setQuality(double q) { quality_ = q; } + inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; } + inline void setPreferred(BitVector128 p) { preferred_ = p; } +}; + +//============================================================================== + +class CoinTreeSiblings { +private: + CoinTreeSiblings(); + CoinTreeSiblings& operator=(const CoinTreeSiblings&); +private: + int current_; + int numSiblings_; + CoinTreeNode** siblings_; +public: + CoinTreeSiblings(const int n, CoinTreeNode** nodes) : + current_(0), numSiblings_(n), siblings_(new CoinTreeNode*[n]) + { + CoinDisjointCopyN(nodes, n, siblings_); + } + CoinTreeSiblings(const CoinTreeSiblings& s) : + current_(s.current_), + numSiblings_(s.numSiblings_), + siblings_(new CoinTreeNode*[s.numSiblings_]) + { + CoinDisjointCopyN(s.siblings_, s.numSiblings_, siblings_); + } + ~CoinTreeSiblings() { delete[] siblings_; } + inline CoinTreeNode* currentNode() const { return siblings_[current_]; } + /** returns false if cannot be advanced */ + inline bool advanceNode() { return ++current_ != numSiblings_; } + inline int toProcess() const { return numSiblings_ - current_; } + inline int size() const { return numSiblings_; } + inline void printPref() const { + for (int i = 0; i < numSiblings_; ++i) { + std::string pref = siblings_[i]->getPreferred().str(); + printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str()); + } + } +}; + +//############################################################################# + +/** Function objects to compare search tree nodes. The comparison function + must return true if the first argument is "better" than the second one, + i.e., it should be processed first. */ +/*@{*/ +/** Depth First Search. */ +struct CoinSearchTreeComparePreferred { + static inline const char* name() { return "CoinSearchTreeComparePreferred"; } + inline bool operator()(const CoinTreeSiblings* x, + const CoinTreeSiblings* y) const { + register const CoinTreeNode* xNode = x->currentNode(); + register const CoinTreeNode* yNode = y->currentNode(); + const BitVector128 xPref = xNode->getPreferred(); + const BitVector128 yPref = yNode->getPreferred(); + bool retval = true; + if (xPref < yPref) { + retval = true; + } else if (yPref < xPref) { + retval = false; + } else { + retval = xNode->getQuality() < yNode->getQuality(); + } +#ifdef DEBUG_PRINT + printf("Comparing xpref (%s) and ypref (%s) : %s\n", + xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F"); +#endif + return retval; + } +}; + +//----------------------------------------------------------------------------- +/** Depth First Search. */ +struct CoinSearchTreeCompareDepth { + static inline const char* name() { return "CoinSearchTreeCompareDepth"; } + inline bool operator()(const CoinTreeSiblings* x, + const CoinTreeSiblings* y) const { +#if 1 + return x->currentNode()->getDepth() >= y->currentNode()->getDepth(); +#else + if(x->currentNode()->getDepth() > y->currentNode()->getDepth()) + return 1; + if(x->currentNode()->getDepth() == y->currentNode()->getDepth() && + x->currentNode()->getQuality() <= y->currentNode()->getQuality()) + return 1; + return 0; +#endif + } +}; + +//----------------------------------------------------------------------------- +/* Breadth First Search */ +struct CoinSearchTreeCompareBreadth { + static inline const char* name() { return "CoinSearchTreeCompareBreadth"; } + inline bool operator()(const CoinTreeSiblings* x, + const CoinTreeSiblings* y) const { + return x->currentNode()->getDepth() < y->currentNode()->getDepth(); + } +}; + +//----------------------------------------------------------------------------- +/** Best first search */ +struct CoinSearchTreeCompareBest { + static inline const char* name() { return "CoinSearchTreeCompareBest"; } + inline bool operator()(const CoinTreeSiblings* x, + const CoinTreeSiblings* y) const { + return x->currentNode()->getQuality() < y->currentNode()->getQuality(); + } +}; + +//############################################################################# + +class CoinSearchTreeBase +{ +private: + CoinSearchTreeBase(const CoinSearchTreeBase&); + CoinSearchTreeBase& operator=(const CoinSearchTreeBase&); + +protected: + std::vector<CoinTreeSiblings*> candidateList_; + int numInserted_; + int size_; + +protected: + CoinSearchTreeBase() : candidateList_(), numInserted_(0), size_(0) {} + + virtual void realpop() = 0; + virtual void realpush(CoinTreeSiblings* s) = 0; + virtual void fixTop() = 0; + +public: + virtual ~CoinSearchTreeBase() {} + virtual const char* compName() const = 0; + + inline const std::vector<CoinTreeSiblings*>& getCandidates() const { + return candidateList_; + } + inline bool empty() const { return candidateList_.empty(); } + inline int size() const { return size_; } + inline int numInserted() const { return numInserted_; } + inline CoinTreeNode* top() const { + if (size_ == 0) + return NULL; +#ifdef DEBUG_PRINT + char output[44]; + output[43] = 0; + candidateList_.front()->currentNode()->getPreferred().print(output); + printf("top's pref: %s\n", output); +#endif + return candidateList_.front()->currentNode(); + } + /** pop will advance the \c next pointer among the siblings on the top and + then moves the top to its correct position. #realpop is the method + that actually removes the element from the heap */ + inline void pop() { + CoinTreeSiblings* s = candidateList_.front(); + if (!s->advanceNode()) { + realpop(); + delete s; + } else { + fixTop(); + } + --size_; + } + inline void push(int numNodes, CoinTreeNode** nodes, + const bool incrInserted = true) { + CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes); + realpush(s); + if (incrInserted) { + numInserted_ += numNodes; + } + size_ += numNodes; + } + inline void push(const CoinTreeSiblings& sib, + const bool incrInserted = true) { + CoinTreeSiblings* s = new CoinTreeSiblings(sib); +#ifdef DEBUG_PRINT + s->printPref(); +#endif + realpush(s); + if (incrInserted) { + numInserted_ += sib.toProcess(); + } + size_ += sib.toProcess(); + } +}; + +//############################################################################# + +// #define CAN_TRUST_STL_HEAP +#ifdef CAN_TRUST_STL_HEAP + +template <class Comp> +class CoinSearchTree : public CoinSearchTreeBase +{ +private: + Comp comp_; +protected: + virtual void realpop() { + candidateList_.pop_back(); + } + virtual void fixTop() { + CoinTreeSiblings* s = top(); + realpop(); + push(s, false); + } + virtual void realpush(CoinTreeSiblings* s) { + nodes_.push_back(s); + std::push_heap(candidateList_.begin(), candidateList_.end(), comp_); + } +public: + CoinSearchTree() : CoinSearchTreeBase(), comp_() {} + CoinSearchTree(const CoinSearchTreeBase& t) : + CoinSearchTreeBase(), comp_() { + candidateList_ = t.getCandidates(); + std::make_heap(candidateList_.begin(), candidateList_.end(), comp_); + numInserted_ = t.numInserted_; + size_ = t.size_; + } + ~CoinSearchTree() {} + const char* compName() const { return Comp::name(); } +}; + +#else + +template <class Comp> +class CoinSearchTree : public CoinSearchTreeBase +{ +private: + Comp comp_; + +protected: + virtual void realpop() { + candidateList_[0] = candidateList_.back(); + candidateList_.pop_back(); + fixTop(); + } + /** After changing data in the top node, fix the heap */ + virtual void fixTop() { + const size_t size = candidateList_.size(); + if (size > 1) { + CoinTreeSiblings** candidates = &candidateList_[0]; + CoinTreeSiblings* s = candidates[0]; + --candidates; + size_t pos = 1; + size_t ch; + for (ch = 2; ch < size; pos = ch, ch *= 2) { + if (comp_(candidates[ch+1], candidates[ch])) + ++ch; + if (comp_(s, candidates[ch])) + break; + candidates[pos] = candidates[ch]; + } + if (ch == size) { + if (comp_(candidates[ch], s)) { + candidates[pos] = candidates[ch]; + pos = ch; + } + } + candidates[pos] = s; + } + } + virtual void realpush(CoinTreeSiblings* s) { + candidateList_.push_back(s); + CoinTreeSiblings** candidates = &candidateList_[0]; + --candidates; + size_t pos = candidateList_.size(); + size_t ch; + for (ch = pos/2; ch != 0; pos = ch, ch /= 2) { + if (comp_(candidates[ch], s)) + break; + candidates[pos] = candidates[ch]; + } + candidates[pos] = s; + } + +public: + CoinSearchTree() : CoinSearchTreeBase(), comp_() {} + CoinSearchTree(const CoinSearchTreeBase& t) : + CoinSearchTreeBase(), comp_() { + candidateList_ = t.getCandidates(); + std::sort(candidateList_.begin(), candidateList_.end(), comp_); + numInserted_ = t.numInserted(); + size_ = t.size(); + } + virtual ~CoinSearchTree() {} + const char* compName() const { return Comp::name(); } +}; + +#endif + +//############################################################################# + +enum CoinNodeAction { + CoinAddNodeToCandidates, + CoinTestNodeForDiving, + CoinDiveIntoNode +}; + +class CoinSearchTreeManager +{ +private: + CoinSearchTreeManager(const CoinSearchTreeManager&); + CoinSearchTreeManager& operator=(const CoinSearchTreeManager&); +private: + CoinSearchTreeBase* candidates_; + int numSolution; + /** Whether there is an upper bound or not. The upper bound may have come + as input, not necessarily from a solution */ + bool hasUB_; + + /** variable used to test whether we need to reevaluate search strategy */ + bool recentlyReevaluatedSearchStrategy_; + +public: + CoinSearchTreeManager() : + candidates_(NULL), + numSolution(0), + recentlyReevaluatedSearchStrategy_(true) + {} + virtual ~CoinSearchTreeManager() { + delete candidates_; + } + + inline void setTree(CoinSearchTreeBase* t) { + delete candidates_; + candidates_ = t; + } + inline CoinSearchTreeBase* getTree() const { + return candidates_; + } + + inline bool empty() const { return candidates_->empty(); } + inline size_t size() const { return candidates_->size(); } + inline size_t numInserted() const { return candidates_->numInserted(); } + inline CoinTreeNode* top() const { return candidates_->top(); } + inline void pop() { candidates_->pop(); } + inline void push(CoinTreeNode* node, const bool incrInserted = true) { + candidates_->push(1, &node, incrInserted); + } + inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) { + candidates_->push(s, incrInserted); + } + inline void push(const int n, CoinTreeNode** nodes, + const bool incrInserted = true) { + candidates_->push(n, nodes, incrInserted); + } + + inline CoinTreeNode* bestQualityCandidate() const { + return candidates_->top(); + } + inline double bestQuality() const { + return candidates_->top()->getQuality(); + } + void newSolution(double solValue); + void reevaluateSearchStrategy(); +}; + +//############################################################################# + +#endif |