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

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

chnages to try and make faster

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.3 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/*! \class tree
147    \brief Implementation of live set as a managed array.
148
149    This class is used to hold the set of live nodes in the search tree.
150*/
151
152class CbcTreeArray : public CbcTree {
153
154public:
155
156  // Default Constructor
157  CbcTreeArray ();
158
159  // Copy constructor
160  CbcTreeArray ( const CbcTreeArray & rhs);
161  // = operator
162  CbcTreeArray & operator=(const CbcTreeArray & rhs);
163   
164  virtual ~CbcTreeArray();
165
166  /// Clone
167  virtual CbcTree * clone() const;
168  /// Create C++ lines to get to current state
169  virtual void generateCpp( FILE * fp) {}
170
171/*! \name Heap access and maintenance methods */
172//@{
173
174  /// Set comparison function and resort heap
175  void setComparison(CbcCompareBase  &compare);
176
177  /// Add a node to the heap
178  virtual void push(CbcNode * x);
179
180  /// Gets best node and takes off heap
181  virtual CbcNode * bestNode(double cutoff);
182
183//@}
184/*! \name vector methods */
185//@{
186
187  /// Test if empty *** note may be overridden
188  virtual bool empty() ;
189
190//@}
191
192/*! \name Search tree maintenance */
193//@{
194
195/*! \brief Prune the tree using an objective function cutoff
196
197  This routine removes all nodes with objective worst than the
198  specified cutoff value.
199  It also sets bestPossibleObjective to best
200  of all on tree before deleting.
201*/
202
203  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
204  /// Get best possible objective function in the tree
205  virtual double getBestPossibleObjective();
206//@}
207protected:
208  /// Returns
209  /// Last node
210  CbcNode * lastNode_;
211  /// Last node popped
212  CbcNode * lastNodePopped_;
213  /// Not used yet
214  int switches_;
215
216};
217
218/// New style
219#include "CoinSearchTree.hpp"
220/*! \class tree
221    \brief Implementation of live set as a heap.
222
223    This class is used to hold the set of live nodes in the search tree.
224*/
225
226class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
227
228public:
229
230  // Default Constructor
231  CbcNewTree ();
232
233  // Copy constructor
234  CbcNewTree ( const CbcNewTree & rhs);
235  // = operator
236  CbcNewTree & operator=(const CbcNewTree & rhs);
237   
238  virtual ~CbcNewTree();
239
240  /// Clone
241  virtual CbcNewTree * clone() const;
242  /// Create C++ lines to get to current state
243  virtual void generateCpp( FILE * fp) {}
244
245/*! \name Heap access and maintenance methods */
246//@{
247
248  /// Set comparison function and resort heap
249  void setComparison(CbcCompareBase  &compare);
250
251  /// Return the top node of the heap
252  virtual CbcNode * top() const;
253
254  /// Add a node to the heap
255  virtual void push(CbcNode * x);
256
257  /// Remove the top node from the heap
258  virtual void pop() ;
259  /// Gets best node and takes off heap
260  virtual CbcNode * bestNode(double cutoff);
261
262//@}
263/*! \name vector methods */
264//@{
265
266  /// Test if empty *** note may be overridden
267  virtual bool empty() ;
268
269  /// Return size
270  inline int size() const
271  { return nodes_.size();}
272
273  /// [] operator
274  inline CbcNode * operator [] (int i) const
275  { return nodes_[i];}
276
277  /// Return a node pointer
278  inline CbcNode * nodePointer (int i) const
279  { return nodes_[i];}
280
281//@}
282
283/*! \name Search tree maintenance */
284//@{
285
286/*! \brief Prune the tree using an objective function cutoff
287
288  This routine removes all nodes with objective worst than the
289  specified cutoff value.
290  It also sets bestPossibleObjective to best
291  of all on tree before deleting.
292*/
293
294  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
295
296  /// Get best on list using alternate method
297  CbcNode * bestAlternate();
298
299  /// We may have got an intelligent tree so give it one more chance
300  virtual void endSearch() {}
301//@}
302protected:
303
304
305};
306#else
307class CbcTree {
308
309public:
310
311  // Default Constructor
312  CbcTree ();
313
314  // Copy constructor
315  CbcTree ( const CbcTree & rhs);
316  // = operator
317  CbcTree & operator=(const CbcTree & rhs);
318   
319  virtual ~CbcTree();
320
321  /// Clone
322  virtual CbcTree * clone() const;
323  /// Create C++ lines to get to current state
324  virtual void generateCpp( FILE * fp) {}
325
326/*! \name Heap access and maintenance methods */
327//@{
328
329  /// Set comparison function and resort heap
330  void setComparison(CbcCompareBase  &compare);
331
332  /// Return the top node of the heap
333  virtual CbcNode * top() const;
334
335  /// Add a node to the heap
336  virtual void push(CbcNode * x);
337
338  /// Remove the top node from the heap
339  virtual void pop() ;
340  /// Gets best node and takes off heap
341  virtual CbcNode * bestNode(double cutoff);
342
343//@}
344/*! \name vector methods */
345//@{
346
347  /// Test if empty *** note may be overridden
348  //virtual bool empty() ;
349
350  /// Return size
351  inline int size() const
352  { return nodes_.size();}
353
354  /// [] operator
355  inline CbcNode * operator [] (int i) const
356  { return nodes_[i];}
357
358  /// Return a node pointer
359  inline CbcNode * nodePointer (int i) const
360  { return nodes_[i];}
361 
362  virtual bool empty();
363  //inline int size() const { return size_; }
364  void realpop();
365  /** After changing data in the top node, fix the heap */
366  void fixTop();
367  void realpush(CbcNode * node);
368//@}
369
370/*! \name Search tree maintenance */
371//@{
372
373/*! \brief Prune the tree using an objective function cutoff
374
375  This routine removes all nodes with objective worst than the
376  specified cutoff value.
377  It also sets bestPossibleObjective to best
378  of all on tree before deleting.
379*/
380
381  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
382
383  /// Get best on list using alternate method
384  CbcNode * bestAlternate();
385
386  /// We may have got an intelligent tree so give it one more chance
387  virtual void endSearch() {}
388  /// Reset maximum node number
389  inline void resetNodeNumbers()
390  { maximumNodeNumber_=0;}
391//@}
392protected:
393  std::vector <CbcNode *> nodes_;
394  CbcCompare comparison_;       ///> Sort function for heap ordering.
395  /// Maximum "node" number so far to split ties
396  int maximumNodeNumber_;
397
398
399};
400#endif
401#endif
402
Note: See TracBrowser for help on using the repository browser.