/build/buildd/coinor-cbc-2.5.0/Cbc/src/CbcTree.hpp
Go to the documentation of this file.
00001 /* $Id: CbcTree.hpp 1393 2009-12-11 00:29:38Z 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 
00020 //#define CBC_DUBIOUS_HEAP
00021 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
00022 //#define CBC_DUBIOUS_HEAP
00023 #endif
00024 #ifndef CBC_DUBIOUS_HEAP
00025 class CbcTree {
00026 
00027 public:
00028 
00029     // Default Constructor
00030     CbcTree ();
00031 
00032     // Copy constructor
00033     CbcTree ( const CbcTree & rhs);
00034     // = operator
00035     CbcTree & operator=(const CbcTree & rhs);
00036 
00037     virtual ~CbcTree();
00038 
00040     virtual CbcTree * clone() const;
00042     virtual void generateCpp( FILE * ) {}
00043 
00046 
00048     void setComparison(CbcCompareBase  &compare);
00049 
00051     virtual CbcNode * top() const;
00052 
00054     virtual void push(CbcNode * x);
00055 
00057     virtual void pop() ;
00059     virtual CbcNode * bestNode(double cutoff);
00060 
00062 
00064 
00066     virtual bool empty() ;
00067 
00069     virtual int size() const {
00070         return nodes_.size();
00071     }
00073     inline CbcNode * operator [] (int i) const {
00074         return nodes_[i];
00075     }
00076 
00078     inline CbcNode * nodePointer (int i) const {
00079         return nodes_[i];
00080     }
00081 
00082 
00084 
00087 
00096     virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00097 
00099     CbcNode * bestAlternate();
00100 
00102     virtual void endSearch() {}
00103 
00105     virtual double getBestPossibleObjective();
00107     inline void resetNodeNumbers() {
00108         maximumNodeNumber_ = 0;
00109     }
00111     inline int maximumNodeNumber() const {
00112         return maximumNodeNumber_;
00113     }
00115     inline void setNumberBranching(int value) {
00116         numberBranching_ = value;
00117     }
00119     inline int getNumberBranching() const {
00120         return numberBranching_;
00121     }
00123     inline void setMaximumBranching(int value) {
00124         maximumBranching_ = value;
00125     }
00127     inline int getMaximumBranching() const {
00128         return maximumBranching_;
00129     }
00131     inline unsigned int * branched() const {
00132         return branched_;
00133     }
00135     inline int * newBounds() const {
00136         return newBound_;
00137     }
00139     void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
00140                                  const double * currentLower,
00141                                  const double * currentUpper);
00143     void increaseSpace();
00145 protected:
00146     std::vector <CbcNode *> nodes_;
00147     CbcCompare comparison_;     
00148 
00149     int maximumNodeNumber_;
00151     int numberBranching_;
00153     int maximumBranching_;
00158     unsigned int * branched_;
00160     int * newBound_;
00161 };
00168 #ifdef JJF_ZERO // not used
00169 class CbcTreeArray : public CbcTree {
00170 
00171 public:
00172 
00173     // Default Constructor
00174     CbcTreeArray ();
00175 
00176     // Copy constructor
00177     CbcTreeArray ( const CbcTreeArray & rhs);
00178     // = operator
00179     CbcTreeArray & operator=(const CbcTreeArray & rhs);
00180 
00181     virtual ~CbcTreeArray();
00182 
00184     virtual CbcTree * clone() const;
00186     virtual void generateCpp( FILE * ) {}
00187 
00190 
00192     void setComparison(CbcCompareBase  &compare);
00193 
00195     virtual void push(CbcNode * x);
00196 
00198     virtual CbcNode * bestNode(double cutoff);
00199 
00201 
00203 
00205     virtual bool empty() ;
00206 
00208 
00211 
00220     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00222     virtual double getBestPossibleObjective();
00224 protected:
00227     CbcNode * lastNode_;
00229     CbcNode * lastNodePopped_;
00231     int switches_;
00232 
00233 };
00234 
00236 #include "CoinSearchTree.hpp"
00243 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
00244 
00245 public:
00246 
00247     // Default Constructor
00248     CbcNewTree ();
00249 
00250     // Copy constructor
00251     CbcNewTree ( const CbcNewTree & rhs);
00252     // = operator
00253     CbcNewTree & operator=(const CbcNewTree & rhs);
00254 
00255     virtual ~CbcNewTree();
00256 
00258     virtual CbcNewTree * clone() const;
00260     virtual void generateCpp( FILE * ) {}
00261 
00264 
00266     void setComparison(CbcCompareBase  &compare);
00267 
00269     virtual CbcNode * top() const;
00270 
00272     virtual void push(CbcNode * x);
00273 
00275     virtual void pop() ;
00277     virtual CbcNode * bestNode(double cutoff);
00278 
00280 
00282 
00284     virtual bool empty() ;
00285 
00287     inline int size() const {
00288         return nodes_.size();
00289     }
00290 
00292     inline CbcNode * operator [] (int i) const {
00293         return nodes_[i];
00294     }
00295 
00297     inline CbcNode * nodePointer (int i) const {
00298         return nodes_[i];
00299     }
00300 
00302 
00305 
00314     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00315 
00317     CbcNode * bestAlternate();
00318 
00320     virtual void endSearch() {}
00322 protected:
00323 
00324 
00325 };
00326 #endif
00327 #else
00328 class CbcTree {
00329 
00330 public:
00331 
00332     // Default Constructor
00333     CbcTree ();
00334 
00335     // Copy constructor
00336     CbcTree ( const CbcTree & rhs);
00337     // = operator
00338     CbcTree & operator=(const CbcTree & rhs);
00339 
00340     virtual ~CbcTree();
00341 
00343     virtual CbcTree * clone() const;
00345     virtual void generateCpp( FILE * fp) {}
00346 
00349 
00351     void setComparison(CbcCompareBase  &compare);
00352 
00354     virtual CbcNode * top() const;
00355 
00357     virtual void push(CbcNode * x);
00358 
00360     virtual void pop() ;
00362     virtual CbcNode * bestNode(double cutoff);
00363 
00365 
00367 
00369     //virtual bool empty() ;
00370 
00372     inline int size() const {
00373         return nodes_.size();
00374     }
00375 
00377     inline CbcNode * operator [] (int i) const {
00378         return nodes_[i];
00379     }
00380 
00382     inline CbcNode * nodePointer (int i) const {
00383         return nodes_[i];
00384     }
00385 
00386     virtual bool empty();
00387     //inline int size() const { return size_; }
00388     void realpop();
00390     void fixTop();
00391     void realpush(CbcNode * node);
00393 
00396 
00405     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00406 
00408     CbcNode * bestAlternate();
00409 
00411     virtual void endSearch() {}
00413     inline void resetNodeNumbers() {
00414         maximumNodeNumber_ = 0;
00415     }
00417 protected:
00418     std::vector <CbcNode *> nodes_;
00419     CbcCompare comparison_;     
00420 
00421     int maximumNodeNumber_;
00422 
00423 
00424 };
00425 #endif
00426 #endif
00427