Cgl  0.60.3
CoinSearchTree.hpp
Go to the documentation of this file.
1 /* \$Id: CoinSearchTree.hpp 2083 2019-01-06 19:38:09Z unxusr \$ */
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
24 private:
25  unsigned int bits_[4];
26
27 public:
28  BitVector128();
29  BitVector128(unsigned int bits[4]);
31  void set(unsigned int bits[4]);
32  void setBit(int i);
33  void clearBit(int i);
34  std::string str() const;
35 };
36
37 bool operator<(const BitVector128 &b0, const BitVector128 &b1);
38
39 //#############################################################################
40
44 class CoinTreeNode {
45 protected:
47  : depth_(-1)
48  , fractionality_(-1)
51  , preferred_()
52  {
53  }
54  CoinTreeNode(int d,
55  int f = -1,
56  double q = -COIN_DBL_MAX,
57  double tlb = -COIN_DBL_MAX,
59  : depth_(d)
60  , fractionality_(f)
61  , quality_(q)
62  , true_lower_bound_(tlb)
63  , preferred_(p)
64  {
65  }
67  : depth_(x.depth_)
69  , quality_(x.quality_)
72  {
73  }
75  {
76  if (this != &x) {
77  depth_ = x.depth_;
79  quality_ = x.quality_;
82  }
83  return *this;
84  }
85
86 private:
88  int depth_;
95  double quality_;
102
103 public:
104  virtual ~CoinTreeNode() {}
105
106  inline int getDepth() const { return depth_; }
107  inline int getFractionality() const { return fractionality_; }
108  inline double getQuality() const { return quality_; }
109  inline double getTrueLB() const { return true_lower_bound_; }
110  inline BitVector128 getPreferred() const { return preferred_; }
111
112  inline void setDepth(int d) { depth_ = d; }
113  inline void setFractionality(int f) { fractionality_ = f; }
114  inline void setQuality(double q) { quality_ = q; }
115  inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; }
116  inline void setPreferred(BitVector128 p) { preferred_ = p; }
117 };
118
119 //==============================================================================
120
122 private:
125
126 private:
127  int current_;
130
131 public:
132  CoinTreeSiblings(const int n, CoinTreeNode **nodes)
133  : current_(0)
134  , numSiblings_(n)
135  , siblings_(new CoinTreeNode *[n])
136  {
137  CoinDisjointCopyN(nodes, n, siblings_);
138  }
140  : current_(s.current_)
143  {
145  }
146  ~CoinTreeSiblings() { delete[] siblings_; }
147  inline CoinTreeNode *currentNode() const { return siblings_[current_]; }
149  inline bool advanceNode() { return ++current_ != numSiblings_; }
150  inline int toProcess() const { return numSiblings_ - current_; }
151  inline int size() const { return numSiblings_; }
152  inline void printPref() const
153  {
154  for (int i = 0; i < numSiblings_; ++i) {
155  std::string pref = siblings_[i]->getPreferred().str();
156  printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
157  }
158  }
159 };
160
161 //#############################################################################
162
169  static inline const char *name() { return "CoinSearchTreeComparePreferred"; }
170  inline bool operator()(const CoinTreeSiblings *x,
171  const CoinTreeSiblings *y) const
172  {
173  const CoinTreeNode *xNode = x->currentNode();
174  const CoinTreeNode *yNode = y->currentNode();
175  const BitVector128 xPref = xNode->getPreferred();
176  const BitVector128 yPref = yNode->getPreferred();
177  bool retval = true;
178  if (xPref < yPref) {
179  retval = true;
180  } else if (yPref < xPref) {
181  retval = false;
182  } else {
183  retval = xNode->getQuality() < yNode->getQuality();
184  }
185 #ifdef DEBUG_PRINT
186  printf("Comparing xpref (%s) and ypref (%s) : %s\n",
187  xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F");
188 #endif
189  return retval;
190  }
191 };
192
193 //-----------------------------------------------------------------------------
196  static inline const char *name() { return "CoinSearchTreeCompareDepth"; }
197  inline bool operator()(const CoinTreeSiblings *x,
198  const CoinTreeSiblings *y) const
199  {
200 #if 1
201  return x->currentNode()->getDepth() >= y->currentNode()->getDepth();
202 #else
203  if (x->currentNode()->getDepth() > y->currentNode()->getDepth())
204  return 1;
205  if (x->currentNode()->getDepth() == y->currentNode()->getDepth() && x->currentNode()->getQuality() <= y->currentNode()->getQuality())
206  return 1;
207  return 0;
208 #endif
209  }
210 };
211
212 //-----------------------------------------------------------------------------
213 /* Breadth First Search */
215  static inline const char *name() { return "CoinSearchTreeCompareBreadth"; }
216  inline bool operator()(const CoinTreeSiblings *x,
217  const CoinTreeSiblings *y) const
218  {
219  return x->currentNode()->getDepth() < y->currentNode()->getDepth();
220  }
221 };
222
223 //-----------------------------------------------------------------------------
226  static inline const char *name() { return "CoinSearchTreeCompareBest"; }
227  inline bool operator()(const CoinTreeSiblings *x,
228  const CoinTreeSiblings *y) const
229  {
230  return x->currentNode()->getQuality() < y->currentNode()->getQuality();
231  }
232 };
233
234 //#############################################################################
235
237 private:
240
241 protected:
242  std::vector< CoinTreeSiblings * > candidateList_;
244  int size_;
245
246 protected:
248  : candidateList_()
249  , numInserted_(0)
250  , size_(0)
251  {
252  }
253
254  virtual void realpop() = 0;
255  virtual void realpush(CoinTreeSiblings *s) = 0;
256  virtual void fixTop() = 0;
257
258 public:
259  virtual ~CoinSearchTreeBase() {}
260  virtual const char *compName() const = 0;
261
262  inline const std::vector< CoinTreeSiblings * > &getCandidates() const
263  {
264  return candidateList_;
265  }
266  inline bool empty() const { return candidateList_.empty(); }
267  inline int size() const { return size_; }
268  inline int numInserted() const { return numInserted_; }
269  inline CoinTreeNode *top() const
270  {
271  if (size_ == 0 || candidateList_.size() == 0)
272  return NULL;
273 #ifdef DEBUG_PRINT
274  char output[44];
275  output[43] = 0;
276  candidateList_.front()->currentNode()->getPreferred().print(output);
277  printf("top's pref: %s\n", output);
278 #endif
279  return candidateList_.front()->currentNode();
280  }
284  inline void pop()
285  {
286  CoinTreeSiblings *s = candidateList_.front();
288  realpop();
289  delete s;
290  } else {
291  fixTop();
292  }
293  --size_;
294  }
295  inline void push(int numNodes, CoinTreeNode **nodes,
296  const bool incrInserted = true)
297  {
298  CoinTreeSiblings *s = new CoinTreeSiblings(numNodes, nodes);
299  realpush(s);
300  if (incrInserted) {
301  numInserted_ += numNodes;
302  }
303  size_ += numNodes;
304  }
305  inline void push(const CoinTreeSiblings &sib,
306  const bool incrInserted = true)
307  {
308  CoinTreeSiblings *s = new CoinTreeSiblings(sib);
309 #ifdef DEBUG_PRINT
310  s->printPref();
311 #endif
312  realpush(s);
313  if (incrInserted) {
314  numInserted_ += sib.toProcess();
315  }
316  size_ += sib.toProcess();
317  }
318 };
319
320 //#############################################################################
321
322 // #define CAN_TRUST_STL_HEAP
323 #ifdef CAN_TRUST_STL_HEAP
324
325 template < class Comp >
326 class CoinSearchTree : public CoinSearchTreeBase {
327 private:
328  Comp comp_;
329
330 protected:
331  virtual void realpop()
332  {
333  candidateList_.pop_back();
334  }
335  virtual void fixTop()
336  {
337  CoinTreeSiblings *s = top();
338  realpop();
339  push(s, false);
340  }
341  virtual void realpush(CoinTreeSiblings *s)
342  {
343  nodes_.push_back(s);
344  std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
345  }
346
347 public:
350  , comp_()
351  {
352  }
355  , comp_()
356  {
358  std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
360  size_ = t.size_;
361  }
362  ~CoinSearchTree() {}
363  const char *compName() const { return Comp::name(); }
364 };
365
366 #else
367
368 template < class Comp >
370 private:
371  Comp comp_;
372
373 protected:
374  virtual void realpop()
375  {
376  candidateList_[0] = candidateList_.back();
377  candidateList_.pop_back();
378  fixTop();
379  }
381  virtual void fixTop()
382  {
383  const size_t size = candidateList_.size();
384  if (size > 1) {
385  CoinTreeSiblings **candidates = &candidateList_[0];
386  CoinTreeSiblings *s = candidates[0];
387  --candidates;
388  size_t pos = 1;
389  size_t ch;
390  for (ch = 2; ch < size; pos = ch, ch *= 2) {
391  if (comp_(candidates[ch + 1], candidates[ch]))
392  ++ch;
393  if (comp_(s, candidates[ch]))
394  break;
395  candidates[pos] = candidates[ch];
396  }
397  if (ch == size) {
398  if (comp_(candidates[ch], s)) {
399  candidates[pos] = candidates[ch];
400  pos = ch;
401  }
402  }
403  candidates[pos] = s;
404  }
405  }
406  virtual void realpush(CoinTreeSiblings *s)
407  {
408  candidateList_.push_back(s);
409  CoinTreeSiblings **candidates = &candidateList_[0];
410  --candidates;
411  size_t pos = candidateList_.size();
412  size_t ch;
413  for (ch = pos / 2; ch != 0; pos = ch, ch /= 2) {
414  if (comp_(candidates[ch], s))
415  break;
416  candidates[pos] = candidates[ch];
417  }
418  candidates[pos] = s;
419  }
420
421 public:
424  , comp_()
425  {
426  }
429  , comp_()
430  {
432  std::sort(candidateList_.begin(), candidateList_.end(), comp_);
434  size_ = t.size();
435  }
436  virtual ~CoinSearchTree() {}
437  const char *compName() const { return Comp::name(); }
438 };
439
440 #endif
441
442 //#############################################################################
443
448 };
449
451 private:
454
455 private:
460  bool hasUB_;
461
464
465 public:
467  : candidates_(NULL)
468  , numSolution(0)
470  {
471  }
473  {
474  delete candidates_;
475  }
476
477  inline void setTree(CoinSearchTreeBase *t)
478  {
479  delete candidates_;
480  candidates_ = t;
481  }
482  inline CoinSearchTreeBase *getTree() const
483  {
484  return candidates_;
485  }
486
487  inline bool empty() const { return candidates_->empty(); }
488  inline size_t size() const { return candidates_->size(); }
489  inline size_t numInserted() const { return candidates_->numInserted(); }
490  inline CoinTreeNode *top() const { return candidates_->top(); }
491  inline void pop() { candidates_->pop(); }
492  inline void push(CoinTreeNode *node, const bool incrInserted = true)
493  {
494  candidates_->push(1, &node, incrInserted);
495  }
496  inline void push(const CoinTreeSiblings &s, const bool incrInserted = true)
497  {
498  candidates_->push(s, incrInserted);
499  }
500  inline void push(const int n, CoinTreeNode **nodes,
501  const bool incrInserted = true)
502  {
503  candidates_->push(n, nodes, incrInserted);
504  }
505
507  {
508  return candidates_->top();
509  }
510  inline double bestQuality() const
511  {
512  return candidates_->top()->getQuality();
513  }
514  void newSolution(double solValue);
516 };
517
518 //#############################################################################
519
520 #endif
521
522 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
523 */
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.
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.
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.
std::vector< CoinTreeSiblings * > candidateList_
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.
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::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)
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
const std::vector< CoinTreeSiblings * > & getCandidates() 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