# CbcTree.hpp

Go to the documentation of this file.

    00001 /* $Id: CbcTree.hpp 1813 2012-11-22 19:00:22Z forrest $ */
    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