6 #ifndef CoinSearchTree_H 7 #define CoinSearchTree_H 31 void set(
unsigned int bits[4]);
34 std::string
str()
const;
62 , true_lower_bound_(tlb)
68 , fractionality_(x.fractionality_)
69 , quality_(x.quality_)
70 , true_lower_bound_(x.true_lower_bound_)
71 , preferred_(x.preferred_)
109 inline double getTrueLB()
const {
return true_lower_bound_; }
115 inline void setTrueLB(
double tlb) { true_lower_bound_ = tlb; }
140 : current_(s.current_)
141 , numSiblings_(s.numSiblings_)
150 inline int toProcess()
const {
return numSiblings_ - current_; }
151 inline int size()
const {
return numSiblings_; }
154 for (
int i = 0; i < numSiblings_; ++i) {
156 printf(
"prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
169 static inline const char *
name() {
return "CoinSearchTreeComparePreferred"; }
180 }
else if (yPref < xPref) {
186 printf(
"Comparing xpref (%s) and ypref (%s) : %s\n",
187 xpref.str().c_str(), ypref.str().c_str(), retval ?
"T" :
"F");
196 static inline const char *
name() {
return "CoinSearchTreeCompareDepth"; }
215 static inline const char *
name() {
return "CoinSearchTreeCompareBreadth"; }
226 static inline const char *
name() {
return "CoinSearchTreeCompareBest"; }
254 virtual void realpop() = 0;
256 virtual void fixTop() = 0;
260 virtual const char *compName()
const = 0;
264 return candidateList_;
266 inline bool empty()
const {
return candidateList_.empty(); }
267 inline int size()
const {
return size_; }
271 if (size_ == 0 || candidateList_.size() == 0)
276 candidateList_.front()->currentNode()->getPreferred().print(output);
277 printf(
"top's pref: %s\n", output);
279 return candidateList_.front()->currentNode();
296 const bool incrInserted =
true)
301 numInserted_ += numNodes;
306 const bool incrInserted =
true)
323 #ifdef CAN_TRUST_STL_HEAP 325 template <
class Comp >
331 virtual void realpop()
333 candidateList_.pop_back();
335 virtual void fixTop()
344 std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
358 std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
363 const char *compName()
const {
return Comp::name(); }
368 template <
class Comp >
376 candidateList_[0] = candidateList_.back();
377 candidateList_.pop_back();
383 const size_t size = candidateList_.size();
390 for (ch = 2; ch < size; pos = ch, ch *= 2) {
391 if (comp_(candidates[ch + 1], candidates[ch]))
393 if (comp_(s, candidates[ch]))
395 candidates[pos] = candidates[ch];
398 if (comp_(candidates[ch], s)) {
399 candidates[pos] = candidates[ch];
408 candidateList_.push_back(s);
411 size_t pos = candidateList_.
size();
413 for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) {
414 if (comp_(candidates[ch], s))
416 candidates[pos] = candidates[ch];
432 std::sort(candidateList_.begin(), candidateList_.end(), comp_);
437 const char *
compName()
const {
return Comp::name(); }
469 , recentlyReevaluatedSearchStrategy_(true)
488 inline size_t size()
const {
return candidates_->
size(); }
491 inline void pop() { candidates_->
pop(); }
494 candidates_->
push(1, &node, incrInserted);
498 candidates_->
push(s, incrInserted);
501 const bool incrInserted =
true)
503 candidates_->
push(n, nodes, incrInserted);
508 return candidates_->
top();
514 void newSolution(
double solValue);
515 void reevaluateSearchStrategy();
const char * compName() const
CoinSearchTreeBase * candidates_
bool recentlyReevaluatedSearchStrategy_
variable used to test whether we need to reevaluate search strategy
bool hasUB_
Whether there is an upper bound or not.
void CoinDisjointCopyN(const T *from, const CoinBigIndex size, T *to)
This helper function copies an array to another location.
int depth_
The depth of the node in the tree.
int getFractionality() const
CoinTreeNode * top() const
CoinTreeSiblings(const int n, CoinTreeNode **nodes)
double getQuality() const
virtual void fixTop()
After changing data in the top node, fix the heap.
std::vector< CoinTreeSiblings *> candidateList_
void push(CoinTreeNode *node, const bool incrInserted=true)
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
double quality_
Some quality for the node.
void setQuality(double q)
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
BitVector128 getPreferred() const
CoinSearchTreeBase * getTree() const
CoinTreeNode * top() const
CoinSearchTree(const CoinSearchTreeBase &t)
Function objects to compare search tree nodes.
bool advanceNode()
returns false if cannot be advanced
double true_lower_bound_
A true lower bound on the node.
static const char * name()
void push(int numNodes, CoinTreeNode **nodes, const bool incrInserted=true)
virtual ~CoinSearchTreeManager()
CoinTreeNode & operator=(const CoinTreeNode &x)
friend bool operator<(const BitVector128 &b0, const BitVector128 &b1)
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
static const char * name()
void push(const int n, CoinTreeNode **nodes, const bool incrInserted=true)
void push(const CoinTreeSiblings &s, const bool incrInserted=true)
CoinTreeNode ** siblings_
CoinTreeSiblings(const CoinTreeSiblings &s)
static const char * name()
CoinTreeNode(int d, int f=-1, double q=-COIN_DBL_MAX, double tlb=-COIN_DBL_MAX, BitVector128 p=BitVector128())
double bestQuality() const
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
size_t numInserted() const
int fractionality_
A measure of fractionality, e.g., the number of unsatisfied integrality requirements.
virtual ~CoinSearchTree()
static const char * name()
void push(const CoinTreeSiblings &sib, const bool incrInserted=true)
#define pref(qqnme, qqref, qquflgs, qqoff, qqsep)
void setTree(CoinSearchTreeBase *t)
CoinTreeNode(const CoinTreeNode &x)
A class from which the real tree nodes should be derived from.
virtual void realpush(CoinTreeSiblings *s)
void setPreferred(BitVector128 p)
const std::vector< CoinTreeSiblings *> & getCandidates() const
CoinTreeNode * bestQualityCandidate() const
void setFractionality(int f)
void pop()
pop will advance the next pointer among the siblings on the top and then moves the top to its correct...
CoinTreeNode * currentNode() const
const double COIN_DBL_MAX
void setTrueLB(double tlb)
virtual ~CoinSearchTreeBase()