Cbc trunk
|
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