00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #ifndef BonDiver_H
00011 #define BonDiver_H
00012
00013 #include "CbcCompareBase.hpp"
00014 #include "CbcTree.hpp"
00015 #include "BonminConfig.h"
00016 #include "IpRegOptions.hpp"
00017 #include "IpOptionsList.hpp"
00018 #include "CbcCompareActual.hpp"
00019 #include "BonRegisteredOptions.hpp"
00020 #include <list>
00021 namespace Bonmin
00022 {
00025 class CbcDiver : public CbcTree
00026 {
00027 public:
00029 CbcDiver();
00030
00032 CbcDiver(const CbcDiver &rhs);
00033
00035 CbcDiver & operator=(const CbcDiver &rhs);
00036
00038 virtual ~CbcDiver();
00039
00041 virtual CbcTree * clone() const;
00042
00045
00046 virtual CbcNode * top() const;
00047
00049 virtual void push(CbcNode * x);
00051 virtual void pop();
00053 virtual CbcNode * bestNode(double cutoff);
00056
00057
00059 virtual bool empty();
00061 virtual int size()
00062 {
00063 return (nodes_.size() + (nextOnBranch_ != NULL) );
00064 }
00074 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00075
00077 virtual double getBestPossibleObjective();
00078
00079
00081 virtual void endSearch()
00082 {
00083 nextOnBranch_ = NULL;
00084 }
00085
00087 static void registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions);
00088
00090 void initialize(Ipopt::SmartPtr<Ipopt::OptionsList> options);
00091
00092 private:
00094 bool treeCleaning_;
00096 CbcNode * nextOnBranch_;
00099 bool stop_diving_on_cutoff_;
00100 };
00101
00102
00107 class CbcProbedDiver : public CbcTree
00108 {
00109 public:
00111 CbcProbedDiver();
00112
00114 CbcProbedDiver(const CbcProbedDiver &rhs);
00115
00117 CbcProbedDiver & operator=(const CbcProbedDiver &rhs);
00118
00120 virtual ~CbcProbedDiver();
00121
00123 virtual CbcTree * clone() const;
00124
00127
00128 virtual CbcNode * top() const;
00129
00131 virtual void push(CbcNode * x);
00133 virtual void pop();
00135 virtual CbcNode * bestNode(double cutoff);
00138
00139
00141 virtual bool empty();
00143 virtual int size()
00144 {
00145 return (nodes_.size() + (nextOnBranch_ != NULL) + (candidateChild_ != NULL) );
00146 }
00156 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00157
00159 virtual double getBestPossibleObjective();
00160
00161
00163 virtual void endSearch()
00164 {
00165 nextOnBranch_ = NULL;
00166 }
00167
00169 void initialize(Ipopt::SmartPtr<Ipopt::OptionsList> options);
00170
00171 private:
00173 bool treeCleaning_;
00175 CbcNode * nextOnBranch_;
00177 CbcNode * candidateChild_;
00180 bool stop_diving_on_cutoff_;
00181 };
00182
00183
00198 class CbcDfsDiver :public CbcTree
00199 {
00200 public:
00201 enum ComparisonModes{
00202 Enlarge,
00203 FindSolutions,
00204 CloseBound,
00205 LimitTreeSize};
00207 CbcDfsDiver();
00208
00210 CbcDfsDiver(const CbcDfsDiver &rhs);
00211
00213 CbcDfsDiver & operator=(const CbcDfsDiver &rhs);
00214
00216 virtual ~CbcDfsDiver();
00217
00219 virtual CbcTree * clone() const;
00220
00223
00224 virtual CbcNode * top() const;
00225
00227 virtual void push(CbcNode * x);
00229 virtual void pop();
00231 virtual CbcNode * bestNode(double cutoff);
00234
00235
00237 virtual bool empty();
00239 virtual int size()
00240 {
00241 return nodes_.size() + diveListSize_;
00242 }
00253 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00254
00256 virtual double getBestPossibleObjective();
00257
00258
00260 static void registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions);
00261
00263 void initialize(Ipopt::SmartPtr<Ipopt::OptionsList> options);
00264
00266 virtual void endSearch()
00267 {}
00268
00271 void setComparisonMode(ComparisonModes newMode);
00273 ComparisonModes getComparisonMode()
00274 {
00275 return mode_;
00276 }
00277 protected:
00280 int treeCleaning_;
00282 std::list<CbcNode *> dive_;
00284 int diveListSize_;
00286 int divingBoardDepth_;
00288 double cutoff_;
00290 int nBacktracks_;
00294 int maxDepthBFS_;
00296 int maxDiveBacktracks_;
00298 int maxDiveDepth_;
00300 ComparisonModes mode_;
00302 private:
00304 void pushDiveOntoHeap(double cutoff);
00305
00306 };
00307
00308 class DiverCompare : public CbcCompareBase
00309 {
00310 public:
00311
00312 DiverCompare ():
00313 CbcCompareBase(),
00314 diver_(NULL),
00315 numberSolToStopDive_(5),
00316 numberNodesToLimitTreeSize_(1000000),
00317 comparisonDive_(NULL),
00318 comparisonBound_(NULL)
00319 {}
00320
00321
00322 virtual ~DiverCompare()
00323 {
00324 delete comparisonDive_;
00325 delete comparisonBound_;
00326 }
00327
00328
00329 DiverCompare ( const DiverCompare & rhs):
00330 CbcCompareBase(rhs),
00331 diver_(rhs.diver_),
00332 numberSolToStopDive_(rhs.numberSolToStopDive_),
00333 numberNodesToLimitTreeSize_(rhs.numberNodesToLimitTreeSize_),
00334 comparisonDive_(rhs.comparisonDive_->clone()),
00335 comparisonBound_(rhs.comparisonBound_->clone())
00336 {}
00337
00338
00339 DiverCompare & operator=( const DiverCompare& rhs)
00340 {
00341 if (this != &rhs) {
00342 CbcCompareBase::operator=(rhs);
00343 diver_ = rhs.diver_;
00344 numberSolToStopDive_ = rhs.numberSolToStopDive_;
00345 numberNodesToLimitTreeSize_ = rhs.numberNodesToLimitTreeSize_;
00346 delete comparisonDive_;
00347 delete comparisonBound_;
00348 comparisonDive_ = NULL;
00349 comparisonBound_ = NULL;
00350 if (rhs.comparisonDive_) comparisonDive_ = rhs.comparisonDive_->clone();
00351 if (rhs.comparisonBound_) comparisonBound_ = rhs.comparisonBound_->clone();
00352 }
00353 return *this;
00354 }
00355
00357 virtual CbcCompareBase * clone() const
00358 {
00359 return new DiverCompare(*this);
00360 }
00361
00363 virtual bool test (CbcNode * x, CbcNode * y);
00364
00366 virtual void newSolution(CbcModel * model);
00367
00369 virtual void newSolution(CbcModel * model,
00370 double objectiveAtContinuous,
00371 int numberInfeasibilitiesAtContinuous);
00372
00375 virtual bool every1000Nodes(CbcModel * model,int numberNodes);
00376
00378 void setDiver(CbcDfsDiver * diver)
00379 {
00380 diver_ = diver;
00381 }
00382
00384 void setNumberSolToStopDive(int val)
00385 {
00386 numberSolToStopDive_ = val;
00387 }
00388
00390 void setNumberNodesToLimitTreeSize(int val)
00391 {
00392 numberNodesToLimitTreeSize_ = val;
00393 }
00394
00396 void setComparisonDive(const CbcCompareBase & val)
00397 {
00398 comparisonDive_ = val.clone();
00399 }
00401 void setComparisonBound(const CbcCompareBase & val)
00402 {
00403 comparisonBound_ = val.clone();
00404 }
00405 private:
00407 CbcDfsDiver * diver_;
00409 int numberSolToStopDive_;
00411 int numberNodesToLimitTreeSize_;
00413 CbcCompareBase * comparisonDive_;
00415 CbcCompareBase * comparisonBound_;
00417 CbcCompareDepth comparisonDepth_;
00418 };
00419
00420 }
00421
00422 #endif
00423