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 {
00023 class BabSetupBase;
00026 class CbcDiver : public CbcTree
00027 {
00028 public:
00030 CbcDiver();
00031
00033 CbcDiver(const CbcDiver &rhs);
00034
00036 CbcDiver & operator=(const CbcDiver &rhs);
00037
00039 virtual ~CbcDiver();
00040
00042 virtual CbcTree * clone() const;
00043
00046
00047 virtual CbcNode * top() const;
00048
00050 virtual void push(CbcNode * x);
00052 virtual void pop();
00054 virtual CbcNode * bestNode(double cutoff);
00057
00058
00060 virtual bool empty();
00062 virtual int size()
00063 {
00064 return ((int) nodes_.size() + (nextOnBranch_ != NULL) );
00065 }
00075 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00076
00078 virtual double getBestPossibleObjective();
00079
00080
00082 virtual void endSearch()
00083 {
00084 nextOnBranch_ = NULL;
00085 }
00086
00088 static void registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions);
00089
00091 void initialize(BabSetupBase &b);
00092
00093 private:
00095 bool treeCleaning_;
00097 CbcNode * nextOnBranch_;
00100 bool stop_diving_on_cutoff_;
00101 };
00102
00103
00108 class CbcProbedDiver : public CbcTree
00109 {
00110 public:
00112 CbcProbedDiver();
00113
00115 CbcProbedDiver(const CbcProbedDiver &rhs);
00116
00118 CbcProbedDiver & operator=(const CbcProbedDiver &rhs);
00119
00121 virtual ~CbcProbedDiver();
00122
00124 virtual CbcTree * clone() const;
00125
00128
00129 virtual CbcNode * top() const;
00130
00132 virtual void push(CbcNode * x);
00134 virtual void pop();
00136 virtual CbcNode * bestNode(double cutoff);
00139
00140
00142 virtual bool empty();
00144 virtual int size()
00145 {
00146 return ((int) nodes_.size() + (nextOnBranch_ != NULL) + (candidateChild_ != NULL) );
00147 }
00157 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00158
00160 virtual double getBestPossibleObjective();
00161
00162
00164 virtual void endSearch()
00165 {
00166 nextOnBranch_ = NULL;
00167 }
00168
00170 void initialize(BabSetupBase &b);
00171
00172 private:
00174 bool treeCleaning_;
00176 CbcNode * nextOnBranch_;
00178 CbcNode * candidateChild_;
00181 bool stop_diving_on_cutoff_;
00182 };
00183
00184
00199 class CbcDfsDiver :public CbcTree
00200 {
00201 public:
00202 enum ComparisonModes{
00203 Enlarge,
00204 FindSolutions,
00205 CloseBound,
00206 LimitTreeSize};
00208 CbcDfsDiver();
00209
00211 CbcDfsDiver(const CbcDfsDiver &rhs);
00212
00214 CbcDfsDiver & operator=(const CbcDfsDiver &rhs);
00215
00217 virtual ~CbcDfsDiver();
00218
00220 virtual CbcTree * clone() const;
00221
00224
00225 virtual CbcNode * top() const;
00226
00228 virtual void push(CbcNode * x);
00230 virtual void pop();
00232 virtual CbcNode * bestNode(double cutoff);
00235
00236
00238 virtual bool empty();
00240 virtual int size()
00241 {
00242 return (int) nodes_.size() + diveListSize_;
00243 }
00254 virtual void cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective);
00255
00257 virtual double getBestPossibleObjective();
00258
00259
00261 static void registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions);
00262
00264 void initialize(BabSetupBase &b);
00265
00267 virtual void endSearch()
00268 {}
00269
00272 void setComparisonMode(ComparisonModes newMode);
00274 ComparisonModes getComparisonMode()
00275 {
00276 return mode_;
00277 }
00278 protected:
00281 int treeCleaning_;
00283 std::list<CbcNode *> dive_;
00285 int diveListSize_;
00287 int divingBoardDepth_;
00289 double cutoff_;
00291 int nBacktracks_;
00295 int maxDepthBFS_;
00297 int maxDiveBacktracks_;
00299 int maxDiveDepth_;
00301 ComparisonModes mode_;
00303 private:
00305 void pushDiveOntoHeap(double cutoff);
00306
00307 };
00308
00309 class DiverCompare : public CbcCompareBase
00310 {
00311 public:
00312
00313 DiverCompare ():
00314 CbcCompareBase(),
00315 diver_(NULL),
00316 numberSolToStopDive_(5),
00317 numberNodesToLimitTreeSize_(1000000),
00318 comparisonDive_(NULL),
00319 comparisonBound_(NULL)
00320 {}
00321
00322
00323 virtual ~DiverCompare()
00324 {
00325 delete comparisonDive_;
00326 delete comparisonBound_;
00327 }
00328
00329
00330 DiverCompare ( const DiverCompare & rhs):
00331 CbcCompareBase(rhs),
00332 diver_(rhs.diver_),
00333 numberSolToStopDive_(rhs.numberSolToStopDive_),
00334 numberNodesToLimitTreeSize_(rhs.numberNodesToLimitTreeSize_),
00335 comparisonDive_(rhs.comparisonDive_->clone()),
00336 comparisonBound_(rhs.comparisonBound_->clone())
00337 {}
00338
00339
00340 DiverCompare & operator=( const DiverCompare& rhs)
00341 {
00342 if (this != &rhs) {
00343 CbcCompareBase::operator=(rhs);
00344 diver_ = rhs.diver_;
00345 numberSolToStopDive_ = rhs.numberSolToStopDive_;
00346 numberNodesToLimitTreeSize_ = rhs.numberNodesToLimitTreeSize_;
00347 delete comparisonDive_;
00348 delete comparisonBound_;
00349 comparisonDive_ = NULL;
00350 comparisonBound_ = NULL;
00351 if (rhs.comparisonDive_) comparisonDive_ = rhs.comparisonDive_->clone();
00352 if (rhs.comparisonBound_) comparisonBound_ = rhs.comparisonBound_->clone();
00353 }
00354 return *this;
00355 }
00356
00358 virtual CbcCompareBase * clone() const
00359 {
00360 return new DiverCompare(*this);
00361 }
00362
00364 virtual bool test (CbcNode * x, CbcNode * y);
00365
00367 virtual void newSolution(CbcModel * model);
00368
00370 virtual void newSolution(CbcModel * model,
00371 double objectiveAtContinuous,
00372 int numberInfeasibilitiesAtContinuous);
00373
00376 virtual bool every1000Nodes(CbcModel * model,int numberNodes);
00377
00379 void setDiver(CbcDfsDiver * diver)
00380 {
00381 diver_ = diver;
00382 }
00383
00385 void setNumberSolToStopDive(int val)
00386 {
00387 numberSolToStopDive_ = val;
00388 }
00389
00391 void setNumberNodesToLimitTreeSize(int val)
00392 {
00393 numberNodesToLimitTreeSize_ = val;
00394 }
00395
00397 void setComparisonDive(const CbcCompareBase & val)
00398 {
00399 comparisonDive_ = val.clone();
00400 }
00402 void setComparisonBound(const CbcCompareBase & val)
00403 {
00404 comparisonBound_ = val.clone();
00405 }
00406 private:
00408 CbcDfsDiver * diver_;
00410 int numberSolToStopDive_;
00412 int numberNodesToLimitTreeSize_;
00414 CbcCompareBase * comparisonDive_;
00416 CbcCompareBase * comparisonBound_;
00418 CbcCompareDepth comparisonDepth_;
00419 };
00420
00421 }
00422
00423 #endif
00424