Ignore:
Timestamp:
Sep 27, 2010 12:55:11 PM (9 years ago)
Author:
lou
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcTree.hpp

    r1393 r1506  
    1313#include "CbcCompare.hpp"
    1414
    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.
     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.
    1927*/
    2028//#define CBC_DUBIOUS_HEAP
     
    2331#endif
    2432#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*/
    2552class CbcTree {
    2653
    2754public:
    28 
    29     // Default Constructor
     55    /*! \name Constructors and related */
     56//@{
     57    /// Default Constructor
    3058    CbcTree ();
    3159
    32     // Copy constructor
    33     CbcTree ( const CbcTree & rhs);
    34     // = operator
    35     CbcTree & operator=(const CbcTree & rhs);
    36 
     60    /// Copy constructor
     61    CbcTree (const CbcTree &rhs);
     62
     63    /// = operator
     64    CbcTree & operator=(const CbcTree &rhs);
     65
     66    /// Destructor
    3767    virtual ~CbcTree();
    3868
    3969    /// Clone
    4070    virtual CbcTree * clone() const;
     71
    4172    /// Create C++ lines to get to current state
    42     virtual void generateCpp( FILE * ) {}
     73    virtual void generateCpp(FILE *) {}
     74//@}
    4375
    4476    /*! \name Heap access and maintenance methods */
    4577//@{
    46 
    4778    /// Set comparison function and resort heap
    48     void setComparison(CbcCompareBase  &compare);
     79    void setComparison(CbcCompareBase &compare);
    4980
    5081    /// Return the top node of the heap
     
    5283
    5384    /// Add a node to the heap
    54     virtual void push(CbcNode * x);
     85    virtual void push(CbcNode *x);
    5586
    5687    /// Remove the top node from the heap
    5788    virtual void pop() ;
    58     /// Gets best node and takes off heap
     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    */
    5996    virtual CbcNode * bestNode(double cutoff);
    6097
    61 //@}
    62     /*! \name vector methods */
    63 //@{
    64 
    65     /// Test if empty *** note may be overridden
     98    /*! \brief Rebuild the heap */
     99    virtual void rebuild() ;
     100//@}
     101
     102    /*! \name Direct node access methods */
     103//@{
     104    /// Test for an empty tree
    66105    virtual bool empty() ;
    67106
    68107    /// 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     }
     108    virtual int size() const { return static_cast<int>(nodes_.size()); }
    76109
    77110    /// Return a node pointer
    78     inline CbcNode * nodePointer (int i) const {
    79         return nodes_[i];
    80     }
    81 
    82 
     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]; }
    83115//@}
    84116
    85117    /*! \name Search tree maintenance */
    86118//@{
    87 
    88119    /*! \brief Prune the tree using an objective function cutoff
    89120
    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 
     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    */
    96125    virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    97126
     
    104133    /// Get best possible objective function in the tree
    105134    virtual double getBestPossibleObjective();
     135
    106136    /// Reset maximum node number
    107     inline void resetNodeNumbers() {
    108         maximumNodeNumber_ = 0;
    109     }
     137    inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
     138
    110139    /// Get maximum node number
    111     inline int maximumNodeNumber() const {
    112         return maximumNodeNumber_;
    113     }
     140    inline int maximumNodeNumber() const { return maximumNodeNumber_; }
     141
    114142    /// Set number of branches
    115     inline void setNumberBranching(int value) {
    116         numberBranching_ = value;
    117     }
     143    inline void setNumberBranching(int value) { numberBranching_ = value; }
     144
    118145    /// Get number of branches
    119     inline int getNumberBranching() const {
    120         return numberBranching_;
    121     }
     146    inline int getNumberBranching() const { return numberBranching_; }
     147
    122148    /// Set maximum branches
    123     inline void setMaximumBranching(int value) {
    124         maximumBranching_ = value;
    125     }
     149    inline void setMaximumBranching(int value) { maximumBranching_ = value; }
     150
    126151    /// Get maximum branches
    127     inline int getMaximumBranching() const {
    128         return maximumBranching_;
    129     }
     152    inline int getMaximumBranching() const { return maximumBranching_; }
     153
    130154    /// Get branched variables
    131     inline unsigned int * branched() const {
    132         return branched_;
    133     }
     155    inline unsigned int * branched() const { return branched_; }
     156
    134157    /// Get bounds
    135     inline int * newBounds() const {
    136         return newBound_;
    137     }
     158    inline int * newBounds() const { return newBound_; }
     159
    138160    /// Adds branching information to complete state
    139161    void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
     
    143165    void increaseSpace();
    144166//@}
     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
    145176protected:
     177    /// Storage vector for the heap
    146178    std::vector <CbcNode *> nodes_;
    147     CbcCompare comparison_;     ///> Sort function for heap ordering.
     179          /// Sort predicate for heap ordering.
     180    CbcCompare comparison_;
    148181    /// Maximum "node" number so far to split ties
    149182    int maximumNodeNumber_;
     
    160193    int * newBound_;
    161194};
    162 /*! \class tree
    163     \brief Implementation of live set as a managed array.
     195
     196#ifdef JJF_ZERO // not used
     197/*! \brief Implementation of live set as a managed array.
    164198
    165199    This class is used to hold the set of live nodes in the search tree.
    166200*/
    167 
    168 #ifdef JJF_ZERO // not used
    169201class CbcTreeArray : public CbcTree {
    170202
     
    326358#endif
    327359#else
     360/* CBC_DUBIOUS_HEAP is defined
     361
     362  See note at top of file. This code is highly suspect.
     363  -- lh, 100921 --
     364*/
    328365class CbcTree {
    329366
Note: See TracChangeset for help on using the changeset viewer.