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