source: stable/2.4/Cbc/src/CbcTree.hpp @ 1271

Last change on this file since 1271 was 1271, checked in by forrest, 10 years ago

Creating new stable branch 2.4 from trunk (rev 1270)

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.3 KB
Line 
1/* $Id: CbcTree.hpp 1271 2009-11-05 15:57:25Z forrest $ */
2// Copyright (C) 2004, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef CbcTree_H
5#define CbcTree_H
6
7#include <vector>
8#include <algorithm>
9#include <cmath>
10
11#include "CoinFinite.hpp"
12#include "CoinHelperFunctions.hpp"
13
14/*! \class tree
15    \brief Implementation of live set as a heap.
16
17    This class is used to hold the set of live nodes in the search tree.
18*/
19//#define CBC_DUBIOUS_HEAP
20#if defined(_MSC_VER) || defined(__MNO_CYGWIN)
21//#define CBC_DUBIOUS_HEAP
22#endif
23#ifndef CBC_DUBIOUS_HEAP
24class CbcTree {
25
26public:
27
28  // Default Constructor
29  CbcTree ();
30
31  // Copy constructor
32  CbcTree ( const CbcTree & rhs);
33  // = operator
34  CbcTree & operator=(const CbcTree & rhs);
35   
36  virtual ~CbcTree();
37
38  /// Clone
39  virtual CbcTree * clone() const;
40  /// Create C++ lines to get to current state
41  virtual void generateCpp( FILE * ) {}
42
43/*! \name Heap access and maintenance methods */
44//@{
45
46  /// Set comparison function and resort heap
47  void setComparison(CbcCompareBase  &compare);
48
49  /// Return the top node of the heap
50  virtual CbcNode * top() const;
51
52  /// Add a node to the heap
53  virtual void push(CbcNode * x);
54
55  /// Remove the top node from the heap
56  virtual void pop() ;
57  /// Gets best node and takes off heap
58  virtual CbcNode * bestNode(double cutoff);
59
60//@}
61/*! \name vector methods */
62//@{
63
64  /// Test if empty *** note may be overridden
65  virtual bool empty() ;
66
67  /// Return size
68  virtual int size() const
69  {return nodes_.size();}
70  /// [] operator
71  inline CbcNode * operator [] (int i) const
72  { return nodes_[i];}
73
74  /// Return a node pointer
75  inline CbcNode * nodePointer (int i) const
76  { return nodes_[i];}
77
78
79//@}
80
81/*! \name Search tree maintenance */
82//@{
83
84/*! \brief Prune the tree using an objective function cutoff
85
86  This routine removes all nodes with objective worst than the
87  specified cutoff value.
88  It also sets bestPossibleObjective to best
89  of all on tree before deleting.
90*/
91
92  virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
93
94  /// Get best on list using alternate method
95  CbcNode * bestAlternate();
96
97  /// We may have got an intelligent tree so give it one more chance
98  virtual void endSearch() {}
99
100  /// Get best possible objective function in the tree
101  virtual double getBestPossibleObjective();
102  /// Reset maximum node number
103  inline void resetNodeNumbers()
104  { maximumNodeNumber_=0;}
105  /// Set number of branches
106  inline void setNumberBranching(int value)
107  { numberBranching_=value;}
108  /// Get number of branches
109  inline int getNumberBranching() const
110  { return numberBranching_;}
111  /// Set maximum branches
112  inline void setMaximumBranching(int value)
113  { maximumBranching_=value;}
114  /// Get maximum branches
115  inline int getMaximumBranching() const
116  { return maximumBranching_;}
117  /// Get branched variables
118  inline unsigned int * branched() const
119  { return branched_;}
120  /// Get bounds
121  inline int * newBounds() const
122  { return newBound_;}
123  /// Adds branching information to complete state
124  void addBranchingInformation(const CbcModel * model,const CbcNodeInfo * nodeInfo,
125                               const double * currentLower,
126                               const double * currentUpper);
127  /// Increase space for data
128  void increaseSpace();
129//@}
130protected:
131  std::vector <CbcNode *> nodes_;
132  CbcCompare comparison_;       ///> Sort function for heap ordering.
133  /// Maximum "node" number so far to split ties
134  int maximumNodeNumber_;
135  /// Size of variable list
136  int numberBranching_;
137  /// Maximum size of variable list
138  int maximumBranching_;
139  /** Integer variables branched or bounded
140      top bit set if new upper bound
141      next bit set if a branch
142  */
143  unsigned int * branched_;
144  /// New bound
145  int * newBound_;
146};
147/*! \class tree
148    \brief Implementation of live set as a managed array.
149
150    This class is used to hold the set of live nodes in the search tree.
151*/
152
153class CbcTreeArray : public CbcTree {
154
155public:
156
157  // Default Constructor
158  CbcTreeArray ();
159
160  // Copy constructor
161  CbcTreeArray ( const CbcTreeArray & rhs);
162  // = operator
163  CbcTreeArray & operator=(const CbcTreeArray & rhs);
164   
165  virtual ~CbcTreeArray();
166
167  /// Clone
168  virtual CbcTree * clone() const;
169  /// Create C++ lines to get to current state
170  virtual void generateCpp( FILE * ) {}
171
172/*! \name Heap access and maintenance methods */
173//@{
174
175  /// Set comparison function and resort heap
176  void setComparison(CbcCompareBase  &compare);
177
178  /// Add a node to the heap
179  virtual void push(CbcNode * x);
180
181  /// Gets best node and takes off heap
182  virtual CbcNode * bestNode(double cutoff);
183
184//@}
185/*! \name vector methods */
186//@{
187
188  /// Test if empty *** note may be overridden
189  virtual bool empty() ;
190
191//@}
192
193/*! \name Search tree maintenance */
194//@{
195
196/*! \brief Prune the tree using an objective function cutoff
197
198  This routine removes all nodes with objective worst than the
199  specified cutoff value.
200  It also sets bestPossibleObjective to best
201  of all on tree before deleting.
202*/
203
204  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
205  /// Get best possible objective function in the tree
206  virtual double getBestPossibleObjective();
207//@}
208protected:
209  /// Returns
210  /// Last node
211  CbcNode * lastNode_;
212  /// Last node popped
213  CbcNode * lastNodePopped_;
214  /// Not used yet
215  int switches_;
216
217};
218
219/// New style
220#include "CoinSearchTree.hpp"
221/*! \class tree
222    \brief Implementation of live set as a heap.
223
224    This class is used to hold the set of live nodes in the search tree.
225*/
226
227class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
228
229public:
230
231  // Default Constructor
232  CbcNewTree ();
233
234  // Copy constructor
235  CbcNewTree ( const CbcNewTree & rhs);
236  // = operator
237  CbcNewTree & operator=(const CbcNewTree & rhs);
238   
239  virtual ~CbcNewTree();
240
241  /// Clone
242  virtual CbcNewTree * clone() const;
243  /// Create C++ lines to get to current state
244  virtual void generateCpp( FILE * ) {}
245
246/*! \name Heap access and maintenance methods */
247//@{
248
249  /// Set comparison function and resort heap
250  void setComparison(CbcCompareBase  &compare);
251
252  /// Return the top node of the heap
253  virtual CbcNode * top() const;
254
255  /// Add a node to the heap
256  virtual void push(CbcNode * x);
257
258  /// Remove the top node from the heap
259  virtual void pop() ;
260  /// Gets best node and takes off heap
261  virtual CbcNode * bestNode(double cutoff);
262
263//@}
264/*! \name vector methods */
265//@{
266
267  /// Test if empty *** note may be overridden
268  virtual bool empty() ;
269
270  /// Return size
271  inline int size() const
272  { return nodes_.size();}
273
274  /// [] operator
275  inline CbcNode * operator [] (int i) const
276  { return nodes_[i];}
277
278  /// Return a node pointer
279  inline CbcNode * nodePointer (int i) const
280  { return nodes_[i];}
281
282//@}
283
284/*! \name Search tree maintenance */
285//@{
286
287/*! \brief Prune the tree using an objective function cutoff
288
289  This routine removes all nodes with objective worst than the
290  specified cutoff value.
291  It also sets bestPossibleObjective to best
292  of all on tree before deleting.
293*/
294
295  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
296
297  /// Get best on list using alternate method
298  CbcNode * bestAlternate();
299
300  /// We may have got an intelligent tree so give it one more chance
301  virtual void endSearch() {}
302//@}
303protected:
304
305
306};
307#else
308class CbcTree {
309
310public:
311
312  // Default Constructor
313  CbcTree ();
314
315  // Copy constructor
316  CbcTree ( const CbcTree & rhs);
317  // = operator
318  CbcTree & operator=(const CbcTree & rhs);
319   
320  virtual ~CbcTree();
321
322  /// Clone
323  virtual CbcTree * clone() const;
324  /// Create C++ lines to get to current state
325  virtual void generateCpp( FILE * fp) {}
326
327/*! \name Heap access and maintenance methods */
328//@{
329
330  /// Set comparison function and resort heap
331  void setComparison(CbcCompareBase  &compare);
332
333  /// Return the top node of the heap
334  virtual CbcNode * top() const;
335
336  /// Add a node to the heap
337  virtual void push(CbcNode * x);
338
339  /// Remove the top node from the heap
340  virtual void pop() ;
341  /// Gets best node and takes off heap
342  virtual CbcNode * bestNode(double cutoff);
343
344//@}
345/*! \name vector methods */
346//@{
347
348  /// Test if empty *** note may be overridden
349  //virtual bool empty() ;
350
351  /// Return size
352  inline int size() const
353  { return nodes_.size();}
354
355  /// [] operator
356  inline CbcNode * operator [] (int i) const
357  { return nodes_[i];}
358
359  /// Return a node pointer
360  inline CbcNode * nodePointer (int i) const
361  { return nodes_[i];}
362 
363  virtual bool empty();
364  //inline int size() const { return size_; }
365  void realpop();
366  /** After changing data in the top node, fix the heap */
367  void fixTop();
368  void realpush(CbcNode * node);
369//@}
370
371/*! \name Search tree maintenance */
372//@{
373
374/*! \brief Prune the tree using an objective function cutoff
375
376  This routine removes all nodes with objective worst than the
377  specified cutoff value.
378  It also sets bestPossibleObjective to best
379  of all on tree before deleting.
380*/
381
382  void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
383
384  /// Get best on list using alternate method
385  CbcNode * bestAlternate();
386
387  /// We may have got an intelligent tree so give it one more chance
388  virtual void endSearch() {}
389  /// Reset maximum node number
390  inline void resetNodeNumbers()
391  { maximumNodeNumber_=0;}
392//@}
393protected:
394  std::vector <CbcNode *> nodes_;
395  CbcCompare comparison_;       ///> Sort function for heap ordering.
396  /// Maximum "node" number so far to split ties
397  int maximumNodeNumber_;
398
399
400};
401#endif
402#endif
403
Note: See TracBrowser for help on using the repository browser.