CbcTree.hpp
Go to the documentation of this file.00001
00002
00003
00004
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
00030 #if defined(_MSC_VER) || defined(__MNO_CYGWIN)
00031
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 inline double lastObjective() const {
00167 return lastObjective_;
00168 }
00170 inline int lastDepth() const {
00171 return lastDepth_;
00172 }
00174 inline int lastUnsatisfied() const {
00175 return lastUnsatisfied_;
00176 }
00178 void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
00179 const double * currentLower,
00180 const double * currentUpper);
00182 void increaseSpace();
00184
00185 # if CBC_DEBUG_HEAP > 0
00186
00189 void validateHeap() ;
00191 # endif
00192
00193 protected:
00195 std::vector <CbcNode *> nodes_;
00197 CbcCompare comparison_;
00199 int maximumNodeNumber_;
00201 int numberBranching_;
00203 int maximumBranching_;
00205 double lastObjective_;
00207 int lastDepth_;
00209 int lastUnsatisfied_;
00214 unsigned int * branched_;
00216 int * newBound_;
00217 };
00218
00219 #ifdef JJF_ZERO // not used
00220
00224 class CbcTreeArray : public CbcTree {
00225
00226 public:
00227
00228
00229 CbcTreeArray ();
00230
00231
00232 CbcTreeArray ( const CbcTreeArray & rhs);
00233
00234 CbcTreeArray & operator=(const CbcTreeArray & rhs);
00235
00236 virtual ~CbcTreeArray();
00237
00239 virtual CbcTree * clone() const;
00241 virtual void generateCpp( FILE * ) {}
00242
00245
00247 void setComparison(CbcCompareBase &compare);
00248
00250 virtual void push(CbcNode * x);
00251
00253 virtual CbcNode * bestNode(double cutoff);
00254
00256
00258
00260 virtual bool empty() ;
00261
00263
00266
00275 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00277 virtual double getBestPossibleObjective();
00279 protected:
00282 CbcNode * lastNode_;
00284 CbcNode * lastNodePopped_;
00286 int switches_;
00287
00288 };
00289
00291 #include "CoinSearchTree.hpp"
00298 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
00299
00300 public:
00301
00302
00303 CbcNewTree ();
00304
00305
00306 CbcNewTree ( const CbcNewTree & rhs);
00307
00308 CbcNewTree & operator=(const CbcNewTree & rhs);
00309
00310 virtual ~CbcNewTree();
00311
00313 virtual CbcNewTree * clone() const;
00315 virtual void generateCpp( FILE * ) {}
00316
00319
00321 void setComparison(CbcCompareBase &compare);
00322
00324 virtual CbcNode * top() const;
00325
00327 virtual void push(CbcNode * x);
00328
00330 virtual void pop() ;
00332 virtual CbcNode * bestNode(double cutoff);
00333
00335
00337
00339 virtual bool empty() ;
00340
00342 inline int size() const {
00343 return nodes_.size();
00344 }
00345
00347 inline CbcNode * operator [] (int i) const {
00348 return nodes_[i];
00349 }
00350
00352 inline CbcNode * nodePointer (int i) const {
00353 return nodes_[i];
00354 }
00355
00357
00360
00369 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00370
00372 CbcNode * bestAlternate();
00373
00375 virtual void endSearch() {}
00377 protected:
00378
00379
00380 };
00381 #endif
00382 #else
00383
00384
00385
00386
00387
00388 class CbcTree {
00389
00390 public:
00391
00392
00393 CbcTree ();
00394
00395
00396 CbcTree ( const CbcTree & rhs);
00397
00398 CbcTree & operator=(const CbcTree & rhs);
00399
00400 virtual ~CbcTree();
00401
00403 virtual CbcTree * clone() const;
00405 virtual void generateCpp( FILE * fp) {}
00406
00409
00411 void setComparison(CbcCompareBase &compare);
00412
00414 virtual CbcNode * top() const;
00415
00417 virtual void push(CbcNode * x);
00418
00420 virtual void pop() ;
00422 virtual CbcNode * bestNode(double cutoff);
00423
00425
00427
00429
00430
00432 inline int size() const {
00433 return nodes_.size();
00434 }
00435
00437 inline CbcNode * operator [] (int i) const {
00438 return nodes_[i];
00439 }
00440
00442 inline CbcNode * nodePointer (int i) const {
00443 return nodes_[i];
00444 }
00445
00446 virtual bool empty();
00447
00448 void realpop();
00450 void fixTop();
00451 void realpush(CbcNode * node);
00453
00456
00465 void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00466
00468 CbcNode * bestAlternate();
00469
00471 virtual void endSearch() {}
00473 inline void resetNodeNumbers() {
00474 maximumNodeNumber_ = 0;
00475 }
00476
00478 inline int maximumNodeNumber() const { return maximumNodeNumber_; }
00480 protected:
00481 std::vector <CbcNode *> nodes_;
00482 CbcCompare comparison_;
00483
00484 int maximumNodeNumber_;
00485
00486
00487 };
00488 #endif
00489 #endif
00490