source: branches/sandbox/Cbc/src/CbcTree.hpp @ 1315

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

final changes before cleaning

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