Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CoinSearchTree.hpp
Go to the documentation of this file.
1 /* $Id: CoinSearchTree.hpp 1824 2015-04-04 16:27:28Z tkr $ */
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 private:
24  unsigned int bits_[4];
25 public:
26  BitVector128();
27  BitVector128(unsigned int bits[4]);
29  void set(unsigned int bits[4]);
30  void setBit(int i);
31  void clearBit(int i);
32  std::string str() const;
33 };
34 
35 bool operator<(const BitVector128& b0, const BitVector128& b1);
36 
37 //#############################################################################
38 
42 class CoinTreeNode {
43 protected:
45  depth_(-1),
46  fractionality_(-1),
49  preferred_() {}
50  CoinTreeNode(int d,
51  int f = -1,
52  double q = -COIN_DBL_MAX,
53  double tlb = -COIN_DBL_MAX,
54  BitVector128 p = BitVector128()) :
55  depth_(d),
56  fractionality_(f),
57  quality_(q),
58  true_lower_bound_(tlb),
59  preferred_(p) {}
61  depth_(x.depth_),
63  quality_(x.quality_),
67  if (this != &x) {
68  depth_ = x.depth_;
70  quality_ = x.quality_;
73  }
74  return *this;
75  }
76 private:
78  int depth_;
85  double quality_;
92 public:
93  virtual ~CoinTreeNode() {}
94 
95  inline int getDepth() const { return depth_; }
96  inline int getFractionality() const { return fractionality_; }
97  inline double getQuality() const { return quality_; }
98  inline double getTrueLB() const { return true_lower_bound_; }
99  inline BitVector128 getPreferred() const { return preferred_; }
100 
101  inline void setDepth(int d) { depth_ = d; }
102  inline void setFractionality(int f) { fractionality_ = f; }
103  inline void setQuality(double q) { quality_ = q; }
104  inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; }
105  inline void setPreferred(BitVector128 p) { preferred_ = p; }
106 };
107 
108 //==============================================================================
109 
111 private:
114 private:
115  int current_;
118 public:
119  CoinTreeSiblings(const int n, CoinTreeNode** nodes) :
121  {
122  CoinDisjointCopyN(nodes, n, siblings_);
123  }
125  current_(s.current_),
128  {
130  }
131  ~CoinTreeSiblings() { delete[] siblings_; }
132  inline CoinTreeNode* currentNode() const { return siblings_[current_]; }
134  inline bool advanceNode() { return ++current_ != numSiblings_; }
135  inline int toProcess() const { return numSiblings_ - current_; }
136  inline int size() const { return numSiblings_; }
137  inline void printPref() const {
138  for (int i = 0; i < numSiblings_; ++i) {
139  std::string pref = siblings_[i]->getPreferred().str();
140  printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
141  }
142  }
143 };
144 
145 //#############################################################################
146 
153  static inline const char* name() { return "CoinSearchTreeComparePreferred"; }
154  inline bool operator()(const CoinTreeSiblings* x,
155  const CoinTreeSiblings* y) const {
156  register const CoinTreeNode* xNode = x->currentNode();
157  register const CoinTreeNode* yNode = y->currentNode();
158  const BitVector128 xPref = xNode->getPreferred();
159  const BitVector128 yPref = yNode->getPreferred();
160  bool retval = true;
161  if (xPref < yPref) {
162  retval = true;
163  } else if (yPref < xPref) {
164  retval = false;
165  } else {
166  retval = xNode->getQuality() < yNode->getQuality();
167  }
168 #ifdef DEBUG_PRINT
169  printf("Comparing xpref (%s) and ypref (%s) : %s\n",
170  xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F");
171 #endif
172  return retval;
173  }
174 };
175 
176 //-----------------------------------------------------------------------------
179  static inline const char* name() { return "CoinSearchTreeCompareDepth"; }
180  inline bool operator()(const CoinTreeSiblings* x,
181  const CoinTreeSiblings* y) const {
182 #if 1
183  return x->currentNode()->getDepth() >= y->currentNode()->getDepth();
184 #else
185  if(x->currentNode()->getDepth() > y->currentNode()->getDepth())
186  return 1;
187  if(x->currentNode()->getDepth() == y->currentNode()->getDepth() &&
188  x->currentNode()->getQuality() <= y->currentNode()->getQuality())
189  return 1;
190  return 0;
191 #endif
192  }
193 };
194 
195 //-----------------------------------------------------------------------------
196 /* Breadth First Search */
198  static inline const char* name() { return "CoinSearchTreeCompareBreadth"; }
199  inline bool operator()(const CoinTreeSiblings* x,
200  const CoinTreeSiblings* y) const {
201  return x->currentNode()->getDepth() < y->currentNode()->getDepth();
202  }
203 };
204 
205 //-----------------------------------------------------------------------------
208  static inline const char* name() { return "CoinSearchTreeCompareBest"; }
209  inline bool operator()(const CoinTreeSiblings* x,
210  const CoinTreeSiblings* y) const {
211  return x->currentNode()->getQuality() < y->currentNode()->getQuality();
212  }
213 };
214 
215 //#############################################################################
216 
218 {
219 private:
222 
223 protected:
224  std::vector<CoinTreeSiblings*> candidateList_;
226  int size_;
227 
228 protected:
230 
231  virtual void realpop() = 0;
232  virtual void realpush(CoinTreeSiblings* s) = 0;
233  virtual void fixTop() = 0;
234 
235 public:
236  virtual ~CoinSearchTreeBase() {}
237  virtual const char* compName() const = 0;
238 
239  inline const std::vector<CoinTreeSiblings*>& getCandidates() const {
240  return candidateList_;
241  }
242  inline bool empty() const { return candidateList_.empty(); }
243  inline int size() const { return size_; }
244  inline int numInserted() const { return numInserted_; }
245  inline CoinTreeNode* top() const {
246  if (size_ == 0 || candidateList_.size() == 0)
247  return NULL;
248 #ifdef DEBUG_PRINT
249  char output[44];
250  output[43] = 0;
251  candidateList_.front()->currentNode()->getPreferred().print(output);
252  printf("top's pref: %s\n", output);
253 #endif
254  return candidateList_.front()->currentNode();
255  }
259  inline void pop() {
260  CoinTreeSiblings* s = candidateList_.front();
261  if (!s->advanceNode()) {
262  realpop();
263  delete s;
264  } else {
265  fixTop();
266  }
267  --size_;
268  }
269  inline void push(int numNodes, CoinTreeNode** nodes,
270  const bool incrInserted = true) {
271  CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes);
272  realpush(s);
273  if (incrInserted) {
274  numInserted_ += numNodes;
275  }
276  size_ += numNodes;
277  }
278  inline void push(const CoinTreeSiblings& sib,
279  const bool incrInserted = true) {
280  CoinTreeSiblings* s = new CoinTreeSiblings(sib);
281 #ifdef DEBUG_PRINT
282  s->printPref();
283 #endif
284  realpush(s);
285  if (incrInserted) {
286  numInserted_ += sib.toProcess();
287  }
288  size_ += sib.toProcess();
289  }
290 };
291 
292 //#############################################################################
293 
294 // #define CAN_TRUST_STL_HEAP
295 #ifdef CAN_TRUST_STL_HEAP
296 
297 template <class Comp>
298 class CoinSearchTree : public CoinSearchTreeBase
299 {
300 private:
301  Comp comp_;
302 protected:
303  virtual void realpop() {
304  candidateList_.pop_back();
305  }
306  virtual void fixTop() {
307  CoinTreeSiblings* s = top();
308  realpop();
309  push(s, false);
310  }
311  virtual void realpush(CoinTreeSiblings* s) {
312  nodes_.push_back(s);
313  std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
314  }
315 public:
320  std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
322  size_ = t.size_;
323  }
324  ~CoinSearchTree() {}
325  const char* compName() const { return Comp::name(); }
326 };
327 
328 #else
329 
330 template <class Comp>
332 {
333 private:
334  Comp comp_;
335 
336 protected:
337  virtual void realpop() {
338  candidateList_[0] = candidateList_.back();
339  candidateList_.pop_back();
340  fixTop();
341  }
343  virtual void fixTop() {
344  const size_t size = candidateList_.size();
345  if (size > 1) {
346  CoinTreeSiblings** candidates = &candidateList_[0];
347  CoinTreeSiblings* s = candidates[0];
348  --candidates;
349  size_t pos = 1;
350  size_t ch;
351  for (ch = 2; ch < size; pos = ch, ch *= 2) {
352  if (comp_(candidates[ch+1], candidates[ch]))
353  ++ch;
354  if (comp_(s, candidates[ch]))
355  break;
356  candidates[pos] = candidates[ch];
357  }
358  if (ch == size) {
359  if (comp_(candidates[ch], s)) {
360  candidates[pos] = candidates[ch];
361  pos = ch;
362  }
363  }
364  candidates[pos] = s;
365  }
366  }
367  virtual void realpush(CoinTreeSiblings* s) {
368  candidateList_.push_back(s);
369  CoinTreeSiblings** candidates = &candidateList_[0];
370  --candidates;
371  size_t pos = candidateList_.size();
372  size_t ch;
373  for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
374  if (comp_(candidates[ch], s))
375  break;
376  candidates[pos] = candidates[ch];
377  }
378  candidates[pos] = s;
379  }
380 
381 public:
386  std::sort(candidateList_.begin(), candidateList_.end(), comp_);
388  size_ = t.size();
389  }
390  virtual ~CoinSearchTree() {}
391  const char* compName() const { return Comp::name(); }
392 };
393 
394 #endif
395 
396 //#############################################################################
397 
402 };
403 
405 {
406 private:
409 private:
414  bool hasUB_;
415 
418 
419 public:
421  candidates_(NULL),
422  numSolution(0),
424  {}
426  delete candidates_;
427  }
428 
429  inline void setTree(CoinSearchTreeBase* t) {
430  delete candidates_;
431  candidates_ = t;
432  }
433  inline CoinSearchTreeBase* getTree() const {
434  return candidates_;
435  }
436 
437  inline bool empty() const { return candidates_->empty(); }
438  inline size_t size() const { return candidates_->size(); }
439  inline size_t numInserted() const { return candidates_->numInserted(); }
440  inline CoinTreeNode* top() const { return candidates_->top(); }
441  inline void pop() { candidates_->pop(); }
442  inline void push(CoinTreeNode* node, const bool incrInserted = true) {
443  candidates_->push(1, &node, incrInserted);
444  }
445  inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) {
446  candidates_->push(s, incrInserted);
447  }
448  inline void push(const int n, CoinTreeNode** nodes,
449  const bool incrInserted = true) {
450  candidates_->push(n, nodes, incrInserted);
451  }
452 
454  return candidates_->top();
455  }
456  inline double bestQuality() const {
457  return candidates_->top()->getQuality();
458  }
459  void newSolution(double solValue);
461 };
462 
463 //#############################################################################
464 
465 #endif
const char * compName() const
CoinSearchTreeBase * candidates_
bool recentlyReevaluatedSearchStrategy_
variable used to test whether we need to reevaluate search strategy
virtual void realpop()=0
bool operator<(const BitVector128 &b0, const BitVector128 &b1)
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
BitVector128 preferred_
void set(unsigned int bits[4])
CoinTreeSiblings(const int n, CoinTreeNode **nodes)
unsigned int bits_[4]
virtual void realpop()
int numInserted() const
virtual void fixTop()
After changing data in the top node, fix the heap.
void push(CoinTreeNode *node, const bool incrInserted=true)
void setBit(int i)
CoinNodeAction
double quality_
Some quality for the node.
void setQuality(double q)
CoinSearchTreeManager & operator=(const CoinSearchTreeManager &)
CoinTreeNode * top() const
double getTrueLB() const
CoinSearchTree(const CoinSearchTreeBase &t)
Function objects to compare search tree nodes.
bool advanceNode()
returns false if cannot be advanced
void printPref() const
CoinTreeNode * currentNode() const
double true_lower_bound_
A true lower bound on the node.
void push(int numNodes, CoinTreeNode **nodes, const bool incrInserted=true)
virtual const char * compName() const =0
std::vector< CoinTreeSiblings * > candidateList_
std::string str() const
int getDepth() const
CoinTreeNode & operator=(const CoinTreeNode &x)
friend bool operator<(const BitVector128 &b0, const BitVector128 &b1)
static const char * name()
void setDepth(int d)
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
void newSolution(double solValue)
CoinSearchTreeBase & operator=(const CoinSearchTreeBase &)
CoinTreeNode ** siblings_
CoinTreeSiblings(const CoinTreeSiblings &s)
Depth First Search.
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)
int toProcess() const
CoinTreeSiblings & operator=(const CoinTreeSiblings &)
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 clearBit(int i)
virtual void fixTop()=0
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
Definition: CoinFinite.hpp:18
CoinTreeNode * bestQualityCandidate() const
double getQuality() const
virtual ~CoinTreeNode()
CoinTreeNode * top() const
void setTrueLB(double tlb)
size_t numInserted() const
virtual void realpush(CoinTreeSiblings *s)=0
virtual ~CoinSearchTreeBase()
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const