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 #include "CbcCompare.hpp"
00014
00028
00029 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
00030
00031 #endif
00032 #ifndef CBC_DUBIOUS_HEAP
00033
00052 class CbcTree {
00053
00054 public:
00057
00058 CbcTree ();
00059
00061 CbcTree (const CbcTree &rhs);
00062
00064 CbcTree & operator=(const CbcTree &rhs);
00065
00067 virtual ~CbcTree();
00068
00070 virtual CbcTree * clone() const;
00071
00073 virtual void generateCpp(FILE *) {}
00075
00078
00079 void setComparison(CbcCompareBase &compare);
00080
00082 virtual CbcNode * top() const;
00083
00085 virtual void push(CbcNode *x);
00086
00088 virtual void pop() ;
00089
00096 virtual CbcNode * bestNode(double cutoff);
00097
00099 virtual void rebuild() ;
00101
00104
00105 virtual bool empty() ;
00106
00108 virtual int size() const { return static_cast<int>(nodes_.size()); }
00109
00111 inline CbcNode * operator [] (int i) const { return nodes_[i]; }
00112
00114 inline CbcNode * nodePointer (int i) const { return nodes_[i]; }
00116
00125 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00126
00128 CbcNode * bestAlternate();
00129
00131 virtual void endSearch() {}
00132
00134 virtual double getBestPossibleObjective();
00135
00137 inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
00138
00140 inline int maximumNodeNumber() const { return maximumNodeNumber_; }
00141
00143 inline void setNumberBranching(int value) { numberBranching_ = value; }
00144
00146 inline int getNumberBranching() const { return numberBranching_; }
00147
00149 inline void setMaximumBranching(int value) { maximumBranching_ = value; }
00150
00152 inline int getMaximumBranching() const { return maximumBranching_; }
00153
00155 inline unsigned int * branched() const { return branched_; }
00156
00158 inline int * newBounds() const { return newBound_; }
00159
00161 void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
00162 const double * currentLower,
00163 const double * currentUpper);
00165 void increaseSpace();
00167
00168 # if CBC_DEBUG_HEAP > 0
00169
00172 void validateHeap() ;
00174 # endif
00175
00176 protected:
00178 std::vector <CbcNode *> nodes_;
00180 CbcCompare comparison_;
00182 int maximumNodeNumber_;
00184 int numberBranching_;
00186 int maximumBranching_;
00191 unsigned int * branched_;
00193 int * newBound_;
00194 };
00195
00196 #ifdef JJF_ZERO // not used
00197
00201 class CbcTreeArray : public CbcTree {
00202
00203 public:
00204
00205
00206 CbcTreeArray ();
00207
00208
00209 CbcTreeArray ( const CbcTreeArray & rhs);
00210
00211 CbcTreeArray & operator=(const CbcTreeArray & rhs);
00212
00213 virtual ~CbcTreeArray();
00214
00216 virtual CbcTree * clone() const;
00218 virtual void generateCpp( FILE * ) {}
00219
00222
00224 void setComparison(CbcCompareBase &compare);
00225
00227 virtual void push(CbcNode * x);
00228
00230 virtual CbcNode * bestNode(double cutoff);
00231
00233
00235
00237 virtual bool empty() ;
00238
00240
00243
00252 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00254 virtual double getBestPossibleObjective();
00256 protected:
00259 CbcNode * lastNode_;
00261 CbcNode * lastNodePopped_;
00263 int switches_;
00264
00265 };
00266
00268 #include "CoinSearchTree.hpp"
00275 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
00276
00277 public:
00278
00279
00280 CbcNewTree ();
00281
00282
00283 CbcNewTree ( const CbcNewTree & rhs);
00284
00285 CbcNewTree & operator=(const CbcNewTree & rhs);
00286
00287 virtual ~CbcNewTree();
00288
00290 virtual CbcNewTree * clone() const;
00292 virtual void generateCpp( FILE * ) {}
00293
00296
00298 void setComparison(CbcCompareBase &compare);
00299
00301 virtual CbcNode * top() const;
00302
00304 virtual void push(CbcNode * x);
00305
00307 virtual void pop() ;
00309 virtual CbcNode * bestNode(double cutoff);
00310
00312
00314
00316 virtual bool empty() ;
00317
00319 inline int size() const {
00320 return nodes_.size();
00321 }
00322
00324 inline CbcNode * operator [] (int i) const {
00325 return nodes_[i];
00326 }
00327
00329 inline CbcNode * nodePointer (int i) const {
00330 return nodes_[i];
00331 }
00332
00334
00337
00346 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00347
00349 CbcNode * bestAlternate();
00350
00352 virtual void endSearch() {}
00354 protected:
00355
00356
00357 };
00358 #endif
00359 #else
00360
00361
00362
00363
00364
00365 class CbcTree {
00366
00367 public:
00368
00369
00370 CbcTree ();
00371
00372
00373 CbcTree ( const CbcTree & rhs);
00374
00375 CbcTree & operator=(const CbcTree & rhs);
00376
00377 virtual ~CbcTree();
00378
00380 virtual CbcTree * clone() const;
00382 virtual void generateCpp( FILE * fp) {}
00383
00386
00388 void setComparison(CbcCompareBase &compare);
00389
00391 virtual CbcNode * top() const;
00392
00394 virtual void push(CbcNode * x);
00395
00397 virtual void pop() ;
00399 virtual CbcNode * bestNode(double cutoff);
00400
00402
00404
00406
00407
00409 inline int size() const {
00410 return nodes_.size();
00411 }
00412
00414 inline CbcNode * operator [] (int i) const {
00415 return nodes_[i];
00416 }
00417
00419 inline CbcNode * nodePointer (int i) const {
00420 return nodes_[i];
00421 }
00422
00423 virtual bool empty();
00424
00425 void realpop();
00427 void fixTop();
00428 void realpush(CbcNode * node);
00430
00433
00442 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00443
00445 CbcNode * bestAlternate();
00446
00448 virtual void endSearch() {}
00450 inline void resetNodeNumbers() {
00451 maximumNodeNumber_ = 0;
00452 }
00454 protected:
00455 std::vector <CbcNode *> nodes_;
00456 CbcCompare comparison_;
00457
00458 int maximumNodeNumber_;
00459
00460
00461 };
00462 #endif
00463 #endif
00464