1/* $Id: CoinSearchTree.hpp 1372 2011-01-03 23:31:00Z lou $ */
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
21class BitVector128 {
22 friend bool operator<(const BitVector128& b0, const BitVector128& b1);
23private:
24 unsigned int bits_[4];
25public:
26 BitVector128();
27 ~BitVector128() {}
28 void setBit(int i);
29 void clearBit(int i);
30 std::string str() const;
31};
32
33bool operator<(const BitVector128& b0, const BitVector128& b1);
34
35//#############################################################################
36
37/** A class from which the real tree nodes should be derived from. Some of the
38 data that undoubtedly exist in the real tree node is replicated here for
39 fast access. This class is used in the various comparison functions. */
40class CoinTreeNode {
41protected:
42 CoinTreeNode() :
43 depth_(-1),
44 fractionality_(-1),
45 quality_(-COIN_DBL_MAX),
46 true_lower_bound_(-COIN_DBL_MAX),
47 preferred_() {}
48 CoinTreeNode(int d,
49 int f = -1,
50 double q = -COIN_DBL_MAX,
51 double tlb = -COIN_DBL_MAX,
52 BitVector128 p = BitVector128()) :
53 depth_(d),
54 fractionality_(f),
55 quality_(q),
56 true_lower_bound_(tlb),
57 preferred_(p) {}
58 CoinTreeNode(const CoinTreeNode& x) :
59 depth_(x.depth_),
60 fractionality_(x.fractionality_),
61 quality_(x.quality_),
62 true_lower_bound_(x.true_lower_bound_),
63 preferred_(x.preferred_) {}
64 CoinTreeNode& operator=(const CoinTreeNode& x) {
65 if (this != &x) {
66 depth_ = x.depth_;
67 fractionality_ = x.fractionality_;
68 quality_ = x.quality_;
69 true_lower_bound_ = x.true_lower_bound_;
70 preferred_ = x.preferred_;
71 }
72 return *this;
73 }
74private:
75 /// The depth of the node in the tree
76 int depth_;
77 /** A measure of fractionality, e.g., the number of unsatisfied
78 integrality requirements */
79 int fractionality_;
80 /** Some quality for the node. For normal branch-and-cut problems the LP
81 relaxation value will do just fine. It is probably an OK approximation
82 even if column generation is done. */
83 double quality_;
84 /** A true lower bound on the node. May be -infinity. For normal
85 branch-and-cut problems the LP relaxation value is OK. It is different
86 when column generation is done. */
87 double true_lower_bound_;
88 /** */
89 BitVector128 preferred_;
90public:
91 virtual ~CoinTreeNode() {}
92
93 inline int getDepth() const { return depth_; }
94 inline int getFractionality() const { return fractionality_; }
95 inline double getQuality() const { return quality_; }
96 inline double getTrueLB() const { return true_lower_bound_; }
97 inline BitVector128 getPreferred() const { return preferred_; }
98
99 inline void setDepth(int d) { depth_ = d; }
100 inline void setFractionality(int f) { fractionality_ = f; }
101 inline void setQuality(double q) { quality_ = q; }
102 inline void setTrueLB(double tlb) { true_lower_bound_ = tlb; }
103 inline void setPreferred(BitVector128 p) { preferred_ = p; }
104};
105
106//==============================================================================
107
108class CoinTreeSiblings {
109private:
110 CoinTreeSiblings();
111 CoinTreeSiblings& operator=(const CoinTreeSiblings&);
112private:
113 int current_;
114 int numSiblings_;
115 CoinTreeNode** siblings_;
116public:
117 CoinTreeSiblings(const int n, CoinTreeNode** nodes) :
118 current_(0), numSiblings_(n), siblings_(new CoinTreeNode*[n])
119 {
120 CoinDisjointCopyN(nodes, n, siblings_);
121 }
122 CoinTreeSiblings(const CoinTreeSiblings& s) :
123 current_(s.current_),
124 numSiblings_(s.numSiblings_),
125 siblings_(new CoinTreeNode*[s.numSiblings_])
126 {
127 CoinDisjointCopyN(s.siblings_, s.numSiblings_, siblings_);
128 }
129 ~CoinTreeSiblings() { delete[] siblings_; }
130 inline CoinTreeNode* currentNode() const { return siblings_[current_]; }
131 /** returns false if cannot be advanced */
132 inline bool advanceNode() { return ++current_ != numSiblings_; }
133 inline int toProcess() const { return numSiblings_ - current_; }
134 inline int size() const { return numSiblings_; }
135 inline void printPref() const {
136 for (int i = 0; i < numSiblings_; ++i) {
137 std::string pref = siblings_[i]->getPreferred().str();
138 printf("prefs of sibligs: sibling[%i]: %s\n", i, pref.c_str());
139 }
140 }
141};
142
143//#############################################################################
144
145/** Function objects to compare search tree nodes. The comparison function
146 must return true if the first argument is "better" than the second one,
147 i.e., it should be processed first. */
148/*@{*/
149/** Depth First Search. */
150struct CoinSearchTreeComparePreferred {
151 static inline const char* name() { return "CoinSearchTreeComparePreferred"; }
152 inline bool operator()(const CoinTreeSiblings* x,
153 const CoinTreeSiblings* y) const {
154 const CoinTreeNode* xNode = x->currentNode();
155 const CoinTreeNode* yNode = y->currentNode();
156 const BitVector128 xPref = xNode->getPreferred();
157 const BitVector128 yPref = yNode->getPreferred();
158 bool retval = true;
159 if (xPref < yPref) {
160 retval = true;
161 } else if (yPref < xPref) {
162 retval = false;
163 } else {
164 retval = xNode->getQuality() < yNode->getQuality();
165 }
166#ifdef DEBUG_PRINT
167 printf("Comparing xpref (%s) and ypref (%s) : %s\n",
168 xpref.str().c_str(), ypref.str().c_str(), retval ? "T" : "F");
169#endif
170 return retval;
171 }
172};
173
174//-----------------------------------------------------------------------------
175/** Depth First Search. */
176struct CoinSearchTreeCompareDepth {
177 static inline const char* name() { return "CoinSearchTreeCompareDepth"; }
178 inline bool operator()(const CoinTreeSiblings* x,
179 const CoinTreeSiblings* y) const {
180#if 1
181 return x->currentNode()->getDepth() >= y->currentNode()->getDepth();
182#else
183 if(x->currentNode()->getDepth() > y->currentNode()->getDepth())
184 return 1;
185 if(x->currentNode()->getDepth() == y->currentNode()->getDepth() &&
186 x->currentNode()->getQuality() <= y->currentNode()->getQuality())
187 return 1;
188 return 0;
189#endif
190 }
191};
192
193//-----------------------------------------------------------------------------
194/* Breadth First Search */
195struct CoinSearchTreeCompareBreadth {
196 static inline const char* name() { return "CoinSearchTreeCompareBreadth"; }
197 inline bool operator()(const CoinTreeSiblings* x,
198 const CoinTreeSiblings* y) const {
199 return x->currentNode()->getDepth() < y->currentNode()->getDepth();
200 }
201};
202
203//-----------------------------------------------------------------------------
204/** Best first search */
205struct CoinSearchTreeCompareBest {
206 static inline const char* name() { return "CoinSearchTreeCompareBest"; }
207 inline bool operator()(const CoinTreeSiblings* x,
208 const CoinTreeSiblings* y) const {
209 return x->currentNode()->getQuality() < y->currentNode()->getQuality();
210 }
211};
212
213//#############################################################################
214
215class CoinSearchTreeBase
216{
217private:
218 CoinSearchTreeBase(const CoinSearchTreeBase&);
219 CoinSearchTreeBase& operator=(const CoinSearchTreeBase&);
220
221protected:
222 std::vector<CoinTreeSiblings*> candidateList_;
223 int numInserted_;
224 int size_;
225
226protected:
227 CoinSearchTreeBase() : candidateList_(), numInserted_(0), size_(0) {}
228
229 virtual void realpop() = 0;
230 virtual void realpush(CoinTreeSiblings* s) = 0;
231 virtual void fixTop() = 0;
232
233public:
234 virtual ~CoinSearchTreeBase() {}
235 virtual const char* compName() const = 0;
236
237 inline const std::vector<CoinTreeSiblings*>& getCandidates() const {
238 return candidateList_;
239 }
240 inline bool empty() const { return candidateList_.empty(); }
241 inline int size() const { return size_; }
242 inline int numInserted() const { return numInserted_; }
243 inline CoinTreeNode* top() const {
244 if (size_ == 0)
245 return nullptr;
246#ifdef DEBUG_PRINT
247 char output[44];
248 output[43] = 0;
249 candidateList_.front()->currentNode()->getPreferred().print(output);
250 printf("top's pref: %s\n", output);
251#endif
252 return candidateList_.front()->currentNode();
253 }
254 /** pop will advance the \c next pointer among the siblings on the top and
255 then moves the top to its correct position. #realpop is the method
256 that actually removes the element from the heap */
257 inline void pop() {
258 CoinTreeSiblings* s = candidateList_.front();
259 if (!s->advanceNode()) {
260 realpop();
261 delete s;
262 } else {
263 fixTop();
264 }
265 --size_;
266 }
267 inline void push(int numNodes, CoinTreeNode** nodes,
268 const bool incrInserted = true) {
269 CoinTreeSiblings* s = new CoinTreeSiblings(numNodes, nodes);
270 realpush(s);
271 if (incrInserted) {
272 numInserted_ += numNodes;
273 }
274 size_ += numNodes;
275 }
276 inline void push(const CoinTreeSiblings& sib,
277 const bool incrInserted = true) {
278 CoinTreeSiblings* s = new CoinTreeSiblings(sib);
279#ifdef DEBUG_PRINT
280 s->printPref();
281#endif
282 realpush(s);
283 if (incrInserted) {
284 numInserted_ += sib.toProcess();
285 }
286 size_ += sib.size();
287 }
288};
289
290//#############################################################################
291
292// #define CAN_TRUST_STL_HEAP
293#ifdef CAN_TRUST_STL_HEAP
294
295template <class Comp>
296class CoinSearchTree : public CoinSearchTreeBase
297{
298private:
299 Comp comp_;
300protected:
301 virtual void realpop() {
302 candidateList_.pop_back();
303 }
304 virtual void fixTop() {
305 CoinTreeSiblings* s = top();
306 realpop();
307 push(s, false);
308 }
309 virtual void realpush(CoinTreeSiblings* s) {
310 nodes_.push_back(s);
311 std::push_heap(candidateList_.begin(), candidateList_.end(), comp_);
312 }
313public:
314 CoinSearchTree() : CoinSearchTreeBase(), comp_() {}
315 CoinSearchTree(const CoinSearchTreeBase& t) :
316 CoinSearchTreeBase(), comp_() {
317 candidateList_ = t.getCandidates();
318 std::make_heap(candidateList_.begin(), candidateList_.end(), comp_);
319 numInserted_ = t.numInserted_;
320 size_ = t.size_;
321 }
322 ~CoinSearchTree() {}
323 const char* compName() const { return Comp::name(); }
324};
325
326#else
327
328template <class Comp>
329class CoinSearchTree : public CoinSearchTreeBase
330{
331private:
332 Comp comp_;
333
334protected:
335 virtual void realpop() override {
336 candidateList_[0] = candidateList_.back();
337 candidateList_.pop_back();
338 fixTop();
339 }
340 /** After changing data in the top node, fix the heap */
341 virtual void fixTop() override {
342 const size_t size = candidateList_.size();
343 if (size > 1) {
344 CoinTreeSiblings** candidates = &candidateList_[0];
345 CoinTreeSiblings* s = candidates[0];
346 --candidates;
347 size_t pos = 1;
348 size_t ch;
349 for (ch = 2; ch < size; pos = ch, ch *= 2) {
350 if (comp_(candidates[ch+1], candidates[ch]))
351 ++ch;
352 if (comp_(s, candidates[ch]))
353 break;
354 candidates[pos] = candidates[ch];
355 }
356 if (ch == size) {
357 if (comp_(candidates[ch], s)) {
358 candidates[pos] = candidates[ch];
359 pos = ch;
360 }
361 }
362 candidates[pos] = s;
363 }
364 }
365 virtual void realpush(CoinTreeSiblings* s) override {
366 candidateList_.push_back(s);
367 CoinTreeSiblings** candidates = &candidateList_[0];
368 --candidates;
369 size_t pos = candidateList_.size();
370 size_t ch;
371 for (ch = pos/2; ch != 0; pos = ch, ch /= 2) {
372 if (comp_(candidates[ch], s))
373 break;
374 candidates[pos] = candidates[ch];
375 }
376 candidates[pos] = s;
377 }
378
379public:
380 CoinSearchTree() : CoinSearchTreeBase(), comp_() {}
381 CoinSearchTree(const CoinSearchTreeBase& t) :
382 CoinSearchTreeBase(), comp_() {
383 candidateList_ = t.getCandidates();
384 std::sort(candidateList_.begin(), candidateList_.end(), comp_);
385 numInserted_ = t.numInserted();
386 size_ = t.size();
387 }
388 ~CoinSearchTree() {}
389 const char* compName() const override { return Comp::name(); }
390};
391
392#endif
393
394//#############################################################################
395
396enum CoinNodeAction {
397 CoinAddNodeToCandidates,
398 CoinTestNodeForDiving,
399 CoinDiveIntoNode
400};
401
402class CoinSearchTreeManager
403{
404private:
405 CoinSearchTreeManager(const CoinSearchTreeManager&);
406 CoinSearchTreeManager& operator=(const CoinSearchTreeManager&);
407private:
408 CoinSearchTreeBase* candidates_;
409 int numSolution;
410 /** Whether there is an upper bound or not. The upper bound may have come
411 as input, not necessarily from a solution */
412 bool hasUB_;
413
414 /** variable used to test whether we need to reevaluate search strategy */
415 bool recentlyReevaluatedSearchStrategy_;
416
417public:
418 CoinSearchTreeManager() :
419 candidates_(nullptr),
420 numSolution(0),
421 recentlyReevaluatedSearchStrategy_(true)
422 {}
423 virtual ~CoinSearchTreeManager() {
424 delete candidates_;
425 }
426
427 inline void setTree(CoinSearchTreeBase* t) {
428 delete candidates_;
429 candidates_ = t;
430 }
431 inline CoinSearchTreeBase* getTree() const {
432 return candidates_;
433 }
434
435 inline bool empty() const { return candidates_->empty(); }
436 inline size_t size() const { return candidates_->size(); }
437 inline size_t numInserted() const { return candidates_->numInserted(); }
438 inline CoinTreeNode* top() const { return candidates_->top(); }
439 inline void pop() { candidates_->pop(); }
440 inline void push(CoinTreeNode* node, const bool incrInserted = true) {
441 candidates_->push(1, &node, incrInserted);
442 }
443 inline void push(const CoinTreeSiblings& s, const bool incrInserted=true) {
444 candidates_->push(s, incrInserted);
445 }
446 inline void push(const int n, CoinTreeNode** nodes,
447 const bool incrInserted = true) {
448 candidates_->push(n, nodes, incrInserted);
449 }
450
451 inline CoinTreeNode* bestQualityCandidate() const {
452 return candidates_->top();
453 }
454 inline double bestQuality() const {
455 return candidates_->top()->getQuality();
456 }
457 void newSolution(double solValue);
458 void reevaluateSearchStrategy();
459};
460
461//#############################################################################
462
463#endif
464