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

Last change on this file since 1573 was 1573, checked in by lou, 8 years ago

Change to EPL license notice.

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