6 #ifndef CoinSearchTree_H 7 #define CoinSearchTree_H 29 void set(
unsigned int bits[4]);
32 std::string
str()
const;
58 true_lower_bound_(tlb),
62 fractionality_(x.fractionality_),
64 true_lower_bound_(x.true_lower_bound_),
65 preferred_(x.preferred_) {}
98 inline double getTrueLB()
const {
return true_lower_bound_; }
104 inline void setTrueLB(
double tlb) { true_lower_bound_ = tlb; }
120 current_(0), numSiblings_(n), siblings_(new
CoinTreeNode*[n])
125 current_(s.current_),
126 numSiblings_(s.numSiblings_),
135 inline int toProcess()
const {
return numSiblings_ - current_; }
136 inline int size()
const {
return numSiblings_; }
138 for (
int i = 0; i < numSiblings_; ++i) {
140 printf(
"prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
153 static inline const char*
name() {
return "CoinSearchTreeComparePreferred"; }
163 }
else if (yPref < xPref) {
169 printf(
"Comparing xpref (%s) and ypref (%s) : %s\n",
170 xpref.str().c_str(), ypref.str().c_str(), retval ?
"T" :
"F");
179 static inline const char*
name() {
return "CoinSearchTreeCompareDepth"; }
198 static inline const char*
name() {
return "CoinSearchTreeCompareBreadth"; }
208 static inline const char*
name() {
return "CoinSearchTreeCompareBest"; }
231 virtual void realpop() = 0;
233 virtual void fixTop() = 0;
237 virtual const char* compName()
const = 0;
240 return candidateList_;
242 inline bool empty()
const {
return candidateList_.empty(); }
243 inline int size()
const {
return size_; }
251 candidateList_.front()->currentNode()->getPreferred().print(output);
252 printf(
"top's pref: %s\n", output);
254 return candidateList_.front()->currentNode();
270 const bool incrInserted =
true) {
274 numInserted_ += numNodes;
279 const bool incrInserted =
true) {
295 #ifdef CAN_TRUST_STL_HEAP 297 template <
class Comp>
303 virtual void realpop() {
304 candidateList_.pop_back();
306 virtual void fixTop() {
313 std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
320 std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
325 const char* compName()
const {
return Comp::name(); }
330 template <
class Comp>
338 candidateList_[0] = candidateList_.back();
339 candidateList_.pop_back();
344 const size_t size = candidateList_.size();
351 for (ch = 2; ch < size; pos = ch, ch *= 2) {
352 if (comp_(candidates[ch+1], candidates[ch]))
354 if (comp_(s, candidates[ch]))
356 candidates[pos] = candidates[ch];
359 if (comp_(candidates[ch], s)) {
360 candidates[pos] = candidates[ch];
368 candidateList_.push_back(s);
371 size_t pos = candidateList_.
size();
373 for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
374 if (comp_(candidates[ch], s))
376 candidates[pos] = candidates[ch];
386 std::sort(candidateList_.begin(), candidateList_.end(), comp_);
391 const char*
compName()
const {
return Comp::name(); }
423 recentlyReevaluatedSearchStrategy_(true)
438 inline size_t size()
const {
return candidates_->
size(); }
441 inline void pop() { candidates_->
pop(); }
443 candidates_->
push(1, &node, incrInserted);
446 candidates_->
push(s, incrInserted);
449 const bool incrInserted =
true) {
450 candidates_->
push(n, nodes, incrInserted);
454 return candidates_->
top();
459 void newSolution(
double solValue);
460 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.
int depth_
The depth of the node in the tree.
void CoinDisjointCopyN(register const T *from, const int size, register T *to)
This helper function copies an array to another location.
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
CoinTreeSiblings(const int n, CoinTreeNode **nodes)
virtual void fixTop()
After changing data in the top node, fix the heap.
void push(CoinTreeNode *node, const bool incrInserted=true)
double quality_
Some quality for the node.
void setQuality(double q)
CoinTreeNode * top() const
CoinSearchTree(const CoinSearchTreeBase &t)
Function objects to compare search tree nodes.
bool advanceNode()
returns false if cannot be advanced
CoinTreeNode * currentNode() const
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)
std::vector< CoinTreeSiblings * > candidateList_
virtual ~CoinSearchTreeManager()
CoinTreeNode & operator=(const CoinTreeNode &x)
friend bool operator<(const BitVector128 &b0, const BitVector128 &b1)
static const char * name()
void push(const int n, CoinTreeNode **nodes, const bool incrInserted=true)
int getFractionality() const
void push(const CoinTreeSiblings &s, const bool incrInserted=true)
const std::vector< CoinTreeSiblings * > & getCandidates() const
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())
int fractionality_
A measure of fractionality, e.g., the number of unsatisfied integrality requirements.
virtual ~CoinSearchTree()
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
CoinSearchTreeBase * getTree() const
static const char * name()
void push(const CoinTreeSiblings &sib, const bool incrInserted=true)
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)
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...
BitVector128 getPreferred() const
double bestQuality() const
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
const double COIN_DBL_MAX
CoinTreeNode * bestQualityCandidate() const
double getQuality() const
CoinTreeNode * top() const
void setTrueLB(double tlb)
size_t numInserted() const
virtual ~CoinSearchTreeBase()
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const