CbcTree.hpp
Go to the documentation of this file.
1 /* $Id: CbcTree.hpp 1393 2009-12-11 00:29:38Z lou $ */
2 // Copyright (C) 2004, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 #ifndef CbcTree_H
5 #define CbcTree_H
6 
7 #include <vector>
8 #include <algorithm>
9 #include <cmath>
10 
11 #include "CoinFinite.hpp"
12 #include "CoinHelperFunctions.hpp"
13 #include "CbcCompare.hpp"
14 
20 //#define CBC_DUBIOUS_HEAP
21 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
22 //#define CBC_DUBIOUS_HEAP
23 #endif
24 #ifndef CBC_DUBIOUS_HEAP
25 class CbcTree {
26 
27 public:
28 
29  // Default Constructor
30  CbcTree ();
31 
32  // Copy constructor
33  CbcTree ( const CbcTree & rhs);
34  // = operator
35  CbcTree & operator=(const CbcTree & rhs);
36 
37  virtual ~CbcTree();
38 
40  virtual CbcTree * clone() const;
42  virtual void generateCpp( FILE * ) {}
43 
46 
48  void setComparison(CbcCompareBase &compare);
49 
51  virtual CbcNode * top() const;
52 
54  virtual void push(CbcNode * x);
55 
57  virtual void pop() ;
59  virtual CbcNode * bestNode(double cutoff);
60 
62 
64 
66  virtual bool empty() ;
67 
69  virtual int size() const {
70  return nodes_.size();
71  }
73  inline CbcNode * operator [] (int i) const {
74  return nodes_[i];
75  }
76 
78  inline CbcNode * nodePointer (int i) const {
79  return nodes_[i];
80  }
81 
82 
84 
87 
96  virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
97 
100 
102  virtual void endSearch() {}
103 
105  virtual double getBestPossibleObjective();
107  inline void resetNodeNumbers() {
108  maximumNodeNumber_ = 0;
109  }
111  inline int maximumNodeNumber() const {
112  return maximumNodeNumber_;
113  }
115  inline void setNumberBranching(int value) {
116  numberBranching_ = value;
117  }
119  inline int getNumberBranching() const {
120  return numberBranching_;
121  }
123  inline void setMaximumBranching(int value) {
124  maximumBranching_ = value;
125  }
127  inline int getMaximumBranching() const {
128  return maximumBranching_;
129  }
131  inline unsigned int * branched() const {
132  return branched_;
133  }
135  inline int * newBounds() const {
136  return newBound_;
137  }
139  void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
140  const double * currentLower,
141  const double * currentUpper);
143  void increaseSpace();
145 protected:
146  std::vector <CbcNode *> nodes_;
148 
158  unsigned int * branched_;
160  int * newBound_;
161 };
168 #ifdef JJF_ZERO // not used
169 class CbcTreeArray : public CbcTree {
170 
171 public:
172 
173  // Default Constructor
174  CbcTreeArray ();
175 
176  // Copy constructor
177  CbcTreeArray ( const CbcTreeArray & rhs);
178  // = operator
179  CbcTreeArray & operator=(const CbcTreeArray & rhs);
180 
181  virtual ~CbcTreeArray();
182 
184  virtual CbcTree * clone() const;
186  virtual void generateCpp( FILE * ) {}
187 
190 
192  void setComparison(CbcCompareBase &compare);
193 
195  virtual void push(CbcNode * x);
196 
198  virtual CbcNode * bestNode(double cutoff);
199 
201 
203 
205  virtual bool empty() ;
206 
208 
211 
220  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
222  virtual double getBestPossibleObjective();
224 protected:
227  CbcNode * lastNode_;
229  CbcNode * lastNodePopped_;
231  int switches_;
232 
233 };
234 
236 #include "CoinSearchTree.hpp"
243 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
244 
245 public:
246 
247  // Default Constructor
248  CbcNewTree ();
249 
250  // Copy constructor
251  CbcNewTree ( const CbcNewTree & rhs);
252  // = operator
253  CbcNewTree & operator=(const CbcNewTree & rhs);
254 
255  virtual ~CbcNewTree();
256 
258  virtual CbcNewTree * clone() const;
260  virtual void generateCpp( FILE * ) {}
261 
264 
266  void setComparison(CbcCompareBase &compare);
267 
269  virtual CbcNode * top() const;
270 
272  virtual void push(CbcNode * x);
273 
275  virtual void pop() ;
277  virtual CbcNode * bestNode(double cutoff);
278 
280 
282 
284  virtual bool empty() ;
285 
287  inline int size() const {
288  return nodes_.size();
289  }
290 
292  inline CbcNode * operator [] (int i) const {
293  return nodes_[i];
294  }
295 
297  inline CbcNode * nodePointer (int i) const {
298  return nodes_[i];
299  }
300 
302 
305 
314  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
315 
318 
320  virtual void endSearch() {}
322 protected:
323 
324 
325 };
326 #endif
327 #else
328 class CbcTree {
329 
330 public:
331 
332  // Default Constructor
333  CbcTree ();
334 
335  // Copy constructor
336  CbcTree ( const CbcTree & rhs);
337  // = operator
338  CbcTree & operator=(const CbcTree & rhs);
339 
340  virtual ~CbcTree();
341 
343  virtual CbcTree * clone() const;
345  virtual void generateCpp( FILE * fp) {}
346 
349 
351  void setComparison(CbcCompareBase &compare);
352 
354  virtual CbcNode * top() const;
355 
357  virtual void push(CbcNode * x);
358 
360  virtual void pop() ;
362  virtual CbcNode * bestNode(double cutoff);
363 
365 
367 
369  //virtual bool empty() ;
370 
372  inline int size() const {
373  return nodes_.size();
374  }
375 
377  inline CbcNode * operator [] (int i) const {
378  return nodes_[i];
379  }
380 
382  inline CbcNode * nodePointer (int i) const {
383  return nodes_[i];
384  }
385 
386  virtual bool empty();
387  //inline int size() const { return size_; }
388  void realpop();
390  void fixTop();
391  void realpush(CbcNode * node);
393 
396 
405  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
406 
409 
411  virtual void endSearch() {}
413  inline void resetNodeNumbers() {
414  maximumNodeNumber_ = 0;
415  }
417 protected:
418  std::vector <CbcNode *> nodes_;
420 
421  int maximumNodeNumber_;
422 
423 
424 };
425 #endif
426 #endif
427