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 #if 1 //ndef 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]; } 00116 void realpop(); 00118 void fixTop(); 00119 void realpush(CbcNode * node); 00121 00130 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); 00131 00133 CbcNode * bestAlternate(); 00134 00136 virtual void endSearch() {} 00137 00139 virtual double getBestPossibleObjective(); 00140 00142 inline void resetNodeNumbers() { maximumNodeNumber_ = 0; } 00143 00145 inline int maximumNodeNumber() const { return maximumNodeNumber_; } 00146 00148 inline void setNumberBranching(int value) { numberBranching_ = value; } 00149 00151 inline int getNumberBranching() const { return numberBranching_; } 00152 00154 inline void setMaximumBranching(int value) { maximumBranching_ = value; } 00155 00157 inline int getMaximumBranching() const { return maximumBranching_; } 00158 00160 inline unsigned int * branched() const { return branched_; } 00161 00163 inline int * newBounds() const { return newBound_; } 00164 00166 void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo, 00167 const double * currentLower, 00168 const double * currentUpper); 00170 void increaseSpace(); 00172 00173 # if CBC_DEBUG_HEAP > 0 00174 00177 void validateHeap() ; 00179 # endif 00180 00181 protected: 00183 std::vector <CbcNode *> nodes_; 00185 CbcCompare comparison_; 00187 int maximumNodeNumber_; 00189 int numberBranching_; 00191 int maximumBranching_; 00196 unsigned int * branched_; 00198 int * newBound_; 00199 }; 00200 00201 #ifdef JJF_ZERO // not used 00202 00206 class CbcTreeArray : public CbcTree { 00207 00208 public: 00209 00210 // Default Constructor 00211 CbcTreeArray (); 00212 00213 // Copy constructor 00214 CbcTreeArray ( const CbcTreeArray & rhs); 00215 // = operator 00216 CbcTreeArray & operator=(const CbcTreeArray & rhs); 00217 00218 virtual ~CbcTreeArray(); 00219 00221 virtual CbcTree * clone() const; 00223 virtual void generateCpp( FILE * ) {} 00224 00227 00229 void setComparison(CbcCompareBase &compare); 00230 00232 virtual void push(CbcNode * x); 00233 00235 virtual CbcNode * bestNode(double cutoff); 00236 00238 00240 00242 virtual bool empty() ; 00243 00245 00248 00257 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); 00259 virtual double getBestPossibleObjective(); 00261 protected: 00264 CbcNode * lastNode_; 00266 CbcNode * lastNodePopped_; 00268 int switches_; 00269 00270 }; 00271 00273 #include "CoinSearchTree.hpp" 00280 class CbcNewTree : public CbcTree, public CoinSearchTreeManager { 00281 00282 public: 00283 00284 // Default Constructor 00285 CbcNewTree (); 00286 00287 // Copy constructor 00288 CbcNewTree ( const CbcNewTree & rhs); 00289 // = operator 00290 CbcNewTree & operator=(const CbcNewTree & rhs); 00291 00292 virtual ~CbcNewTree(); 00293 00295 virtual CbcNewTree * clone() const; 00297 virtual void generateCpp( FILE * ) {} 00298 00301 00303 void setComparison(CbcCompareBase &compare); 00304 00306 virtual CbcNode * top() const; 00307 00309 virtual void push(CbcNode * x); 00310 00312 virtual void pop() ; 00314 virtual CbcNode * bestNode(double cutoff); 00315 00317 00319 00321 virtual bool empty() ; 00322 00324 inline int size() const { 00325 return nodes_.size(); 00326 } 00327 00329 inline CbcNode * operator [] (int i) const { 00330 return nodes_[i]; 00331 } 00332 00334 inline CbcNode * nodePointer (int i) const { 00335 return nodes_[i]; 00336 } 00337 00339 00342 00351 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); 00352 00354 CbcNode * bestAlternate(); 00355 00357 virtual void endSearch() {} 00359 protected: 00360 00361 00362 }; 00363 #endif 00364 #else 00365 /* CBC_DUBIOUS_HEAP is defined 00366 00367 See note at top of file. This code is highly suspect. 00368 -- lh, 100921 -- 00369 */ 00370 class CbcTree { 00371 00372 public: 00373 00374 // Default Constructor 00375 CbcTree (); 00376 00377 // Copy constructor 00378 CbcTree ( const CbcTree & rhs); 00379 // = operator 00380 CbcTree & operator=(const CbcTree & rhs); 00381 00382 virtual ~CbcTree(); 00383 00385 virtual CbcTree * clone() const; 00387 virtual void generateCpp( FILE * fp) {} 00388 00391 00393 void setComparison(CbcCompareBase &compare); 00394 00396 virtual CbcNode * top() const; 00397 00399 virtual void push(CbcNode * x); 00400 00402 virtual void pop() ; 00404 virtual CbcNode * bestNode(double cutoff); 00405 00407 00409 00411 //virtual bool empty() ; 00412 00414 inline int size() const { 00415 return nodes_.size(); 00416 } 00417 00419 inline CbcNode * operator [] (int i) const { 00420 return nodes_[i]; 00421 } 00422 00424 inline CbcNode * nodePointer (int i) const { 00425 return nodes_[i]; 00426 } 00427 00428 virtual bool empty(); 00429 //inline int size() const { return size_; } 00430 void realpop(); 00432 void fixTop(); 00433 void realpush(CbcNode * node); 00435 00438 00447 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective); 00448 00450 CbcNode * bestAlternate(); 00451 00453 virtual void endSearch() {} 00455 inline void resetNodeNumbers() { 00456 maximumNodeNumber_ = 0; 00457 } 00458 00460 inline int maximumNodeNumber() const { return maximumNodeNumber_; } 00462 protected: 00463 std::vector <CbcNode *> nodes_; 00464 CbcCompare comparison_; 00465 00466 int maximumNodeNumber_; 00467 00468 00469 }; 00470 #endif 00471 #endif 00472