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

Last change on this file since 940 was 940, checked in by forrest, 11 years ago

for my experiments

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