Cbc  trunk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
CbcTree.hpp
Go to the documentation of this file.
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines