Cbc trunk
CbcTree.hpp
Go to the documentation of this file.
00001 /* $Id$ */
00002 // Copyright (C) 2004, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
00004 // This code is licensed under the terms of the Eclipse Public License (EPL).
00005 
00006 #ifndef CbcTree_H
00007 #define CbcTree_H
00008 
00009 #include <vector>
00010 #include <algorithm>
00011 #include <cmath>
00012 
00013 #include "CoinHelperFunctions.hpp"
00014 #include "CbcCompare.hpp"
00015 
00029 //#define CBC_DUBIOUS_HEAP
00030 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
00031 //#define CBC_DUBIOUS_HEAP
00032 #endif
00033 #ifndef CBC_DUBIOUS_HEAP
00034 
00053 class CbcTree {
00054 
00055 public:
00058 
00059     CbcTree ();
00060 
00062     CbcTree (const CbcTree &rhs);
00063 
00065     CbcTree & operator=(const CbcTree &rhs);
00066 
00068     virtual ~CbcTree();
00069 
00071     virtual CbcTree * clone() const;
00072 
00074     virtual void generateCpp(FILE *) {}
00076 
00079 
00080     void setComparison(CbcCompareBase &compare);
00081 
00083     virtual CbcNode * top() const;
00084 
00086     virtual void push(CbcNode *x);
00087 
00089     virtual void pop() ;
00090 
00097     virtual CbcNode * bestNode(double cutoff);
00098 
00100     virtual void rebuild() ;
00102 
00105 
00106     virtual bool empty() ;
00107 
00109     virtual int size() const { return static_cast<int>(nodes_.size()); }
00110 
00112     inline CbcNode * operator [] (int i) const { return nodes_[i]; }
00113 
00115     inline CbcNode * nodePointer (int i) const { return nodes_[i]; }
00117 
00126     virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00127 
00129     CbcNode * bestAlternate();
00130 
00132     virtual void endSearch() {}
00133 
00135     virtual double getBestPossibleObjective();
00136 
00138     inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
00139 
00141     inline int maximumNodeNumber() const { return maximumNodeNumber_; }
00142 
00144     inline void setNumberBranching(int value) { numberBranching_ = value; }
00145 
00147     inline int getNumberBranching() const { return numberBranching_; }
00148 
00150     inline void setMaximumBranching(int value) { maximumBranching_ = value; }
00151 
00153     inline int getMaximumBranching() const { return maximumBranching_; }
00154 
00156     inline unsigned int * branched() const { return branched_; }
00157 
00159     inline int * newBounds() const { return newBound_; }
00160 
00162     void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
00163                                  const double * currentLower,
00164                                  const double * currentUpper);
00166     void increaseSpace();
00168 
00169 # if CBC_DEBUG_HEAP > 0
00170 
00173     void validateHeap() ;
00175 # endif
00176 
00177 protected:
00179     std::vector <CbcNode *> nodes_;
00181     CbcCompare comparison_;
00183     int maximumNodeNumber_;
00185     int numberBranching_;
00187     int maximumBranching_;
00192     unsigned int * branched_;
00194     int * newBound_;
00195 };
00196 
00197 #ifdef JJF_ZERO // not used
00198 
00202 class CbcTreeArray : public CbcTree {
00203 
00204 public:
00205 
00206     // Default Constructor
00207     CbcTreeArray ();
00208 
00209     // Copy constructor
00210     CbcTreeArray ( const CbcTreeArray & rhs);
00211     // = operator
00212     CbcTreeArray & operator=(const CbcTreeArray & rhs);
00213 
00214     virtual ~CbcTreeArray();
00215 
00217     virtual CbcTree * clone() const;
00219     virtual void generateCpp( FILE * ) {}
00220 
00223 
00225     void setComparison(CbcCompareBase  &compare);
00226 
00228     virtual void push(CbcNode * x);
00229 
00231     virtual CbcNode * bestNode(double cutoff);
00232 
00234 
00236 
00238     virtual bool empty() ;
00239 
00241 
00244 
00253     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00255     virtual double getBestPossibleObjective();
00257 protected:
00260     CbcNode * lastNode_;
00262     CbcNode * lastNodePopped_;
00264     int switches_;
00265 
00266 };
00267 
00269 #include "CoinSearchTree.hpp"
00276 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
00277 
00278 public:
00279 
00280     // Default Constructor
00281     CbcNewTree ();
00282 
00283     // Copy constructor
00284     CbcNewTree ( const CbcNewTree & rhs);
00285     // = operator
00286     CbcNewTree & operator=(const CbcNewTree & rhs);
00287 
00288     virtual ~CbcNewTree();
00289 
00291     virtual CbcNewTree * clone() const;
00293     virtual void generateCpp( FILE * ) {}
00294 
00297 
00299     void setComparison(CbcCompareBase  &compare);
00300 
00302     virtual CbcNode * top() const;
00303 
00305     virtual void push(CbcNode * x);
00306 
00308     virtual void pop() ;
00310     virtual CbcNode * bestNode(double cutoff);
00311 
00313 
00315 
00317     virtual bool empty() ;
00318 
00320     inline int size() const {
00321         return nodes_.size();
00322     }
00323 
00325     inline CbcNode * operator [] (int i) const {
00326         return nodes_[i];
00327     }
00328 
00330     inline CbcNode * nodePointer (int i) const {
00331         return nodes_[i];
00332     }
00333 
00335 
00338 
00347     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00348 
00350     CbcNode * bestAlternate();
00351 
00353     virtual void endSearch() {}
00355 protected:
00356 
00357 
00358 };
00359 #endif
00360 #else
00361 /* CBC_DUBIOUS_HEAP is defined
00362 
00363   See note at top of file. This code is highly suspect.
00364   -- lh, 100921 --
00365 */
00366 class CbcTree {
00367 
00368 public:
00369 
00370     // Default Constructor
00371     CbcTree ();
00372 
00373     // Copy constructor
00374     CbcTree ( const CbcTree & rhs);
00375     // = operator
00376     CbcTree & operator=(const CbcTree & rhs);
00377 
00378     virtual ~CbcTree();
00379 
00381     virtual CbcTree * clone() const;
00383     virtual void generateCpp( FILE * fp) {}
00384 
00387 
00389     void setComparison(CbcCompareBase  &compare);
00390 
00392     virtual CbcNode * top() const;
00393 
00395     virtual void push(CbcNode * x);
00396 
00398     virtual void pop() ;
00400     virtual CbcNode * bestNode(double cutoff);
00401 
00403 
00405 
00407     //virtual bool empty() ;
00408 
00410     inline int size() const {
00411         return nodes_.size();
00412     }
00413 
00415     inline CbcNode * operator [] (int i) const {
00416         return nodes_[i];
00417     }
00418 
00420     inline CbcNode * nodePointer (int i) const {
00421         return nodes_[i];
00422     }
00423 
00424     virtual bool empty();
00425     //inline int size() const { return size_; }
00426     void realpop();
00428     void fixTop();
00429     void realpush(CbcNode * node);
00431 
00434 
00443     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00444 
00446     CbcNode * bestAlternate();
00447 
00449     virtual void endSearch() {}
00451     inline void resetNodeNumbers() {
00452         maximumNodeNumber_ = 0;
00453     }
00455 protected:
00456     std::vector <CbcNode *> nodes_;
00457     CbcCompare comparison_;     
00458 
00459     int maximumNodeNumber_;
00460 
00461 
00462 };
00463 #endif
00464 #endif
00465 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines