CoinSearchTree.hpp
Go to the documentation of this file.
1 /* $Id: CoinSearchTree.hpp 1191 2009-07-25 08:38:12Z forrest $ */
2 #ifndef CoinSearchTree_H
3 #define CoinSearchTree_H
4 
5 #include <vector>
6 #include <algorithm>
7 #include <cmath>
8 #include <string>
9 
10 #include "CoinFinite.hpp"
11 #include "CoinHelperFunctions.hpp"
12 
13 // #define DEBUG_PRINT
14 
15 //#############################################################################
16 
17 class BitVector128 {
18  friend bool operator<(const BitVector128& b0, const BitVector128& b1);
19 private:
20  unsigned int bits_[4];
21 public:
22  BitVector128();
24  void setBit(int i);
25  void clearBit(int i);
26  std::string str() const;
27 };
28 
29 bool operator<(const BitVector128& b0, const BitVector128& b1);
30 
31 //#############################################################################
32 
36 class CoinTreeNode {
37 protected:
39  depth_(-1),
40  fractionality_(-1),
43  preferred_() {}
44  CoinTreeNode(int d,
45  int f = -1,
46  double q = -COIN_DBL_MAX,
47  double tlb = -COIN_DBL_MAX,
48  BitVector128 p = BitVector128()) :
49  depth_(d),
50  fractionality_(f),
51  quality_(q),
52  true_lower_bound_(tlb),
53  preferred_(p) {}
55  depth_(x.depth_),
57  quality_(x.quality_),
61  if (this != &x) {
62  depth_ = x.depth_;
64  quality_ = x.quality_;
67  }
68  return *this;
69  }
70 private:
72  int depth_;
79  double quality_;
86 public:
87  virtual ~CoinTreeNode() {}
88 
89  inline int getDepth() const { return depth_; }
90  inline int getFractionality() const { return fractionality_; }
91  inline double getQuality() const { return quality_; }
92  inline double getTrueLB() const { return true_lower_bound_; }
93  inline BitVector128 getPreferred() const { return preferred_; }
94 
95  inline void setDepth(int d) { depth_ = d; }
96  inline void setFractionality(int f) { fractionality_ = f; }
97  inline void setQuality(double q) { quality_ = q; }
98  inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; }
99  inline void setPreferred(BitVector128 p) { preferred_ = p; }
100 };
101 
102 //==============================================================================
103 
105 private:
108 private:
109  int current_;
112 public:
113  CoinTreeSiblings(const int n, CoinTreeNode** nodes) :
115  {
116  CoinDisjointCopyN(nodes, n, siblings_);
117  }
119  current_(s.current_),
122  {
124  }
125  ~CoinTreeSiblings() { delete[] siblings_; }
126  inline CoinTreeNode* currentNode() const { return siblings_[current_]; }
128  inline bool advanceNode() { return ++current_ != numSiblings_; }
129  inline int toProcess() const { return numSiblings_ - current_; }
130  inline int size() const { return numSiblings_; }
131  inline void printPref() const {
132  for (int i = 0; i < numSiblings_; ++i) {
133  std::string pref = siblings_[i]->getPreferred().str();
134  printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
135  }
136  }
137 };
138 
139 //#############################################################################
140 
147  static inline const char* name() { return "CoinSearchTreeComparePreferred"; }
148  inline bool operator()(const CoinTreeSiblings* x,
149  const CoinTreeSiblings* y) const {
150  register const CoinTreeNode* xNode = x->currentNode();
151  register const CoinTreeNode* yNode = y->currentNode();
152  const BitVector128 xPref = xNode->getPreferred();
153  const BitVector128 yPref = yNode->getPreferred();
154  bool retval = true;
155  if (xPref < yPref) {
156  retval = true;
157  } else if (yPref < xPref) {
158  retval = false;
159  } else {
160  retval = xNode->getQuality() < yNode->getQuality();
161  }
162 #ifdef DEBUG_PRINT
163  printf("Comparing xpref (%s) and ypref (%s) : %s\n",
164  xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F");
165 #endif
166  return retval;
167  }
168 };
169 
170 //-----------------------------------------------------------------------------
173  static inline const char* name() { return "CoinSearchTreeCompareDepth"; }
174  inline bool operator()(const CoinTreeSiblings* x,
175  const CoinTreeSiblings* y) const {
176 #if 1
177  return x->currentNode()->getDepth() >= y->currentNode()->getDepth();
178 #else
179  if(x->currentNode()->getDepth() > y->currentNode()->getDepth())
180  return 1;
181  if(x->currentNode()->getDepth() == y->currentNode()->getDepth() &&
182  x->currentNode()->getQuality() <= y->currentNode()->getQuality())
183  return 1;
184  return 0;
185 #endif
186  }
187 };
188 
189 //-----------------------------------------------------------------------------
190 /* Breadth First Search */
192  static inline const char* name() { return "CoinSearchTreeCompareBreadth"; }
193  inline bool operator()(const CoinTreeSiblings* x,
194  const CoinTreeSiblings* y) const {
195  return x->currentNode()->getDepth() < y->currentNode()->getDepth();
196  }
197 };
198 
199 //-----------------------------------------------------------------------------
202  static inline const char* name() { return "CoinSearchTreeCompareBest"; }
203  inline bool operator()(const CoinTreeSiblings* x,
204  const CoinTreeSiblings* y) const {
205  return x->currentNode()->getQuality() < y->currentNode()->getQuality();
206  }
207 };
208 
209 //#############################################################################
210 
212 {
213 private:
216 
217 protected:
218  std::vector<CoinTreeSiblings*> candidateList_;
220  int size_;
221 
222 protected:
224 
225  virtual void realpop() = 0;
226  virtual void realpush(CoinTreeSiblings* s) = 0;
227  virtual void fixTop() = 0;
228 
229 public:
230  virtual ~CoinSearchTreeBase() {}
231  virtual const char* compName() const = 0;
232 
233  inline const std::vector<CoinTreeSiblings*>& getCandidates() const {
234  return candidateList_;
235  }
236  inline bool empty() const { return candidateList_.empty(); }
237  inline int size() const { return size_; }
238  inline int numInserted() const { return numInserted_; }
239  inline CoinTreeNode* top() const {
240  if (size_ == 0)
241  return NULL;
242 #ifdef DEBUG_PRINT
243  char output[44];
244  output[43] = 0;
245  candidateList_.front()->currentNode()->getPreferred().print(output);
246  printf("top's pref: %s\n", output);
247 #endif
248  return candidateList_.front()->currentNode();
249  }
253  inline void pop() {
254  CoinTreeSiblings* s = candidateList_.front();
255  if (!s->advanceNode()) {
256  realpop();
257  delete s;
258  } else {
259  fixTop();
260  }
261  --size_;
262  }
263  inline void push(int numNodes, CoinTreeNode** nodes,
264  const bool incrInserted = true) {
265  CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes);
266  realpush(s);
267  if (incrInserted) {
268  numInserted_ += numNodes;
269  }
270  size_ += numNodes;
271  }
272  inline void push(const CoinTreeSiblings& sib,
273  const bool incrInserted = true) {
274  CoinTreeSiblings* s = new CoinTreeSiblings(sib);
275 #ifdef DEBUG_PRINT
276  s->printPref();
277 #endif
278  realpush(s);
279  if (incrInserted) {
280  numInserted_ += sib.toProcess();
281  }
282  size_ += sib.size();
283  }
284 };
285 
286 //#############################################################################
287 
288 // #define CAN_TRUST_STL_HEAP
289 #ifdef CAN_TRUST_STL_HEAP
290 
291 template <class Comp>
292 class CoinSearchTree : public CoinSearchTreeBase
293 {
294 private:
295  Comp comp_;
296 protected:
297  virtual void realpop() {
298  candidateList_.pop_back();
299  }
300  virtual void fixTop() {
301  CoinTreeSiblings* s = top();
302  realpop();
303  push(s, false);
304  }
305  virtual void realpush(CoinTreeSiblings* s) {
306  nodes_.push_back(s);
307  std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
308  }
309 public:
314  std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
316  size_ = t.size_;
317  }
318  ~CoinSearchTree() {}
319  const char* compName() const { return Comp::name(); }
320 };
321 
322 #else
323 
324 template <class Comp>
326 {
327 private:
328  Comp comp_;
329 
330 protected:
331  virtual void realpop() {
332  candidateList_[0] = candidateList_.back();
333  candidateList_.pop_back();
334  fixTop();
335  }
337  virtual void fixTop() {
338  const int size = candidateList_.size();
339  if (size > 1) {
340  CoinTreeSiblings** candidates = &candidateList_[0];
341  CoinTreeSiblings* s = candidates[0];
342  --candidates;
343  int pos = 1;
344  int ch;
345  for (ch = 2; ch < size; pos = ch, ch *= 2) {
346  if (comp_(candidates[ch+1], candidates[ch]))
347  ++ch;
348  if (comp_(s, candidates[ch]))
349  break;
350  candidates[pos] = candidates[ch];
351  }
352  if (ch == size) {
353  if (comp_(candidates[ch], s)) {
354  candidates[pos] = candidates[ch];
355  pos = ch;
356  }
357  }
358  candidates[pos] = s;
359  }
360  }
361  virtual void realpush(CoinTreeSiblings* s) {
362  candidateList_.push_back(s);
363  CoinTreeSiblings** candidates = &candidateList_[0];
364  --candidates;
365  int pos = candidateList_.size();
366  int ch;
367  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
368  if (comp_(candidates[ch], s))
369  break;
370  candidates[pos] = candidates[ch];
371  }
372  candidates[pos] = s;
373  }
374 
375 public:
380  std::sort(candidateList_.begin(), candidateList_.end(), comp_);
382  size_ = t.size();
383  }
385  const char* compName() const { return Comp::name(); }
386 };
387 
388 #endif
389 
390 //#############################################################################
391 
396 };
397 
399 {
400 private:
403 private:
408  bool hasUB_;
409 
412 
413 public:
415  candidates_(NULL),
416  numSolution(0),
418  {}
420  delete candidates_;
421  }
422 
423  inline void setTree(CoinSearchTreeBase* t) {
424  delete candidates_;
425  candidates_ = t;
426  }
427  inline CoinSearchTreeBase* getTree() const {
428  return candidates_;
429  }
430 
431  inline bool empty() const { return candidates_->empty(); }
432  inline size_t size() const { return candidates_->size(); }
433  inline size_t numInserted() const { return candidates_->numInserted(); }
434  inline CoinTreeNode* top() const { return candidates_->top(); }
435  inline void pop() { candidates_->pop(); }
436  inline void push(CoinTreeNode* node, const bool incrInserted = true) {
437  candidates_->push(1, &node, incrInserted);
438  }
439  inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) {
440  candidates_->push(s, incrInserted);
441  }
442  inline void push(const int n, CoinTreeNode** nodes,
443  const bool incrInserted = true) {
444  candidates_->push(n, nodes, incrInserted);
445  }
446 
448  return candidates_->top();
449  }
450  inline double bestQuality() const {
451  return candidates_->top()->getQuality();
452  }
453  void newSolution(double solValue);
455 };
456 
457 //#############################################################################
458 
459 #endif
bool recentlyReevaluatedSearchStrategy_
variable used to test whether we need to reevaluate search strategy
bool hasUB_
Whether there is an upper bound or not.
double bestQuality() const
CoinTreeNode * top() const
CoinSearchTreeBase & operator=(const CoinSearchTreeBase &)
virtual ~CoinSearchTreeBase()
void clearBit(int i)
int getDepth() const
CoinTreeSiblings & operator=(const CoinTreeSiblings &)
void CoinDisjointCopyN(register const T *from, const int size, register T *to)
This helper function copies an array to another location.
CoinTreeNode(int d, int f=-1, double q=-COIN_DBL_MAX, double tlb=-COIN_DBL_MAX, BitVector128 p=BitVector128())
BitVector128 preferred_
bool operator<(const BitVector128 &b0, const BitVector128 &b1)
size_t numInserted() const
unsigned int bits_[4]
CoinTreeNode * top() const
friend bool operator<(const BitVector128 &b0, const BitVector128 &b1)
void setQuality(double q)
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
CoinTreeNode(const CoinTreeNode &x)
virtual void realpop()
void setTrueLB(double tlb)
void printPref() const
virtual void realpush(CoinTreeSiblings *s)=0
static const char * name()
BitVector128 getPreferred() const
int fractionality_
A measure of fractionality, e.g., the number of unsatisfied integrality requirements.
void pop()
pop will advance the next pointer among the siblings on the top and then moves the top to its correct...
std::vector< CoinTreeSiblings * > candidateList_
CoinSearchTreeManager & operator=(const CoinSearchTreeManager &)
void setFractionality(int f)
#define COIN_DBL_MAX
This has #defines etc for the "C" interface to Coin.
CoinTreeNode * bestQualityCandidate() const
static const char * name()
int getFractionality() const
void setBit(int i)
void setDepth(int d)
double true_lower_bound_
A true lower bound on the node.
void setTree(CoinSearchTreeBase *t)
void push(int numNodes, CoinTreeNode **nodes, const bool incrInserted=true)
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
const std::vector< CoinTreeSiblings * > & getCandidates() const
CoinTreeSiblings(const int n, CoinTreeNode **nodes)
Depth First Search.
void push(CoinTreeNode *node, const bool incrInserted=true)
virtual void fixTop()=0
virtual ~CoinTreeNode()
double getTrueLB() const
const char * compName() const
bool advanceNode()
returns false if cannot be advanced
int toProcess() const
A class from which the real tree nodes should be derived from.
int numInserted() const
CoinSearchTreeBase * getTree() const
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
virtual void realpush(CoinTreeSiblings *s)
static const char * name()
CoinNodeAction
CoinTreeSiblings(const CoinTreeSiblings &s)
virtual const char * compName() const =0
CoinTreeNode ** siblings_
CoinSearchTree(const CoinSearchTreeBase &t)
void push(const CoinTreeSiblings &s, const bool incrInserted=true)
void push(const CoinTreeSiblings &sib, const bool incrInserted=true)
double getQuality() const
CoinTreeNode & operator=(const CoinTreeNode &x)
int depth_
The depth of the node in the tree.
void push(const int n, CoinTreeNode **nodes, const bool incrInserted=true)
double quality_
Some quality for the node.
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
Function objects to compare search tree nodes.
std::string str() const
void setPreferred(BitVector128 p)
virtual void fixTop()
After changing data in the top node, fix the heap.
virtual void realpop()=0
CoinSearchTreeBase * candidates_
CoinTreeNode * currentNode() const
void newSolution(double solValue)