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

Last change on this file since 777 was 777, checked in by forrest, 12 years ago

for bonmin

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.1 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
70//@}
71
72/*! \name Search tree maintenance */
73//@{
74
75/*! \brief Prune the tree using an objective function cutoff
76
77  This routine removes all nodes with objective worst than the
78  specified cutoff value.
79  It also sets bestPossibleObjective to best
80  of all on tree before deleting.
81*/
82
83  virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
84
85  /// Get best on list using alternate method
86  CbcNode * bestAlternate();
87
88  /// We may have got an intelligent tree so give it one more chance
89  virtual void endSearch() {}
90
91  /// Get best possible objective function in the tree
92  virtual double getBestPossibleObjective();
93//@}
94protected:
95  std::vector <CbcNode *> nodes_;
96  CbcCompare comparison_;       ///> Sort function for heap ordering.
97
98
99};
100
101/// New style
102#include "CoinSearchTree.hpp"
103/*! \class tree
104    \brief Implementation of live set as a heap.
105
106    This class is used to hold the set of live nodes in the search tree.
107*/
108
109class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
110
111public:
112
113  // Default Constructor
114  CbcNewTree ();
115
116  // Copy constructor
117  CbcNewTree ( const CbcNewTree & rhs);
118  // = operator
119  CbcNewTree & operator=(const CbcNewTree & rhs);
120   
121  virtual ~CbcNewTree();
122
123  /// Clone
124  virtual CbcNewTree * clone() const;
125  /// Create C++ lines to get to current state
126  virtual void generateCpp( FILE * fp) {}
127
128/*! \name Heap access and maintenance methods */
129//@{
130
131  /// Set comparison function and resort heap
132  void setComparison(CbcCompareBase  &compare);
133
134  /// Return the top node of the heap
135  virtual CbcNode * top() const;
136
137  /// Add a node to the heap
138  virtual void push(CbcNode * x);
139
140  /// Remove the top node from the heap
141  virtual void pop() ;
142  /// Gets best node and takes off heap
143  virtual CbcNode * bestNode(double cutoff);
144
145//@}
146/*! \name vector methods */
147//@{
148
149  /// Test if empty *** note may be overridden
150  virtual bool empty() ;
151
152  /// Return size
153  inline int size() const
154  { return nodes_.size();}
155
156  /// [] operator
157  inline CbcNode * operator [] (int i) const
158  { return nodes_[i];}
159
160  /// Return a node pointer
161  inline CbcNode * nodePointer (int i) const
162  { return nodes_[i];}
163
164//@}
165
166/*! \name Search tree maintenance */
167//@{
168
169/*! \brief Prune the tree using an objective function cutoff
170
171  This routine removes all nodes with objective worst than the
172  specified cutoff value.
173  It also sets bestPossibleObjective to best
174  of all on tree before deleting.
175*/
176
177  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
178
179  /// Get best on list using alternate method
180  CbcNode * bestAlternate();
181
182  /// We may have got an intelligent tree so give it one more chance
183  virtual void endSearch() {}
184//@}
185protected:
186
187
188};
189#else
190class CbcTree {
191
192public:
193
194  // Default Constructor
195  CbcTree ();
196
197  // Copy constructor
198  CbcTree ( const CbcTree & rhs);
199  // = operator
200  CbcTree & operator=(const CbcTree & rhs);
201   
202  virtual ~CbcTree();
203
204  /// Clone
205  virtual CbcTree * clone() const;
206  /// Create C++ lines to get to current state
207  virtual void generateCpp( FILE * fp) {}
208
209/*! \name Heap access and maintenance methods */
210//@{
211
212  /// Set comparison function and resort heap
213  void setComparison(CbcCompareBase  &compare);
214
215  /// Return the top node of the heap
216  virtual CbcNode * top() const;
217
218  /// Add a node to the heap
219  virtual void push(CbcNode * x);
220
221  /// Remove the top node from the heap
222  virtual void pop() ;
223  /// Gets best node and takes off heap
224  virtual CbcNode * bestNode(double cutoff);
225
226//@}
227/*! \name vector methods */
228//@{
229
230  /// Test if empty *** note may be overridden
231  //virtual bool empty() ;
232
233  /// Return size
234  inline int size() const
235  { return nodes_.size();}
236
237  /// [] operator
238  inline CbcNode * operator [] (int i) const
239  { return nodes_[i];}
240
241  /// Return a node pointer
242  inline CbcNode * nodePointer (int i) const
243  { return nodes_[i];}
244 
245  virtual bool empty();
246  //inline int size() const { return size_; }
247  void realpop();
248  /** After changing data in the top node, fix the heap */
249  void fixTop();
250  void realpush(CbcNode * node);
251//@}
252
253/*! \name Search tree maintenance */
254//@{
255
256/*! \brief Prune the tree using an objective function cutoff
257
258  This routine removes all nodes with objective worst than the
259  specified cutoff value.
260  It also sets bestPossibleObjective to best
261  of all on tree before deleting.
262*/
263
264  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
265
266  /// Get best on list using alternate method
267  CbcNode * bestAlternate();
268
269  /// We may have got an intelligent tree so give it one more chance
270  virtual void endSearch() {}
271//@}
272protected:
273  std::vector <CbcNode *> nodes_;
274  CbcCompare comparison_;       ///> Sort function for heap ordering.
275
276
277};
278#endif
279#endif
280
Note: See TracBrowser for help on using the repository browser.