source: trunk/Cbc/src/CbcTree.hpp @ 931

Last change on this file since 931 was 931, checked in by forrest, 14 years ago

changes to try and improve performance

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.6 KB
Line 
1// Copyright (C) 2004, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef CbcTree_H
4#define CbcTree_H
5
6#include <vector>
7#include <algorithm>
8#include <cmath>
9
10#include "CoinFinite.hpp"
11#include "CoinHelperFunctions.hpp"
12
13/*! \class tree
14    \brief Implementation of live set as a heap.
15
16    This class is used to hold the set of live nodes in the search tree.
17*/
18//#define CBC_DUBIOUS_HEAP
19#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
20//#define CBC_DUBIOUS_HEAP
21#endif
22#ifndef CBC_DUBIOUS_HEAP
23class CbcTree {
24
25public:
26
27  // Default Constructor
28  CbcTree ();
29
30  // Copy constructor
31  CbcTree ( const CbcTree & rhs);
32  // = operator
33  CbcTree & operator=(const CbcTree & rhs);
34   
35  virtual ~CbcTree();
36
37  /// Clone
38  virtual CbcTree * clone() const;
39  /// Create C++ lines to get to current state
40  virtual void generateCpp( FILE * fp) {}
41
42/*! \name Heap access and maintenance methods */
43//@{
44
45  /// Set comparison function and resort heap
46  void setComparison(CbcCompareBase  &compare);
47
48  /// Return the top node of the heap
49  virtual CbcNode * top() const;
50
51  /// Add a node to the heap
52  virtual void push(CbcNode * x);
53
54  /// Remove the top node from the heap
55  virtual void pop() ;
56  /// Gets best node and takes off heap
57  virtual CbcNode * bestNode(double cutoff);
58
59//@}
60/*! \name vector methods */
61//@{
62
63  /// Test if empty *** note may be overridden
64  virtual bool empty() ;
65
66  /// Return size
67  virtual int size() const
68  {return nodes_.size();}
69  /// [] operator
70  inline CbcNode * operator [] (int i) const
71  { return nodes_[i];}
72
73  /// Return a node pointer
74  inline CbcNode * nodePointer (int i) const
75  { return nodes_[i];}
76
77
78//@}
79
80/*! \name Search tree maintenance */
81//@{
82
83/*! \brief Prune the tree using an objective function cutoff
84
85  This routine removes all nodes with objective worst than the
86  specified cutoff value.
87  It also sets bestPossibleObjective to best
88  of all on tree before deleting.
89*/
90
91  virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
92
93  /// Get best on list using alternate method
94  CbcNode * bestAlternate();
95
96  /// We may have got an intelligent tree so give it one more chance
97  virtual void endSearch() {}
98
99  /// Get best possible objective function in the tree
100  virtual double getBestPossibleObjective();
101  /// Reset maximum node number
102  inline void resetNodeNumbers()
103  { maximumNodeNumber_=0;}
104//@}
105protected:
106  std::vector <CbcNode *> nodes_;
107  CbcCompare comparison_;       ///> Sort function for heap ordering.
108  /// Maximum "node" number so far to split ties
109  int maximumNodeNumber_;
110};
111
112/// New style
113#include "CoinSearchTree.hpp"
114/*! \class tree
115    \brief Implementation of live set as a heap.
116
117    This class is used to hold the set of live nodes in the search tree.
118*/
119
120class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
121
122public:
123
124  // Default Constructor
125  CbcNewTree ();
126
127  // Copy constructor
128  CbcNewTree ( const CbcNewTree & rhs);
129  // = operator
130  CbcNewTree & operator=(const CbcNewTree & rhs);
131   
132  virtual ~CbcNewTree();
133
134  /// Clone
135  virtual CbcNewTree * clone() const;
136  /// Create C++ lines to get to current state
137  virtual void generateCpp( FILE * fp) {}
138
139/*! \name Heap access and maintenance methods */
140//@{
141
142  /// Set comparison function and resort heap
143  void setComparison(CbcCompareBase  &compare);
144
145  /// Return the top node of the heap
146  virtual CbcNode * top() const;
147
148  /// Add a node to the heap
149  virtual void push(CbcNode * x);
150
151  /// Remove the top node from the heap
152  virtual void pop() ;
153  /// Gets best node and takes off heap
154  virtual CbcNode * bestNode(double cutoff);
155
156//@}
157/*! \name vector methods */
158//@{
159
160  /// Test if empty *** note may be overridden
161  virtual bool empty() ;
162
163  /// Return size
164  inline int size() const
165  { return nodes_.size();}
166
167  /// [] operator
168  inline CbcNode * operator [] (int i) const
169  { return nodes_[i];}
170
171  /// Return a node pointer
172  inline CbcNode * nodePointer (int i) const
173  { return nodes_[i];}
174
175//@}
176
177/*! \name Search tree maintenance */
178//@{
179
180/*! \brief Prune the tree using an objective function cutoff
181
182  This routine removes all nodes with objective worst than the
183  specified cutoff value.
184  It also sets bestPossibleObjective to best
185  of all on tree before deleting.
186*/
187
188  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
189
190  /// Get best on list using alternate method
191  CbcNode * bestAlternate();
192
193  /// We may have got an intelligent tree so give it one more chance
194  virtual void endSearch() {}
195//@}
196protected:
197
198
199};
200#else
201class CbcTree {
202
203public:
204
205  // Default Constructor
206  CbcTree ();
207
208  // Copy constructor
209  CbcTree ( const CbcTree & rhs);
210  // = operator
211  CbcTree & operator=(const CbcTree & rhs);
212   
213  virtual ~CbcTree();
214
215  /// Clone
216  virtual CbcTree * clone() const;
217  /// Create C++ lines to get to current state
218  virtual void generateCpp( FILE * fp) {}
219
220/*! \name Heap access and maintenance methods */
221//@{
222
223  /// Set comparison function and resort heap
224  void setComparison(CbcCompareBase  &compare);
225
226  /// Return the top node of the heap
227  virtual CbcNode * top() const;
228
229  /// Add a node to the heap
230  virtual void push(CbcNode * x);
231
232  /// Remove the top node from the heap
233  virtual void pop() ;
234  /// Gets best node and takes off heap
235  virtual CbcNode * bestNode(double cutoff);
236
237//@}
238/*! \name vector methods */
239//@{
240
241  /// Test if empty *** note may be overridden
242  //virtual bool empty() ;
243
244  /// Return size
245  inline int size() const
246  { return nodes_.size();}
247
248  /// [] operator
249  inline CbcNode * operator [] (int i) const
250  { return nodes_[i];}
251
252  /// Return a node pointer
253  inline CbcNode * nodePointer (int i) const
254  { return nodes_[i];}
255 
256  virtual bool empty();
257  //inline int size() const { return size_; }
258  void realpop();
259  /** After changing data in the top node, fix the heap */
260  void fixTop();
261  void realpush(CbcNode * node);
262//@}
263
264/*! \name Search tree maintenance */
265//@{
266
267/*! \brief Prune the tree using an objective function cutoff
268
269  This routine removes all nodes with objective worst than the
270  specified cutoff value.
271  It also sets bestPossibleObjective to best
272  of all on tree before deleting.
273*/
274
275  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
276
277  /// Get best on list using alternate method
278  CbcNode * bestAlternate();
279
280  /// We may have got an intelligent tree so give it one more chance
281  virtual void endSearch() {}
282  /// Reset maximum node number
283  inline void resetNodeNumbers()
284  { maximumNodeNumber_=0;}
285//@}
286protected:
287  std::vector <CbcNode *> nodes_;
288  CbcCompare comparison_;       ///> Sort function for heap ordering.
289  /// Maximum "node" number so far to split ties
290  int maximumNodeNumber_;
291
292
293};
294#endif
295#endif
296
Note: See TracBrowser for help on using the repository browser.