/home/coin/SVN-release/OS-2.4.0/Bonmin/src/CbcBonmin/BonDiver.cpp

Go to the documentation of this file.
00001 // (C) Copyright International Business Machines Corporation 2007
00002 // All Rights Reserved.
00003 // This code is published under the Common Public License.
00004 //
00005 // Authors :
00006 // Pierre Bonami, International Business Machines Corporation
00007 //
00008 // Date : 09/01/2007
00009 
00010 #include "BonDiver.hpp"
00011 #include "CoinFinite.hpp"
00012 #include "CbcModel.hpp"
00013 #include "CbcConfig.h"
00014 #include "BonBabSetupBase.hpp"
00015 //#define DIVE_DEBUG
00016 namespace Bonmin
00017 {
00018 
00019   /************************************************************************/
00020   /*                CbcDiver methods                                       */
00021   /************************************************************************/
00022 
00024   CbcDiver::CbcDiver(): CbcTree(),
00025       treeCleaning_(false),
00026       nextOnBranch_(NULL),
00027       stop_diving_on_cutoff_(false)
00028   {}
00029 
00031   CbcDiver::CbcDiver(const CbcDiver &rhs):CbcTree(rhs),
00032       treeCleaning_(rhs.treeCleaning_),
00033       nextOnBranch_(rhs.nextOnBranch_),
00034       stop_diving_on_cutoff_(rhs.stop_diving_on_cutoff_)
00035   {}
00036 
00038   CbcDiver &
00039   CbcDiver::operator=(const CbcDiver &rhs)
00040   {
00041     if (this != &rhs) {
00042       CbcTree::operator=(rhs);
00043       treeCleaning_ = rhs.treeCleaning_;
00044       nextOnBranch_ = rhs.nextOnBranch_;
00045       stop_diving_on_cutoff_ = rhs.stop_diving_on_cutoff_;
00046     }
00047     return *this;
00048   }
00049 
00051   CbcDiver::~CbcDiver()
00052   {}
00053 
00055   CbcTree *
00056   CbcDiver::clone() const
00057   {
00058     return new CbcDiver(*this);
00059   }
00060 
00061 
00063   CbcNode *
00064   CbcDiver::top() const
00065   {
00066 #ifdef DIVE_DEBUG
00067     std::cout<<"CbcDiver::top"<<std::endl;
00068 #endif
00069     if (nextOnBranch_ != NULL && !treeCleaning_) {
00070       return nextOnBranch_;
00071     }
00072     else return CbcTree::top();
00073   }
00074 
00076   void
00077   CbcDiver::push(CbcNode * x)
00078   {
00079 #ifdef DIVE_DEBUG
00080     std::cout<<"CbcDiver::push"<<std::endl;
00081 #endif
00082     if (treeCleaning_) return CbcTree::push(x);
00083 
00084     if (x->branchingObject()->numberBranchesLeft() == x->branchingObject()->numberBranches()) {//Not Backtracking
00085       assert(nextOnBranch_==NULL);//Should not happen twice in a row
00086       nextOnBranch_ = x;
00087     }
00088     else
00089       CbcTree::push(x);
00090   }
00091 
00093   void
00094   CbcDiver::pop()
00095   {
00096 #ifdef DIVE_DEBUG
00097     std::cout<<"CbcDiver::pop"<<std::endl;
00098 #endif
00099     if (nextOnBranch_ != NULL && !treeCleaning_) {
00100       nextOnBranch_ = NULL;
00101     }
00102     else
00103       CbcTree::pop();
00104   }
00106   CbcNode *
00107   CbcDiver::bestNode(double cutoff)
00108   {
00109 #ifdef DIVE_DEBUG
00110     std::cout<<"CbcDiver::bestNode"<<std::endl;
00111 #endif
00112     if (nextOnBranch_ != NULL && !treeCleaning_) {
00113       if (nextOnBranch_->objectiveValue() < cutoff) {
00114         if (stop_diving_on_cutoff_ && nextOnBranch_->guessedObjectiveValue() >= cutoff) {
00115           //printf("Stopping dive %g %g\n", nextOnBranch_->objectiveValue(), nextOnBranch_->guessedObjectiveValue());
00116           CbcTree::push(nextOnBranch_);
00117           nextOnBranch_ = NULL;
00118           return CbcTree::bestNode(cutoff);
00119         }
00120         //printf("Diving!! %g %g\n", nextOnBranch_->objectiveValue(), nextOnBranch_->guessedObjectiveValue());
00121         CbcNode * ret_val = nextOnBranch_;
00122         nextOnBranch_ = NULL;
00123         return ret_val;
00124       }
00125       assert(true && "We did not think we get here.");
00126       CbcTree::push(nextOnBranch_);//For safety
00127       nextOnBranch_ = NULL;
00128     }
00129     return CbcTree::bestNode(cutoff);
00130   }
00131 
00132 
00134   bool CbcDiver::empty()
00135   {
00136     return (CbcTree::empty() && (nextOnBranch_ == NULL) );
00137   }
00138 
00142   void
00143   CbcDiver::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
00144   {
00145     if (nextOnBranch_ != NULL)
00146       CbcTree::push(nextOnBranch_);
00147     nextOnBranch_=NULL;
00148     treeCleaning_ = true;
00149     CbcTree::cleanTree(model,cutoff, bestPossibleObjective);
00150     treeCleaning_ = false;
00151   }
00152 
00154   double
00155   CbcDiver::getBestPossibleObjective()
00156   {
00157     double bestPossibleObjective = (nextOnBranch_ != NULL) ? nextOnBranch_->objectiveValue() : 1e100;
00158     for (unsigned int i = 0 ; i < nodes_.size() ; i++) {
00159       if (nodes_[i] == NULL) continue;
00160       const double & obj = nodes_[i]->objectiveValue();
00161       if (obj < bestPossibleObjective) {
00162         bestPossibleObjective = obj;
00163       }
00164     }
00165     return bestPossibleObjective;
00166   }
00167 
00168   void
00169   CbcDiver::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00170   {
00171     roptions->SetRegisteringCategory("Diving options", RegisteredOptions::UndocumentedCategory);
00172     roptions->AddStringOption2(
00173       "stop_diving_on_cutoff",
00174       "Flag indicating whether we stop diving based on guessed feasible objective and the current cutoff",
00175       "no",
00176       "no", "",
00177       "yes", "");
00178     roptions->setOptionExtraInfo("stop_diving_on_cutoff", 63);
00179 
00180   }
00181 
00183   void
00184   CbcDiver::initialize(BabSetupBase &b)
00185   {
00186     b.options()->GetBoolValue("stop_diving_on_cutoff", stop_diving_on_cutoff_,
00187         b.prefix());
00188   }
00189 
00190 
00191   /************************************************************************/
00192   /*                CbcProbedDiver methods                                       */
00193   /************************************************************************/
00194 
00196   CbcProbedDiver::CbcProbedDiver(): CbcTree(),
00197       treeCleaning_(false),
00198       nextOnBranch_(NULL),
00199       candidateChild_(NULL),
00200       stop_diving_on_cutoff_(false)
00201   {}
00202 
00204   CbcProbedDiver::CbcProbedDiver(const CbcProbedDiver &rhs):CbcTree(rhs),
00205       treeCleaning_(rhs.treeCleaning_),
00206       nextOnBranch_(rhs.nextOnBranch_),
00207       candidateChild_(rhs.candidateChild_),
00208       stop_diving_on_cutoff_(rhs.stop_diving_on_cutoff_)
00209   {}
00210 
00212   CbcProbedDiver &
00213   CbcProbedDiver::operator=(const CbcProbedDiver &rhs)
00214   {
00215     if (this != &rhs) {
00216       CbcTree::operator=(rhs);
00217       treeCleaning_ = rhs.treeCleaning_;
00218       nextOnBranch_ = rhs.nextOnBranch_;
00219       candidateChild_ = rhs.candidateChild_;
00220       stop_diving_on_cutoff_ = rhs.stop_diving_on_cutoff_;
00221     }
00222     return *this;
00223   }
00224 
00226   CbcProbedDiver::~CbcProbedDiver()
00227   {}
00228 
00230   CbcTree *
00231   CbcProbedDiver::clone() const
00232   {
00233     return new CbcProbedDiver(*this);
00234   }
00235 
00236 
00238   CbcNode *
00239   CbcProbedDiver::top() const
00240   {
00241 #ifdef DIVE_DEBUG
00242     std::cout<<"CbcProbedDiver::top"<<std::endl;
00243 #endif
00244     if (nextOnBranch_ != NULL && !treeCleaning_) {
00245       return nextOnBranch_;
00246     }
00247     else if(candidateChild_ != NULL && !treeCleaning_){
00248       return candidateChild_;
00249     }
00250     else return CbcTree::top();
00251   }
00252 
00254   void
00255   CbcProbedDiver::push(CbcNode * x)
00256   {
00257 #ifdef DIVE_DEBUG
00258     std::cout<<"CbcProbedDiver::push"<<std::endl;
00259 #endif
00260     if (treeCleaning_) return CbcTree::push(x);
00261 
00262     if (x->branchingObject()->numberBranchesLeft() == x->branchingObject()->numberBranches()) {
00263       //Not Backtracking
00264       if(nextOnBranch_ == NULL && candidateChild_ == NULL){
00265 #ifdef DIVE_DEBUG
00266         printf("Putting parent %i. objective value %g\n", x, x->objectiveValue());
00267 #endif
00268         nextOnBranch_ = x;
00269         return;
00270       }
00271       if(candidateChild_ == NULL){
00272 #ifdef DIVE_DEBUG
00273         printf("Putting first kid %i. objective value %g\n", x, x->objectiveValue());
00274 #endif
00275         candidateChild_ = x;
00276         return;}
00277 #ifdef DIVE_DEBUG
00278         printf("Putting second kid %i. objective value %g\n", x, x->objectiveValue());
00279 #endif
00280       // If we get here we have two nodes follow on the best one and put the other on the tree
00281       if(comparison_.compareNodes(x,candidateChild_)){// Follow on candidateChild_
00282 #ifdef DIVE_DEBUG
00283         printf("first child %i is found better.\n", x);
00284 #endif
00285         nextOnBranch_ = candidateChild_;
00286         CbcTree::push(x);
00287         candidateChild_ = NULL;
00288         return;
00289       }
00290       else {// Follow on x
00291 #ifdef DIVE_DEBUG
00292         printf("second child %i is found better\n", x);
00293 #endif
00294         nextOnBranch_ = x;
00295         CbcTree::push(candidateChild_);
00296         candidateChild_ = NULL;
00297         return;
00298       }
00299     }
00300     else {
00301 #ifdef DIVE_DEBUG
00302         printf("Putting back parent %i.\n",x);
00303 #endif
00304       if(nextOnBranch_ != NULL){
00305 #ifdef DIVE_DEBUG
00306         printf("Putting nextOnBranch_ in candidateChild_.\n");
00307 #endif
00308         assert(candidateChild_ == NULL);
00309         candidateChild_ = nextOnBranch_;
00310       }
00311       nextOnBranch_ = x;
00312       return;
00313       //CbcTree::push(x);
00314     }
00315   }
00317   void
00318   CbcProbedDiver::pop()
00319   {
00320 #ifdef DIVE_DEBUG
00321     std::cout<<"CbcProbedDiver::pop"<<std::endl;
00322 #endif
00323     if (nextOnBranch_ != NULL && !treeCleaning_) {
00324       nextOnBranch_ = NULL;
00325     }
00326     else if(candidateChild_ != NULL && !treeCleaning_){
00327       candidateChild_ = NULL;
00328     }
00329     else
00330       CbcTree::pop();
00331   }
00333   CbcNode *
00334   CbcProbedDiver::bestNode(double cutoff)
00335   {
00336 #ifdef DIVE_DEBUG
00337     std::cout<<"CbcProbedDiver::bestNode"<<std::endl;
00338 #endif
00339     if (nextOnBranch_ != NULL && !treeCleaning_) {
00340       if (nextOnBranch_->objectiveValue() < cutoff) {
00341         if (stop_diving_on_cutoff_ && nextOnBranch_->guessedObjectiveValue() >= cutoff) {
00342 #ifdef DIVE_DEBUG
00343           printf("Stopping dive %g %g\n", nextOnBranch_->objectiveValue(), nextOnBranch_->guessedObjectiveValue());
00344 #endif
00345           CbcTree::push(nextOnBranch_);
00346           nextOnBranch_ = NULL;
00347           //Also have to cleanup candidateChild_
00348           CbcTree::push(candidateChild_);
00349           candidateChild_ = NULL;
00350           return CbcTree::bestNode(cutoff);
00351         }
00352 #ifdef DIVE_DEBUG
00353         printf("Diving on %i. obj=%g guesses=%g\n", nextOnBranch_, 
00354                 nextOnBranch_->objectiveValue(), 
00355                 nextOnBranch_->guessedObjectiveValue());
00356 #endif
00357         CbcNode * ret_val = nextOnBranch_;
00358         nextOnBranch_ = NULL;
00359         return ret_val;
00360       }
00361       assert(true && "Should not get here.");
00362       CbcTree::push(nextOnBranch_);//For safety
00363       nextOnBranch_ = NULL;
00364     }
00365     else if(candidateChild_ != NULL && ! treeCleaning_){
00366 #ifdef DIVE_DEBUG
00367       printf("brother was infeasible!!\n``");
00368 #endif
00369       if(candidateChild_->objectiveValue() < cutoff) {
00370         if(stop_diving_on_cutoff_ && candidateChild_->guessedObjectiveValue() >= cutoff) {
00371 #ifdef DIVE_DEBUG
00372           printf("Stopping dive %g %g\n", candidateChild_->objectiveValue(), candidateChild_->guessedObjectiveValue());
00373 #endif
00374           CbcTree::push(candidateChild_);
00375           candidateChild_ = NULL;
00376           return CbcTree::bestNode(cutoff);
00377         }
00378 #ifdef DIVE_DEBUG
00379         printf("Diving on %i. obj=%g guessed=%g\n", 
00380                candidateChild_,
00381                candidateChild_->objectiveValue(), 
00382                candidateChild_->guessedObjectiveValue());
00383 #endif
00384         CbcNode * ret_val =  candidateChild_;
00385         candidateChild_ = NULL;
00386         return ret_val;
00387       }
00388       assert(true && "Should not get here.");
00389    }
00390    CbcNode * ret_val = CbcTree::bestNode(cutoff);
00391 #ifdef DIVE_DEBUG
00392         printf("Picking top of the heap node %i", ret_val);
00393 #endif
00394     return ret_val;
00395   }
00396 
00397 
00399   bool CbcProbedDiver::empty()
00400   {
00401     return (CbcTree::empty() && (nextOnBranch_ == NULL) && (candidateChild_ == NULL) );
00402   }
00403 
00407   void
00408   CbcProbedDiver::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
00409   {
00410     if (nextOnBranch_ != NULL)
00411       CbcTree::push(nextOnBranch_);
00412     if (candidateChild_ != NULL)
00413       CbcTree::push(candidateChild_);
00414     nextOnBranch_=NULL;
00415     candidateChild_ = NULL;
00416     treeCleaning_ = true;
00417     CbcTree::cleanTree(model,cutoff, bestPossibleObjective);
00418     treeCleaning_ = false;
00419   }
00420 
00422   double
00423   CbcProbedDiver::getBestPossibleObjective()
00424   {
00425     double bestPossibleObjective = (nextOnBranch_ != NULL) ? nextOnBranch_->objectiveValue() : 1e100;
00426     if(candidateChild_ != NULL && candidateChild_->objectiveValue() < bestPossibleObjective )
00427        bestPossibleObjective = candidateChild_->objectiveValue();
00428     for (unsigned int i = 0 ; i < nodes_.size() ; i++) {
00429       if (nodes_[i] == NULL) continue;
00430       const double & obj = nodes_[i]->objectiveValue();
00431       if (obj < bestPossibleObjective) {
00432         bestPossibleObjective = obj;
00433       }
00434     }
00435     return bestPossibleObjective;
00436   }
00437 
00439   void
00440   CbcProbedDiver::initialize(BabSetupBase &b)
00441   {
00442     b.options()->GetBoolValue("stop_diving_on_cutoff", stop_diving_on_cutoff_,
00443         b.prefix());
00444   }
00445 
00446   /************************************************************************/
00447   /*                CbcDfsDiver methods                                    */
00448   /************************************************************************/
00450   CbcDfsDiver::CbcDfsDiver(): CbcTree(),
00451       treeCleaning_(false),
00452       dive_(),
00453       diveListSize_(0),
00454       divingBoardDepth_(-1),
00455       cutoff_(1e100),
00456       nBacktracks_(0),
00457       maxDepthBFS_(4),
00458       maxDiveBacktracks_(2),
00459       maxDiveDepth_(COIN_INT_MAX),
00460       mode_(Enlarge)
00461   {}
00462 
00464   CbcDfsDiver::CbcDfsDiver(const CbcDfsDiver &rhs):CbcTree(rhs),
00465       treeCleaning_(rhs.treeCleaning_),
00466       dive_(rhs.dive_),
00467       diveListSize_(rhs.diveListSize_),
00468       divingBoardDepth_(rhs.divingBoardDepth_),
00469       cutoff_(rhs.cutoff_),
00470       nBacktracks_(rhs.nBacktracks_),
00471       maxDepthBFS_(rhs.maxDepthBFS_),
00472       maxDiveBacktracks_(rhs.maxDiveBacktracks_),
00473       maxDiveDepth_(rhs.maxDiveDepth_),
00474       mode_(rhs.mode_)
00475   {}
00477   CbcDfsDiver &
00478   CbcDfsDiver::operator=(const CbcDfsDiver &rhs)
00479   {
00480     if (this != &rhs) {
00481       CbcTree::operator=(rhs);
00482       treeCleaning_ = rhs.treeCleaning_;
00483       dive_ = rhs.dive_;
00484       diveListSize_ = rhs.diveListSize_;
00485       divingBoardDepth_ = rhs.divingBoardDepth_;
00486       cutoff_ = rhs.cutoff_;
00487       nBacktracks_ = rhs.nBacktracks_;
00488       maxDepthBFS_ = rhs.maxDepthBFS_;
00489       maxDiveBacktracks_ = rhs.maxDiveBacktracks_;
00490       maxDiveDepth_ = maxDiveDepth_;
00491       mode_ = rhs.mode_;
00492     }
00493     return *this;
00494   }
00495 
00497   CbcDfsDiver::~CbcDfsDiver()
00498   {}
00499 
00501   CbcTree *
00502   CbcDfsDiver::clone() const
00503   {
00504     return new CbcDfsDiver(*this);
00505   }
00506 
00508   CbcNode *
00509   CbcDfsDiver::top() const
00510   {
00511     if (treeCleaning_) return CbcTree::top();
00512 #ifdef DIVE_DEBUG
00513     std::cout<<"CbcDfsDiver::top"<<std::endl;
00514 #endif
00515     if (mode_ != CbcDfsDiver::FindSolutions) {
00516       assert(dive_.empty());
00517       CbcTree::top();
00518     }
00519     if (diveListSize_) {
00520       return dive_.front();
00521     }
00522     else return CbcTree::top();
00523   }
00524 
00526   void
00527   CbcDfsDiver::push(CbcNode * x)
00528   {
00529     if (treeCleaning_) return CbcTree::push(x);
00530 #ifdef DIVE_DEBUG
00531     std::cout<<"CbcDfsDiver::push"<<std::endl;
00532 #endif
00533     if (mode_ > CbcDfsDiver::FindSolutions) {
00534       CbcTree::push(x);
00535       assert(dive_.empty());
00536       return;
00537     }
00538     //Always push on dive;
00539     dive_.push_front(x);
00540     diveListSize_++;
00541 #ifdef DIVE_DEBUG
00542     printf("diveListSize_ = %i == %u = dive_.size()\n",diveListSize_, dive_.size());
00543     assert(diveListSize_ == dive_.size());
00544 #endif
00545   }
00546 
00548   void
00549   CbcDfsDiver::pop()
00550   {
00551     if (treeCleaning_) return CbcTree::pop();
00552 #ifdef DIVE_DEBUG
00553     std::cout<<"CbcDfsDiver::pop"<<std::endl;
00554 #endif
00555     if (mode_ > CbcDfsDiver::FindSolutions) {
00556       assert(dive_.empty());
00557     }
00558     if (!dive_.empty()) {
00559       dive_.pop_front();
00560       diveListSize_--;
00561     }
00562     else
00563       CbcTree::pop();
00564   }
00565 
00567   CbcNode *
00568   CbcDfsDiver::bestNode(double cutoff)
00569   {
00570 #ifdef DIVE_DEBUG
00571     std::cout<<"CbcDfsDiver::bestNode"<<std::endl;
00572 #endif
00573     if (treeCleaning_) return CbcTree::bestNode(cutoff);
00574 #ifdef DIVE_DEBUG
00575     for (unsigned int i = 0 ; i < nodes_.size() ; i++) {
00576       if (nodes_[i]->objectiveValue() >= cutoff)
00577         std::cerr<<"CbcDfsDiver::bestNode"<<std::endl
00578         <<nodes_[i]->objectiveValue()<<", "<<cutoff<<std::endl;
00579       assert(nodes_[i]->objectiveValue() < cutoff);
00580     }
00581 #endif
00582     if (mode_ == CbcDfsDiver::Enlarge) {
00583       if (diveListSize_ == 0)
00584         mode_ = CbcDfsDiver::FindSolutions;
00585       else {
00586         CbcNode * node = dive_.back();
00587         assert(node != NULL);
00588         if (node->depth() > maxDepthBFS_) {
00589           //Switch mode to Diving
00590           setComparisonMode(FindSolutions);
00591         }
00592         else {
00593           //pop and return node;
00594           dive_.pop_back();
00595           diveListSize_ --;
00596           return node;
00597         }
00598       }
00599     }
00600     if (mode_ != CbcDfsDiver::FindSolutions) {
00601       assert(dive_.empty());
00602       CbcTree::bestNode(cutoff);
00603     }
00604     assert(nBacktracks_ < maxDiveBacktracks_);
00605     CbcNode * node = NULL;
00606     while (diveListSize_ > 0) {
00607 #ifdef DIVE_DEBUG
00608       std::cerr<<"CbcDfsDiver::bestNode"
00609       <<", examining node"<<std::endl;
00610 #endif
00611       assert(!dive_.empty());
00612       node = dive_.front();
00613       dive_.pop_front();
00614       diveListSize_ --;
00615       assert(node);
00616       assert((node->depth() - divingBoardDepth_) <= maxDiveDepth_);
00617       if (node->objectiveValue() > cutoff) {//throw away node for now just put it on the heap as deleting a node is
00618         //more complicated than that (has to delete nodeInfo, cuts...)
00619 #ifdef DIVE_DEBUG
00620         std::cout<<"CbcDfsDiver::bestNode"
00621         <<", node above cutoff"<<std::endl;
00622 #endif
00623         CbcTree::push(node);
00624         node = NULL;
00625         nBacktracks_++;
00626       }
00627       else if (0 && node->guessedObjectiveValue() > cutoff) {//Put it on the real heap
00628 #ifdef DIVE_DEBUG
00629         std::cout<<"CbcDfsDiver::bestNode"
00630         <<", node estimates "<<node->guessedObjectiveValue()<<"above cutoff"
00631         <<cutoff<<std::endl;
00632 #endif
00633         CbcTree::push(node);
00634         nBacktracks_++;
00635         node = NULL;
00636       }
00637       else if ((node->depth() - divingBoardDepth_) > maxDiveDepth_) {//Put it on the real heap
00638 #ifdef DIVE_DEBUG
00639         std::cout<<"CbcDfsDiver::bestNode"
00640         <<", node too deep"<<std::endl;
00641 #endif
00642         CbcTree::push(node);
00643         nBacktracks_++;
00644         node = NULL;
00645       }
00646       else if (node->branchingObject()->numberBranchesLeft() < node->branchingObject()->numberBranches()) {//Backtracking
00647         nBacktracks_++;
00648 #ifdef DIVE_DEBUG
00649         std::cout<<"CbcDfsDiver::bestNode"
00650         <<", backtracking"<<std::endl;
00651 #endif
00652       }
00653       if (nBacktracks_ >= maxDiveBacktracks_) {//Push all the node in dive_ onto nodes_
00654 #ifdef DIVE_DEBUG
00655         std::cout<<"CbcDfsDiver::bestNode"
00656         <<", maximum number of backtracks attained emptying dive_"<<std::endl;
00657 #endif
00658         pushDiveOntoHeap(-COIN_DBL_MAX);
00659         if (node != NULL) CbcTree::push(node);
00660         node = NULL;
00661       }
00662       if (node != NULL)
00663         return node;
00664     }
00665     assert(node == NULL);
00666     assert(dive_.empty());
00667     assert(diveListSize_ == 0);
00668     node = CbcTree::bestNode(cutoff);
00669     divingBoardDepth_ = node->depth();
00670     nBacktracks_ = 0;
00671     return node;
00672   }
00673 
00674 
00675   void CbcDfsDiver::pushDiveOntoHeap(double cutoff)
00676   {
00677     while (!dive_.empty() ){//&& dive_.front()->objectiveValue() >= cutoff) {
00678       CbcTree::push(dive_.front());
00679       dive_.pop_front();
00680       diveListSize_--;
00681     }
00682     for (std::list<CbcNode *>::iterator i = dive_.begin() ; i != dive_.end();
00683         i++) {
00684       assert(*i != NULL);
00685     }
00686   }
00688   bool CbcDfsDiver::empty()
00689   {
00690     return (CbcTree::empty() && dive_.empty());
00691   }
00692 
00696   void
00697   CbcDfsDiver::cleanTree(CbcModel * model, double cutoff, double & bestPossibleObjective)
00698   {
00699 #ifdef DIVE_DEBUG
00700     std::cout<<"CbcDfsDiver::cleanTree"<<std::endl;
00701     std::cout<<"cutoff: "<<cutoff<<std::endl;
00702 #endif
00703     pushDiveOntoHeap(cutoff);
00704     treeCleaning_ = true;
00705     CbcTree::cleanTree(model,cutoff, bestPossibleObjective);
00706     treeCleaning_ = false;
00707   }
00708 
00710   double
00711   CbcDfsDiver::getBestPossibleObjective()
00712   {
00713 #ifdef DIVE_DEBUG
00714     std::cout<<"CbcDfsDiver::getBestPossibleObjective"<<std::endl;
00715 #endif
00716     double bestPossibleObjective = CbcTree::empty() ? COIN_DBL_MAX : CbcTree::getBestPossibleObjective();
00717     for (std::list<CbcNode *>::iterator i = dive_.begin() ; i != dive_.end() ; i++) {
00718       if (*i == NULL) continue;
00719       const double & obj = (*i)->objectiveValue();
00720       if (obj < bestPossibleObjective) {
00721         bestPossibleObjective = obj;
00722       }
00723     }
00724     return bestPossibleObjective;
00725   }
00726 //#ifdef COIN_HAS_BONMIN
00728   void
00729   CbcDfsDiver::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00730   {
00731     roptions->SetRegisteringCategory("Diving options", RegisteredOptions::UndocumentedCategory);
00732     roptions->AddLowerBoundedIntegerOption("max_backtracks_in_dive",
00733         "Set the number of backtracks in a dive when using dfs-dive tree search"
00734         "strategy.",
00735         0,5,
00736         "");
00737     roptions->setOptionExtraInfo("max_backtracks_in_dive",27);
00738 
00739     roptions->AddLowerBoundedIntegerOption("max_dive_depth",
00740         "When using dfs-dive search. Maximum depth to go to from the diving "
00741         "board (node where the diving started.",
00742         0,COIN_INT_MAX,
00743         "");
00744     roptions->setOptionExtraInfo("max_dive_depth",27);
00745 
00746   }
00747 
00749   void
00750   CbcDfsDiver::initialize(BabSetupBase &b)
00751   {
00752     b.options()->GetIntegerValue("max_dive_depth", maxDiveDepth_,b.prefix());
00753     b.options()->GetIntegerValue("max_backtracks_in_dive", maxDiveBacktracks_,b.prefix());
00754   }
00755 //#endif
00756 
00759   void
00760   CbcDfsDiver::setComparisonMode(ComparisonModes newMode)
00761   {
00762     if (newMode != mode_) {
00763       mode_ = newMode;
00764       //Empty heap
00765       pushDiveOntoHeap(-COIN_DBL_MAX);
00766       nBacktracks_ = maxDiveBacktracks_ -1;//Force to start a new dive
00767 #ifdef DIVE_DEBUG
00768       std::cout<<"CbcDfsDiver::setComparisonMode"
00769       <<std::endl;
00770       switch (mode_) {
00771       case Enlarge:
00772         std::cout<<"Enlarge"<<std::endl;
00773         break;
00774       case FindSolutions:
00775         std::cout<<"FindSolutions"<<std::endl;
00776         break;
00777       case CloseBound:
00778         std::cout<<"CloseBound"<<std::endl;
00779         break;
00780       case LimitTreeSize:
00781         std::cout<<"LimitTreeSize"<<std::endl;
00782         break;
00783       }
00784 #endif
00785       CbcTree::setComparison(*comparison_.test_); 
00786     }
00787   }
00788 
00789 
00790 
00791   // This allows any method to change behavior as it is called
00792   // after each solution
00793   bool
00794   DiverCompare::newSolution(CbcModel * model)
00795   {
00796     assert(diver_);
00797 #ifdef DIVE_DEBUG
00798     std::cout<<"CbcDfsDiver::newSolution"
00799     <<std::endl;
00800     std::cout<<"Found "<<model->getSolutionCount()<<" solutions"<<std::endl;
00801 #endif
00802     bool r_value = false;
00803     if (diver_->getComparisonMode() == CbcDfsDiver::Enlarge){
00804       diver_->setComparisonMode(CbcDfsDiver::FindSolutions);
00805       r_value = true;}
00806     if (model->getSolutionCount() >= numberSolToStopDive_ && diver_->getComparisonMode() == CbcDfsDiver::FindSolutions) {
00807       diver_->setComparisonMode(CbcDfsDiver::CloseBound);
00808       r_value = true;
00809     }
00810     return r_value;
00811   }
00812 
00814   bool
00815   DiverCompare::test (CbcNode * x, CbcNode * y)
00816   {
00817     assert(diver_);
00818     assert(comparisonDive_);
00819     assert(comparisonBound_);
00820     CbcDfsDiver::ComparisonModes mode = diver_->getComparisonMode();
00821     if (mode == CbcDfsDiver::FindSolutions) {
00822       return comparisonDive_->test(x,y);
00823     }
00824     else if (mode == CbcDfsDiver::CloseBound) {
00825       return comparisonBound_->test(x,y);
00826     }
00827     else if (mode == CbcDfsDiver::LimitTreeSize) {
00828       return comparisonDepth_.test(x,y);
00829     }
00830     else {
00831       throw -1;
00832     }
00833   }
00834 
00835 
00836   // This Also allows any method to change behavior as it is called
00837   // after each solution
00838   bool
00839   DiverCompare::newSolution(CbcModel * model,
00840       double objectiveAtContinuous,
00841       int numberInfeasibilitiesAtContinuous)
00842   { return false; }
00843 
00844   // This allows any method to change behavior as it is called
00845   // after every 1000 nodes.
00846   // Return true if want tree re-sorted
00847   bool
00848   DiverCompare::every1000Nodes(CbcModel * model,int numberNodes)
00849   {
00850     assert(diver_);
00851     if (numberNodes > numberNodesToLimitTreeSize_  && diver_->getComparisonMode() != CbcDfsDiver::LimitTreeSize) {
00852       diver_->setComparisonMode(CbcDfsDiver::LimitTreeSize);
00853       return true;
00854     }
00855     return false;
00856   }
00857 
00858 }/* Ends namespace Bonmin.*/
00859 

Generated on Thu Sep 22 03:05:54 2011 by  doxygen 1.4.7