# CbcTree.hpp

Go to the documentation of this file.

    00001 /* $Id: CbcTree.hpp 1675 2011-06-19 17:23:14Z stefan $ */
    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 #ifndef 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]; }
    00117
    00126     virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    00127
    00129     CbcNode * bestAlternate();
    00130
    00132     virtual void endSearch() {}
    00133
    00135     virtual double getBestPossibleObjective();
    00136
    00138     inline void resetNodeNumbers() { maximumNodeNumber_ = 0; }
    00139
    00141     inline int maximumNodeNumber() const { return maximumNodeNumber_; }
    00142
    00144     inline void setNumberBranching(int value) { numberBranching_ = value; }
    00145
    00147     inline int getNumberBranching() const { return numberBranching_; }
    00148
    00150     inline void setMaximumBranching(int value) { maximumBranching_ = value; }
    00151
    00153     inline int getMaximumBranching() const { return maximumBranching_; }
    00154
    00156     inline unsigned int * branched() const { return branched_; }
    00157
    00159     inline int * newBounds() const { return newBound_; }
    00160
    00162     void addBranchingInformation(const CbcModel * model, const CbcNodeInfo * nodeInfo,
    00163                                  const double * currentLower,
    00164                                  const double * currentUpper);
    00166     void increaseSpace();
    00168
    00169 # if CBC_DEBUG_HEAP > 0
    00170
    00173     void validateHeap() ;
    00175 # endif
    00176
    00177 protected:
    00179     std::vector <CbcNode *> nodes_;
    00181     CbcCompare comparison_;
    00183     int maximumNodeNumber_;
    00185     int numberBranching_;
    00187     int maximumBranching_;
    00192     unsigned int * branched_;
    00194     int * newBound_;
    00195 };
    00196
    00197 #ifdef JJF_ZERO // not used
    00198
    00202 class CbcTreeArray : public CbcTree {
    00203
    00204 public:
    00205
    00206     // Default Constructor
    00207     CbcTreeArray ();
    00208
    00209     // Copy constructor
    00210     CbcTreeArray ( const CbcTreeArray & rhs);
    00211     // = operator
    00212     CbcTreeArray & operator=(const CbcTreeArray & rhs);
    00213
    00214     virtual ~CbcTreeArray();
    00215
    00217     virtual CbcTree * clone() const;
    00219     virtual void generateCpp( FILE * ) {}
    00220
    00223
    00225     void setComparison(CbcCompareBase  &compare);
    00226
    00228     virtual void push(CbcNode * x);
    00229
    00231     virtual CbcNode * bestNode(double cutoff);
    00232
    00234
    00236
    00238     virtual bool empty() ;
    00239
    00241
    00244
    00253     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    00255     virtual double getBestPossibleObjective();
    00257 protected:
    00260     CbcNode * lastNode_;
    00262     CbcNode * lastNodePopped_;
    00264     int switches_;
    00265
    00266 };
    00267
    00269 #include "CoinSearchTree.hpp"
    00276 class CbcNewTree : public CbcTree, public CoinSearchTreeManager {
    00277
    00278 public:
    00279
    00280     // Default Constructor
    00281     CbcNewTree ();
    00282
    00283     // Copy constructor
    00284     CbcNewTree ( const CbcNewTree & rhs);
    00285     // = operator
    00286     CbcNewTree & operator=(const CbcNewTree & rhs);
    00287
    00288     virtual ~CbcNewTree();
    00289
    00291     virtual CbcNewTree * clone() const;
    00293     virtual void generateCpp( FILE * ) {}
    00294
    00297
    00299     void setComparison(CbcCompareBase  &compare);
    00300
    00302     virtual CbcNode * top() const;
    00303
    00305     virtual void push(CbcNode * x);
    00306
    00308     virtual void pop() ;
    00310     virtual CbcNode * bestNode(double cutoff);
    00311
    00313
    00315
    00317     virtual bool empty() ;
    00318
    00320     inline int size() const {
    00321         return nodes_.size();
    00322     }
    00323
    00325     inline CbcNode * operator [] (int i) const {
    00326         return nodes_[i];
    00327     }
    00328
    00330     inline CbcNode * nodePointer (int i) const {
    00331         return nodes_[i];
    00332     }
    00333
    00335
    00338
    00347     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    00348
    00350     CbcNode * bestAlternate();
    00351
    00353     virtual void endSearch() {}
    00355 protected:
    00356
    00357
    00358 };
    00359 #endif
    00360 #else
    00361 /* CBC_DUBIOUS_HEAP is defined
    00362
    00363   See note at top of file. This code is highly suspect.
    00364   -- lh, 100921 --
    00365 */
    00366 class CbcTree {
    00367
    00368 public:
    00369
    00370     // Default Constructor
    00371     CbcTree ();
    00372
    00373     // Copy constructor
    00374     CbcTree ( const CbcTree & rhs);
    00375     // = operator
    00376     CbcTree & operator=(const CbcTree & rhs);
    00377
    00378     virtual ~CbcTree();
    00379
    00381     virtual CbcTree * clone() const;
    00383     virtual void generateCpp( FILE * fp) {}
    00384
    00387
    00389     void setComparison(CbcCompareBase  &compare);
    00390
    00392     virtual CbcNode * top() const;
    00393
    00395     virtual void push(CbcNode * x);
    00396
    00398     virtual void pop() ;
    00400     virtual CbcNode * bestNode(double cutoff);
    00401
    00403
    00405
    00407     //virtual bool empty() ;
    00408
    00410     inline int size() const {
    00411         return nodes_.size();
    00412     }
    00413
    00415     inline CbcNode * operator [] (int i) const {
    00416         return nodes_[i];
    00417     }
    00418
    00420     inline CbcNode * nodePointer (int i) const {
    00421         return nodes_[i];
    00422     }
    00423
    00424     virtual bool empty();
    00425     //inline int size() const { return size_; }
    00426     void realpop();
    00428     void fixTop();
    00429     void realpush(CbcNode * node);
    00431
    00434
    00443     void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
    00444
    00446     CbcNode * bestAlternate();
    00447
    00449     virtual void endSearch() {}
    00451     inline void resetNodeNumbers() {
    00452         maximumNodeNumber_ = 0;
    00453     }
    00455 protected:
    00456     std::vector <CbcNode *> nodes_;
    00457     CbcCompare comparison_;
    00458
    00459     int maximumNodeNumber_;
    00460
    00461
    00462 };
    00463 #endif
    00464 #endif
    00465

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines