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

Last change on this file since 1514 was 1506, checked in by lou, 9 years ago

Fix `Invalid heap' error in cl debug builds. Add validateHeap method to CbcTree? for future debugging.

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