CbcTree.hpp

Go to the documentation of this file.
00001 /* $Id: CbcTree.hpp 1506 2010-09-27 16:55:11Z lou $ */
00002 // Copyright (C) 2004, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
00004 #ifndef CbcTree_H
00005 #define CbcTree_H
00006 
00007 #include <vector>
00008 #include <algorithm>
00009 #include <cmath>
00010 
00011 #include "CoinFinite.hpp"
00012 #include "CoinHelperFunctions.hpp"
00013 #include "CbcCompare.hpp"
00014 
00028 //#define CBC_DUBIOUS_HEAP
00029 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
00030 //#define CBC_DUBIOUS_HEAP
00031 #endif
00032 #ifndef CBC_DUBIOUS_HEAP
00033 
00052 class CbcTree {
00053 
00054 public:
00057 
00058     CbcTree ();
00059 
00061     CbcTree (const CbcTree &rhs);
00062 
00064     CbcTree & operator=(const CbcTree &rhs);
00065 
00067     virtual ~CbcTree();
00068 
00070     virtual CbcTree * clone() const;
00071 
00073     virtual void generateCpp(FILE *) {}
00075 
00078 
00079     void setComparison(CbcCompareBase &compare);
00080 
00082     virtual CbcNode * top() const;
00083 
00085     virtual void push(CbcNode *x);
00086 
00088     virtual void pop() ;
00089 
00096     virtual CbcNode * bestNode(double cutoff);
00097 
00099     virtual void rebuild() ;
00101 
00104 
00105     virtual bool empty() ;
00106 
00108     virtual int size() const { return static_cast<int>(nodes_.size()); }
00109 
00111     inline CbcNode * operator [] (int i) const { return nodes_[i]; }
00112 
00114     inline CbcNode * nodePointer (int i) const { return nodes_[i]; }
00116 
00125     virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00126 
00128     CbcNode * bestAlternate();
00129 
00131     virtual void endSearch() {}
00132 
00134     virtual double getBestPossibleObjective();
00135 
00137     inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
00138 
00140     inline int maximumNodeNumber() const { return maximumNodeNumber_; }
00141 
00143     inline void setNumberBranching(int value) { numberBranching_ = value; }
00144 
00146     inline int getNumberBranching() const { return numberBranching_; }
00147 
00149     inline void setMaximumBranching(int value) { maximumBranching_ = value; }
00150 
00152     inline int getMaximumBranching() const { return maximumBranching_; }
00153 
00155     inline unsigned int * branched() const { return branched_; }
00156 
00158     inline int * newBounds() const { return newBound_; }
00159 
00161     void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
00162                                  const double * currentLower,
00163                                  const double * currentUpper);
00165     void increaseSpace();
00167 
00168 # if CBC_DEBUG_HEAP > 0
00169 
00172     void validateHeap() ;
00174 # endif
00175 
00176 protected:
00178     std::vector <CbcNode *> nodes_;
00180     CbcCompare comparison_;
00182     int maximumNodeNumber_;
00184     int numberBranching_;
00186     int maximumBranching_;
00191     unsigned int * branched_;
00193     int * newBound_;
00194 };
00195 
00196 #ifdef JJF_ZERO // not used
00197 
00201 class CbcTreeArray : public CbcTree {
00202 
00203 public:
00204 
00205     // Default Constructor
00206     CbcTreeArray ();
00207 
00208     // Copy constructor
00209     CbcTreeArray ( const CbcTreeArray & rhs);
00210     // = operator
00211     CbcTreeArray & operator=(const CbcTreeArray & rhs);
00212 
00213     virtual ~CbcTreeArray();
00214 
00216     virtual CbcTree * clone() const;
00218     virtual void generateCpp( FILE * ) {}
00219 
00222 
00224     void setComparison(CbcCompareBase  &compare);
00225 
00227     virtual void push(CbcNode * x);
00228 
00230     virtual CbcNode * bestNode(double cutoff);
00231 
00233 
00235 
00237     virtual bool empty() ;
00238 
00240 
00243 
00252     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00254     virtual double getBestPossibleObjective();
00256 protected:
00259     CbcNode * lastNode_;
00261     CbcNode * lastNodePopped_;
00263     int switches_;
00264 
00265 };
00266 
00268 #include "CoinSearchTree.hpp"
00275 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
00276 
00277 public:
00278 
00279     // Default Constructor
00280     CbcNewTree ();
00281 
00282     // Copy constructor
00283     CbcNewTree ( const CbcNewTree & rhs);
00284     // = operator
00285     CbcNewTree & operator=(const CbcNewTree & rhs);
00286 
00287     virtual ~CbcNewTree();
00288 
00290     virtual CbcNewTree * clone() const;
00292     virtual void generateCpp( FILE * ) {}
00293 
00296 
00298     void setComparison(CbcCompareBase  &compare);
00299 
00301     virtual CbcNode * top() const;
00302 
00304     virtual void push(CbcNode * x);
00305 
00307     virtual void pop() ;
00309     virtual CbcNode * bestNode(double cutoff);
00310 
00312 
00314 
00316     virtual bool empty() ;
00317 
00319     inline int size() const {
00320         return nodes_.size();
00321     }
00322 
00324     inline CbcNode * operator [] (int i) const {
00325         return nodes_[i];
00326     }
00327 
00329     inline CbcNode * nodePointer (int i) const {
00330         return nodes_[i];
00331     }
00332 
00334 
00337 
00346     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00347 
00349     CbcNode * bestAlternate();
00350 
00352     virtual void endSearch() {}
00354 protected:
00355 
00356 
00357 };
00358 #endif
00359 #else
00360 /* CBC_DUBIOUS_HEAP is defined
00361 
00362   See note at top of file. This code is highly suspect.
00363   -- lh, 100921 --
00364 */
00365 class CbcTree {
00366 
00367 public:
00368 
00369     // Default Constructor
00370     CbcTree ();
00371 
00372     // Copy constructor
00373     CbcTree ( const CbcTree & rhs);
00374     // = operator
00375     CbcTree & operator=(const CbcTree & rhs);
00376 
00377     virtual ~CbcTree();
00378 
00380     virtual CbcTree * clone() const;
00382     virtual void generateCpp( FILE * fp) {}
00383 
00386 
00388     void setComparison(CbcCompareBase  &compare);
00389 
00391     virtual CbcNode * top() const;
00392 
00394     virtual void push(CbcNode * x);
00395 
00397     virtual void pop() ;
00399     virtual CbcNode * bestNode(double cutoff);
00400 
00402 
00404 
00406     //virtual bool empty() ;
00407 
00409     inline int size() const {
00410         return nodes_.size();
00411     }
00412 
00414     inline CbcNode * operator [] (int i) const {
00415         return nodes_[i];
00416     }
00417 
00419     inline CbcNode * nodePointer (int i) const {
00420         return nodes_[i];
00421     }
00422 
00423     virtual bool empty();
00424     //inline int size() const { return size_; }
00425     void realpop();
00427     void fixTop();
00428     void realpush(CbcNode * node);
00430 
00433 
00442     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00443 
00445     CbcNode * bestAlternate();
00446 
00448     virtual void endSearch() {}
00450     inline void resetNodeNumbers() {
00451         maximumNodeNumber_ = 0;
00452     }
00454 protected:
00455     std::vector <CbcNode *> nodes_;
00456     CbcCompare comparison_;     
00457 
00458     int maximumNodeNumber_;
00459 
00460 
00461 };
00462 #endif
00463 #endif
00464 

Generated on Tue Jun 14 23:14:03 2011 for Cbc by  doxygen 1.4.7