00001
00002
00003
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
00019
00020 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
00021
00022 #endif
00023 #ifndef CBC_DUBIOUS_HEAP
00024 class CbcTree {
00025
00026 public:
00027
00028
00029 CbcTree ();
00030
00031
00032 CbcTree ( const CbcTree & rhs);
00033
00034 CbcTree & operator=(const CbcTree & rhs);
00035
00036 virtual ~CbcTree();
00037
00039 virtual CbcTree * clone() const;
00041 virtual void generateCpp( FILE * ) {}
00042
00045
00047 void setComparison(CbcCompareBase &compare);
00048
00050 virtual CbcNode * top() const;
00051
00053 virtual void push(CbcNode * x);
00054
00056 virtual void pop() ;
00058 virtual CbcNode * bestNode(double cutoff);
00059
00061
00063
00065 virtual bool empty() ;
00066
00068 virtual int size() const
00069 {return nodes_.size();}
00071 inline CbcNode * operator [] (int i) const
00072 { return nodes_[i];}
00073
00075 inline CbcNode * nodePointer (int i) const
00076 { return nodes_[i];}
00077
00078
00080
00083
00092 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00093
00095 CbcNode * bestAlternate();
00096
00098 virtual void endSearch() {}
00099
00101 virtual double getBestPossibleObjective();
00103 inline void resetNodeNumbers()
00104 { maximumNodeNumber_=0;}
00106 inline void setNumberBranching(int value)
00107 { numberBranching_=value;}
00109 inline int getNumberBranching() const
00110 { return numberBranching_;}
00112 inline void setMaximumBranching(int value)
00113 { maximumBranching_=value;}
00115 inline int getMaximumBranching() const
00116 { return maximumBranching_;}
00118 inline unsigned int * branched() const
00119 { return branched_;}
00121 inline int * newBounds() const
00122 { return newBound_;}
00124 void addBranchingInformation(const CbcModel * model,const CbcNodeInfo * nodeInfo,
00125 const double * currentLower,
00126 const double * currentUpper);
00128 void increaseSpace();
00130 protected:
00131 std::vector <CbcNode *> nodes_;
00132 CbcCompare comparison_;
00133
00134 int maximumNodeNumber_;
00136 int numberBranching_;
00138 int maximumBranching_;
00143 unsigned int * branched_;
00145 int * newBound_;
00146 };
00153 class CbcTreeArray : public CbcTree {
00154
00155 public:
00156
00157
00158 CbcTreeArray ();
00159
00160
00161 CbcTreeArray ( const CbcTreeArray & rhs);
00162
00163 CbcTreeArray & operator=(const CbcTreeArray & rhs);
00164
00165 virtual ~CbcTreeArray();
00166
00168 virtual CbcTree * clone() const;
00170 virtual void generateCpp( FILE * ) {}
00171
00174
00176 void setComparison(CbcCompareBase &compare);
00177
00179 virtual void push(CbcNode * x);
00180
00182 virtual CbcNode * bestNode(double cutoff);
00183
00185
00187
00189 virtual bool empty() ;
00190
00192
00195
00204 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00206 virtual double getBestPossibleObjective();
00208 protected:
00211 CbcNode * lastNode_;
00213 CbcNode * lastNodePopped_;
00215 int switches_;
00216
00217 };
00218
00220 #include "CoinSearchTree.hpp"
00227 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
00228
00229 public:
00230
00231
00232 CbcNewTree ();
00233
00234
00235 CbcNewTree ( const CbcNewTree & rhs);
00236
00237 CbcNewTree & operator=(const CbcNewTree & rhs);
00238
00239 virtual ~CbcNewTree();
00240
00242 virtual CbcNewTree * clone() const;
00244 virtual void generateCpp( FILE * ) {}
00245
00248
00250 void setComparison(CbcCompareBase &compare);
00251
00253 virtual CbcNode * top() const;
00254
00256 virtual void push(CbcNode * x);
00257
00259 virtual void pop() ;
00261 virtual CbcNode * bestNode(double cutoff);
00262
00264
00266
00268 virtual bool empty() ;
00269
00271 inline int size() const
00272 { return nodes_.size();}
00273
00275 inline CbcNode * operator [] (int i) const
00276 { return nodes_[i];}
00277
00279 inline CbcNode * nodePointer (int i) const
00280 { return nodes_[i];}
00281
00283
00286
00295 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00296
00298 CbcNode * bestAlternate();
00299
00301 virtual void endSearch() {}
00303 protected:
00304
00305
00306 };
00307 #else
00308 class CbcTree {
00309
00310 public:
00311
00312
00313 CbcTree ();
00314
00315
00316 CbcTree ( const CbcTree & rhs);
00317
00318 CbcTree & operator=(const CbcTree & rhs);
00319
00320 virtual ~CbcTree();
00321
00323 virtual CbcTree * clone() const;
00325 virtual void generateCpp( FILE * fp) {}
00326
00329
00331 void setComparison(CbcCompareBase &compare);
00332
00334 virtual CbcNode * top() const;
00335
00337 virtual void push(CbcNode * x);
00338
00340 virtual void pop() ;
00342 virtual CbcNode * bestNode(double cutoff);
00343
00345
00347
00349
00350
00352 inline int size() const
00353 { return nodes_.size();}
00354
00356 inline CbcNode * operator [] (int i) const
00357 { return nodes_[i];}
00358
00360 inline CbcNode * nodePointer (int i) const
00361 { return nodes_[i];}
00362
00363 virtual bool empty();
00364
00365 void realpop();
00367 void fixTop();
00368 void realpush(CbcNode * node);
00370
00373
00382 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00383
00385 CbcNode * bestAlternate();
00386
00388 virtual void endSearch() {}
00390 inline void resetNodeNumbers()
00391 { maximumNodeNumber_=0;}
00393 protected:
00394 std::vector <CbcNode *> nodes_;
00395 CbcCompare comparison_;
00396
00397 int maximumNodeNumber_;
00398
00399
00400 };
00401 #endif
00402 #endif
00403