00001
00002
00003 #ifndef CbcTree_H
00004 #define CbcTree_H
00005
00006 #include <vector>
00007 #include <algorithm>
00008 #include <cmath>
00009
00010 #include "CoinFinite.hpp"
00011 #include "CoinHelperFunctions.hpp"
00012
00018
00019 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
00020
00021 #endif
00022 #ifndef CBC_DUBIOUS_HEAP
00023 class CbcTree {
00024
00025 public:
00026
00027
00028 CbcTree ();
00029
00030
00031 CbcTree ( const CbcTree & rhs);
00032
00033 CbcTree & operator=(const CbcTree & rhs);
00034
00035 virtual ~CbcTree();
00036
00038 virtual CbcTree * clone() const;
00040 virtual void generateCpp( FILE * fp) {}
00041
00044
00046 void setComparison(CbcCompareBase &compare);
00047
00049 virtual CbcNode * top() const;
00050
00052 virtual void push(CbcNode * x);
00053
00055 virtual void pop() ;
00057 virtual CbcNode * bestNode(double cutoff);
00058
00060
00062
00064 virtual bool empty() ;
00065
00067 virtual int size() const
00068 {return nodes_.size();}
00070 inline CbcNode * operator [] (int i) const
00071 { return nodes_[i];}
00072
00074 inline CbcNode * nodePointer (int i) const
00075 { return nodes_[i];}
00076
00077
00079
00082
00091 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00092
00094 CbcNode * bestAlternate();
00095
00097 virtual void endSearch() {}
00098
00100 virtual double getBestPossibleObjective();
00102 inline void resetNodeNumbers()
00103 { maximumNodeNumber_=0;}
00105 inline void setNumberBranching(int value)
00106 { numberBranching_=value;}
00108 inline int getNumberBranching() const
00109 { return numberBranching_;}
00111 inline void setMaximumBranching(int value)
00112 { maximumBranching_=value;}
00114 inline int getMaximumBranching() const
00115 { return maximumBranching_;}
00117 inline unsigned int * branched() const
00118 { return branched_;}
00120 inline int * newBounds() const
00121 { return newBound_;}
00123 void addBranchingInformation(const CbcModel * model,const CbcNodeInfo * nodeInfo,
00124 const double * currentLower,
00125 const double * currentUpper);
00127 void increaseSpace();
00129 protected:
00130 std::vector <CbcNode *> nodes_;
00131 CbcCompare comparison_;
00132
00133 int maximumNodeNumber_;
00135 int numberBranching_;
00137 int maximumBranching_;
00142 unsigned int * branched_;
00144 int * newBound_;
00145 };
00152 class CbcTreeArray : public CbcTree {
00153
00154 public:
00155
00156
00157 CbcTreeArray ();
00158
00159
00160 CbcTreeArray ( const CbcTreeArray & rhs);
00161
00162 CbcTreeArray & operator=(const CbcTreeArray & rhs);
00163
00164 virtual ~CbcTreeArray();
00165
00167 virtual CbcTree * clone() const;
00169 virtual void generateCpp( FILE * fp) {}
00170
00173
00175 void setComparison(CbcCompareBase &compare);
00176
00178 virtual void push(CbcNode * x);
00179
00181 virtual CbcNode * bestNode(double cutoff);
00182
00184
00186
00188 virtual bool empty() ;
00189
00191
00194
00203 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00205 virtual double getBestPossibleObjective();
00207 protected:
00210 CbcNode * lastNode_;
00212 CbcNode * lastNodePopped_;
00214 int switches_;
00215
00216 };
00217
00219 #include "CoinSearchTree.hpp"
00226 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
00227
00228 public:
00229
00230
00231 CbcNewTree ();
00232
00233
00234 CbcNewTree ( const CbcNewTree & rhs);
00235
00236 CbcNewTree & operator=(const CbcNewTree & rhs);
00237
00238 virtual ~CbcNewTree();
00239
00241 virtual CbcNewTree * clone() const;
00243 virtual void generateCpp( FILE * fp) {}
00244
00247
00249 void setComparison(CbcCompareBase &compare);
00250
00252 virtual CbcNode * top() const;
00253
00255 virtual void push(CbcNode * x);
00256
00258 virtual void pop() ;
00260 virtual CbcNode * bestNode(double cutoff);
00261
00263
00265
00267 virtual bool empty() ;
00268
00270 inline int size() const
00271 { return nodes_.size();}
00272
00274 inline CbcNode * operator [] (int i) const
00275 { return nodes_[i];}
00276
00278 inline CbcNode * nodePointer (int i) const
00279 { return nodes_[i];}
00280
00282
00285
00294 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00295
00297 CbcNode * bestAlternate();
00298
00300 virtual void endSearch() {}
00302 protected:
00303
00304
00305 };
00306 #else
00307 class CbcTree {
00308
00309 public:
00310
00311
00312 CbcTree ();
00313
00314
00315 CbcTree ( const CbcTree & rhs);
00316
00317 CbcTree & operator=(const CbcTree & rhs);
00318
00319 virtual ~CbcTree();
00320
00322 virtual CbcTree * clone() const;
00324 virtual void generateCpp( FILE * fp) {}
00325
00328
00330 void setComparison(CbcCompareBase &compare);
00331
00333 virtual CbcNode * top() const;
00334
00336 virtual void push(CbcNode * x);
00337
00339 virtual void pop() ;
00341 virtual CbcNode * bestNode(double cutoff);
00342
00344
00346
00348
00349
00351 inline int size() const
00352 { return nodes_.size();}
00353
00355 inline CbcNode * operator [] (int i) const
00356 { return nodes_[i];}
00357
00359 inline CbcNode * nodePointer (int i) const
00360 { return nodes_[i];}
00361
00362 virtual bool empty();
00363
00364 void realpop();
00366 void fixTop();
00367 void realpush(CbcNode * node);
00369
00372
00381 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00382
00384 CbcNode * bestAlternate();
00385
00387 virtual void endSearch() {}
00389 inline void resetNodeNumbers()
00390 { maximumNodeNumber_=0;}
00392 protected:
00393 std::vector <CbcNode *> nodes_;
00394 CbcCompare comparison_;
00395
00396 int maximumNodeNumber_;
00397
00398
00399 };
00400 #endif
00401 #endif
00402