source: branches/heur/Cbc/src/CbcTree.hpp @ 885

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

for deterministic parallel

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