CoinUtils 2.11.10
Loading...
Searching...
No Matches
CoinSearchTree.hpp
Go to the documentation of this file.
1/* $Id$ */
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"
16
17// #define DEBUG_PRINT
18
19//#############################################################################
20
22 friend bool operator<(const BitVector128 &b0, const BitVector128 &b1);
23
24private:
25 unsigned int bits_[4];
26
27public:
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
37bool operator<(const BitVector128 &b0, const BitVector128 &b1);
38
39//#############################################################################
40
45protected:
55 int f = -1,
56 double q = -COIN_DBL_MAX,
57 double tlb = -COIN_DBL_MAX,
59 : depth_(d)
61 , quality_(q)
63 , preferred_(p)
64 {
65 }
75 {
76 if (this != &x) {
77 depth_ = x.depth_;
82 }
83 return *this;
84 }
85
86private:
88 int depth_;
95 double quality_;
102
103public:
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
122private:
125
126private:
130
131public:
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 }
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
237private:
240
241protected:
242 std::vector< CoinTreeSiblings * > candidateList_;
244 int size_;
245
246protected:
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
258public:
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();
287 if (!s->advanceNode()) {
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 {
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
325template < class Comp >
326class CoinSearchTree : public CoinSearchTreeBase {
327private:
328 Comp comp_;
329
330protected:
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
347public:
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
368template < class Comp >
370private:
371 Comp comp_;
372
373protected:
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
421public:
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
449
451private:
454
455private:
460 bool hasUB_;
461
464
465public:
473 {
474 delete candidates_;
475 }
476
478 {
479 delete candidates_;
480 candidates_ = t;
481 }
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 double COIN_DBL_MAX
void CoinDisjointCopyN(const T *from, const CoinBigIndex size, T *to)
This helper function copies an array to another location.
bool operator<(const BitVector128 &b0, const BitVector128 &b1)
CoinNodeAction
@ CoinAddNodeToCandidates
@ CoinDiveIntoNode
@ CoinTestNodeForDiving
void set(unsigned int bits[4])
friend bool operator<(const BitVector128 &b0, const BitVector128 &b1)
void setBit(int i)
BitVector128(unsigned int bits[4])
unsigned int bits_[4]
std::string str() const
void clearBit(int i)
virtual void realpop()=0
virtual void fixTop()=0
virtual const char * compName() const =0
const std::vector< CoinTreeSiblings * > & getCandidates() const
CoinSearchTreeBase & operator=(const CoinSearchTreeBase &)
CoinSearchTreeBase(const CoinSearchTreeBase &)
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_
void push(const CoinTreeSiblings &sib, const bool incrInserted=true)
CoinTreeNode * top() const
virtual void realpush(CoinTreeSiblings *s)=0
void push(int numNodes, CoinTreeNode **nodes, const bool incrInserted=true)
bool hasUB_
Whether there is an upper bound or not.
void push(const int n, CoinTreeNode **nodes, const bool incrInserted=true)
void setTree(CoinSearchTreeBase *t)
CoinSearchTreeManager & operator=(const CoinSearchTreeManager &)
void push(const CoinTreeSiblings &s, const bool incrInserted=true)
CoinSearchTreeBase * getTree() const
CoinSearchTreeManager(const CoinSearchTreeManager &)
CoinTreeNode * top() const
CoinTreeNode * bestQualityCandidate() const
void push(CoinTreeNode *node, const bool incrInserted=true)
bool recentlyReevaluatedSearchStrategy_
variable used to test whether we need to reevaluate search strategy
CoinSearchTreeBase * candidates_
void newSolution(double solValue)
CoinSearchTree(const CoinSearchTreeBase &t)
virtual void realpush(CoinTreeSiblings *s)
virtual void fixTop()
After changing data in the top node, fix the heap.
virtual void realpop()
virtual ~CoinSearchTree()
const char * compName() const
A class from which the real tree nodes should be derived from.
int depth_
The depth of the node in the tree.
BitVector128 getPreferred() const
double getTrueLB() const
double true_lower_bound_
A true lower bound on the node.
int fractionality_
A measure of fractionality, e.g., the number of unsatisfied integrality requirements.
CoinTreeNode & operator=(const CoinTreeNode &x)
void setTrueLB(double tlb)
double getQuality() const
double quality_
Some quality for the node.
CoinTreeNode(const CoinTreeNode &x)
void setPreferred(BitVector128 p)
CoinTreeNode(int d, int f=-1, double q=-COIN_DBL_MAX, double tlb=-COIN_DBL_MAX, BitVector128 p=BitVector128())
void setDepth(int d)
void setQuality(double q)
int getFractionality() const
BitVector128 preferred_
virtual ~CoinTreeNode()
int getDepth() const
void setFractionality(int f)
CoinTreeNode * currentNode() const
bool advanceNode()
returns false if cannot be advanced
CoinTreeSiblings(const CoinTreeSiblings &s)
CoinTreeNode ** siblings_
CoinTreeSiblings & operator=(const CoinTreeSiblings &)
void printPref() const
CoinTreeSiblings(const int n, CoinTreeNode **nodes)
static const char * name()
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const
static const char * name()
Function objects to compare search tree nodes.
bool operator()(const CoinTreeSiblings *x, const CoinTreeSiblings *y) const