00001
00002
00003 #if defined(_MSC_VER)
00004
00005 # pragma warning(disable:4786)
00006 #endif
00007
00008 #include <climits>
00009 #include "BonChooseVariable.hpp"
00010 #include "CoinTime.hpp"
00011 #include "IpBlas.hpp"
00012 #include "BonMsgUtils.hpp"
00013
00014
00015 #include "CbcModel.hpp"
00016
00017 namespace Bonmin
00018 {
00019
00020 BonChooseVariable::Messages::Messages():
00021 CoinMessages((int) BON_CHOOSE_MESSAGES_DUMMY_END)
00022 {
00023 strcpy(source_,"BON");
00024 ADD_MSG(PS_COST_HISTORY,std_m,5,"%3d up %3d %15.8e down %3d %15.8e");
00025 ADD_MSG(PS_COST_MULT,std_m, 5, "upMultiplier = %e downMultiplier = %e");
00026 ADD_MSG(PS_COST_ESTIMATES, std_m, 5, "%3d value = %e upEstimate = %e downEstimate = %e infeas = %e value2 = %e");
00027 ADD_MSG(CANDIDATE_LIST,std_m,4,
00028 "list_[%5d] = %5d, usefull_[%5d] = %23.16e %23.16e");
00029 ADD_MSG(CANDIDATE_LIST2, std_m, 5,
00030 "list_[%3d] = %3d useful_[%3d] = %e");
00031 ADD_MSG(CANDIDATE_LIST3, std_m, 5,
00032 "list2[%3d] = %3d useful2[%3d] = %e");
00033 ADD_MSG(SB_HEADER, std_m,5,
00034 " DownStat DownChange UpStat UpChange");
00035 ADD_MSG(SB_RES, std_m, 5,
00036 " %3d %6s %13.6e %6s %13.6e");
00037 ADD_MSG(BRANCH_VAR, std_m, 4, "Branched on variable %i, bestWhichWay: %i");
00038 ADD_MSG(CHOSEN_VAR, std_m, 4," Choosing %d");
00039 ADD_MSG(UPDATE_PS_COST, std_m, 4,"update %3d %3d %e %e %3d");
00040 }
00041 const std::string BonChooseVariable::CNAME = "BonChooseVariable";
00042
00043 BonChooseVariable::BonChooseVariable(BabSetupBase &b, const OsiSolverInterface* solver):
00044 OsiChooseVariable(solver),
00045 results_(),
00046 cbc_model_(NULL),
00047 only_pseudo_when_trusted_(false),
00048 pseudoCosts_()
00049 {
00050 jnlst_ = b.journalist();
00051 SmartPtr<OptionsList> options = b.options();
00052
00053 handler_ = new CoinMessageHandler;
00054
00055 options->GetIntegerValue("bb_log_level", bb_log_level_, "bonmin.");
00056 handler_->setLogLevel(bb_log_level_);
00057 options->GetNumericValue("setup_pseudo_frac", setup_pseudo_frac_, "bonmin.");
00058 options->GetNumericValue("maxmin_crit_no_sol", maxmin_crit_no_sol_, "bonmin.");
00059 options->GetNumericValue("maxmin_crit_have_sol", maxmin_crit_have_sol_, "bonmin.");
00060 options->GetEnumValue("trust_strong_branching_for_pseudo_cost",trustStrongForPseudoCosts_ , "bonmin.");
00061 int sortCrit;
00062 options->GetEnumValue("candidate_sort_criterion", sortCrit, "bonmin.");
00063 #ifndef OLD_USEFULLNESS
00064 sortCrit_ = (CandidateSortCriterion) sortCrit;
00065 #endif
00066
00067 int numberObjects = solver_->numberObjects();
00068
00069 pseudoCosts_.initialize(numberObjects);
00070 int numberBeforeTrusted = b.getIntParameter(BabSetupBase::MinReliability);
00071 pseudoCosts_.setNumberBeforeTrusted(numberBeforeTrusted);
00072
00073 setNumberStrong(b.getIntParameter(BabSetupBase::NumberStrong));
00074
00076 if (!options->GetIntegerValue("number_before_trust_list", numberBeforeTrustedList_, "bonmin.")) {
00077
00078 numberBeforeTrustedList_ = numberBeforeTrusted;
00079 }
00080 options->GetIntegerValue("number_strong_branch_root", numberStrongRoot_, "bonmin.");
00081 options->GetIntegerValue("min_number_strong_branch", minNumberStrongBranch_, "bonmin.");
00082 options->GetIntegerValue("number_look_ahead", numberLookAhead_, "bonmin.");
00083
00084 }
00085
00086 BonChooseVariable::BonChooseVariable(const BonChooseVariable & rhs) :
00087 OsiChooseVariable(rhs),
00088 results_(rhs.results_),
00089 cbc_model_(rhs.cbc_model_),
00090 only_pseudo_when_trusted_(rhs.only_pseudo_when_trusted_),
00091 maxmin_crit_no_sol_(rhs.maxmin_crit_no_sol_),
00092 maxmin_crit_have_sol_(rhs.maxmin_crit_have_sol_),
00093 setup_pseudo_frac_(rhs.setup_pseudo_frac_),
00094 numberBeforeTrustedList_(rhs.numberBeforeTrustedList_),
00095 numberStrongRoot_(rhs.numberStrongRoot_),
00096 #ifndef OLD_USEFULLNESS
00097 sortCrit_(rhs.sortCrit_),
00098 #endif
00099 numberLookAhead_(rhs.numberLookAhead_),
00100 minNumberStrongBranch_(rhs.minNumberStrongBranch_),
00101 pseudoCosts_(rhs.pseudoCosts_),
00102 trustStrongForPseudoCosts_(rhs.trustStrongForPseudoCosts_)
00103 {
00104 jnlst_ = rhs.jnlst_;
00105 handler_ = rhs.handler_->clone();
00106 bb_log_level_ = rhs.bb_log_level_;
00107 DBG_ASSERT(IsValid(jnlst_));
00108 }
00109
00110 BonChooseVariable &
00111 BonChooseVariable::operator=(const BonChooseVariable & rhs)
00112 {
00113 if (this != &rhs) {
00114 OsiChooseVariable::operator=(rhs);
00115 delete handler_;
00116 handler_ = rhs.handler_->clone();
00117 jnlst_ = rhs.jnlst_;
00118 bb_log_level_ = rhs.bb_log_level_;
00119 cbc_model_ = rhs.cbc_model_;
00120 only_pseudo_when_trusted_ = rhs.only_pseudo_when_trusted_;
00121 maxmin_crit_no_sol_ = rhs.maxmin_crit_no_sol_;
00122 maxmin_crit_have_sol_ = rhs.maxmin_crit_have_sol_;
00123 setup_pseudo_frac_ = rhs.setup_pseudo_frac_;
00124 numberBeforeTrustedList_ = rhs.numberBeforeTrustedList_;
00125 numberStrongRoot_ = rhs.numberStrongRoot_;
00126 #ifndef OLD_USEFULLNESS
00127 sortCrit_ = rhs.sortCrit_;
00128 #endif
00129 minNumberStrongBranch_ = rhs.minNumberStrongBranch_;
00130 pseudoCosts_ = rhs.pseudoCosts_;
00131 trustStrongForPseudoCosts_ = rhs.trustStrongForPseudoCosts_;
00132 numberLookAhead_ = rhs.numberLookAhead_;
00133 results_ = rhs.results_;
00134 }
00135 return *this;
00136 }
00137
00138 OsiChooseVariable *
00139 BonChooseVariable::clone() const
00140 {
00141 return new BonChooseVariable(*this);
00142 }
00143
00144 BonChooseVariable::~BonChooseVariable ()
00145 {
00146 delete handler_;
00147 }
00148
00149 void
00150 BonChooseVariable::registerOptions(
00151 Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00152 {
00153 roptions->SetRegisteringCategory("Strong branching setup", RegisteredOptions::BonminCategory);
00154 roptions->AddStringOption4("candidate_sort_criterion",
00155 "Choice of the criterion to choose candidates in strong-branching",
00156 "best-ps-cost",
00157 "best-ps-cost","Sort by decreasing pseudo-cost",
00158 "worst-ps-cost", "Sort by increasing pseudo-cost",
00159 "most-fractional", "Sort by decreasing integer infeasibility",
00160 "least-fractional", "Sort by increasing integer infeasibility","");
00161
00162 roptions->setOptionExtraInfo("candidate_sort_criterion",31);
00163
00164 roptions->AddBoundedNumberOption("setup_pseudo_frac", "Proportion of strong branching list that has to be taken from most-integer-infeasible list.",
00165 0., false, 1., false, 0.5);
00166 roptions->setOptionExtraInfo("setup_pseudo_frac",31);
00167 roptions->AddBoundedNumberOption("maxmin_crit_no_sol", "Weight towards minimum in of lower and upper branching estimates when no solution has been found yet.",
00168 0., false, 1., false, 0.7);
00169 roptions->setOptionExtraInfo("maxmin_crit_no_sol",31);
00170 roptions->AddBoundedNumberOption("maxmin_crit_have_sol", "Weight towards minimum in of lower and upper branching estimates when a solution has been found.",
00171 0., false, 1., false, 0.1);
00172 roptions->setOptionExtraInfo("maxmin_crit_have_sol",31);
00173 roptions->AddLowerBoundedIntegerOption("number_before_trust_list",
00174 "Set the number of branches on a variable before its pseudo costs are to be believed during setup of strong branching candidate list.",
00175 -1, 0, "The default value is that of \"number_before_trust\"");
00176 roptions->setOptionExtraInfo("number_before_trust_list",31);
00177 roptions->AddLowerBoundedIntegerOption("number_strong_branch_root",
00178 "Maximum number of variables considered for strong branching in root node.",
00179 0, COIN_INT_MAX, "");
00180 roptions->setOptionExtraInfo("number_strong_branch_root",31);
00181
00182 roptions->AddLowerBoundedIntegerOption("min_number_strong_branch", "Sets minimum number of variables for strong branching (overriding trust)",
00183 0, 0,"");
00184 roptions->setOptionExtraInfo("min_number_strong_branch",31);
00185 roptions->AddStringOption2("trust_strong_branching_for_pseudo_cost",
00186 "Wether or not to trust strong branching results for updating pseudo costs.",
00187 "yes",
00188 "no","",
00189 "yes","",
00190 ""
00191 );
00192 roptions->setOptionExtraInfo("trust_strong_branching_for_pseudo_cost", 31);
00193
00194 roptions->AddLowerBoundedIntegerOption("number_look_ahead", "Sets limit of look-ahead strong-branching trials",
00195 0, 0,"");
00196 }
00197
00198
00199 void
00200 BonChooseVariable::computeMultipliers(double& upMult, double& downMult) const
00201 {
00202 const double* upTotalChange = pseudoCosts_.upTotalChange();
00203 const double* downTotalChange = pseudoCosts_.downTotalChange();
00204 const int* upNumber = pseudoCosts_.upNumber();
00205 const int* downNumber = pseudoCosts_.downNumber();
00206 double sumUp=0.0;
00207 double numberUp=0.0;
00208 double sumDown=0.0;
00209 double numberDown=0.0;
00210 for (int i=pseudoCosts_.numberObjects() - 1; i >= 0; --i) {
00211 sumUp += upTotalChange[i];
00212 numberUp += upNumber[i];
00213 sumDown += downTotalChange[i];
00214 numberDown += downNumber[i];
00215 message(PS_COST_HISTORY)
00216 <<i<< upNumber[i]<< upTotalChange[i]
00217 << downNumber[i]<< downTotalChange[i]<<CoinMessageEol;
00218 }
00219 upMult=(1.0+sumUp)/(1.0+numberUp);
00220 downMult=(1.0+sumDown)/(1.0+numberDown);
00221
00222 message(PS_COST_MULT)
00223 <<upMult<< downMult<<CoinMessageEol;
00224 }
00225
00226 double
00227 BonChooseVariable::computeUsefulness(const double MAXMIN_CRITERION,
00228 const double upMult, const double downMult,
00229 const double value,
00230 const OsiObject* object, int i,
00231 double& value2) const
00232 {
00233 #ifdef OLD_USEFULLNESS
00234 double sumUp = pseudoCosts_.upTotalChange()[i]+1.0e-30;
00235 int numberUp = pseudoCosts_.upNumber()[i];
00236 double sumDown = pseudoCosts_.downTotalChange()[i]+1.0e-30;
00237 int numberDown = pseudoCosts_.downNumber()[i];
00238 double upEst = object->upEstimate();
00239 double downEst = object->downEstimate();
00240 upEst = numberUp ? ((upEst*sumUp)/numberUp) : (upEst*upMult);
00241
00242
00243 downEst = numberDown ? ((downEst*sumDown)/numberDown) : (downEst*downMult);
00244
00245
00246 double useful = ( MAXMIN_CRITERION*CoinMin(upEst,downEst) +
00247 (1.0-MAXMIN_CRITERION)*CoinMax(upEst,downEst) );
00248 value2 = -COIN_DBL_MAX;
00249 if (numberUp < numberBeforeTrustedList_ ||
00250 numberDown < numberBeforeTrustedList_) {
00251 value2 = value;
00252 }
00253 #else
00254
00255 int numberUp = pseudoCosts_.upNumber()[i];
00256 int numberDown = pseudoCosts_.downNumber()[i];
00257 if (sortCrit_ >= DecrPs && sortCrit_ <= IncrPs) {
00258 double sumUp = pseudoCosts_.upTotalChange()[i]+1.0e-30;
00259 double sumDown = pseudoCosts_.downTotalChange()[i]+1.0e-30;
00260 double upEst = object->upEstimate();
00261 double downEst = object->downEstimate();
00262 upEst = numberUp ? ((upEst*sumUp)/numberUp) : (upEst*upMult);
00263
00264
00265 downEst = numberDown ? ((downEst*sumDown)/numberDown) : (downEst*downMult);
00266
00267
00268 double useful = ( MAXMIN_CRITERION*CoinMin(upEst,downEst) +
00269 (1.0-MAXMIN_CRITERION)*CoinMax(upEst,downEst) );
00270 if (numberUp == 0 || numberDown == 0) {
00271 if (value == 0.) useful = 0;
00272 else if (MAXMIN_CRITERION >= 0.5)
00273 useful = CoinMin(upEst, downEst);
00274 else {
00275 useful = CoinMax(upEst, downEst);
00276 }
00277 }
00278 value2 = -COIN_DBL_MAX;
00279 if (numberUp < numberBeforeTrustedList_ ||
00280 numberDown < numberBeforeTrustedList_) {
00281 value2 = value;
00282 }
00283 #endif
00284 message(PS_COST_ESTIMATES)
00285 <<i<< useful<< upEst<< downEst<< value<< value2<< CoinMessageEol;
00286 return useful;
00287 }
00288 #ifndef OLD_USEFULLNESS
00289 else if (sortCrit_ >= DecrInfeas && sortCrit_ <= IncrInfeas) {
00290 double usefull = value;
00291 value2 = value;
00292 return usefull;
00293 }
00294 else {
00295 throw CoinError("BonChooseVariable", "computeUsefullnee",
00296 "Unknown criterion for soring candidates");
00297 return COIN_DBL_MAX;
00298 }
00299 }
00300 #endif
00301
00302 int
00303 BonChooseVariable::setupList ( OsiBranchingInformation *info, bool initialize)
00304 {
00305 if (numberBeforeTrustedList_ < 0) {
00306 number_not_trusted_ = 1;
00307 return OsiChooseVariable::setupList(info, initialize);
00308 }
00309 if (initialize) {
00310 status_=-2;
00311 delete [] goodSolution_;
00312 bestObjectIndex_=-1;
00313 numberStrongDone_=0;
00314 numberStrongIterations_ = 0;
00315 numberStrongFixed_ = 0;
00316 goodSolution_ = NULL;
00317 goodObjectiveValue_ = COIN_DBL_MAX;
00318 number_not_trusted_=0;
00319 }
00320 else {
00321 throw CoinError(CNAME,"setupList","Should not be called with initialize==false");
00322 }
00323 numberOnList_=0;
00324 numberUnsatisfied_=0;
00325 int numberObjects = solver_->numberObjects();
00326 assert (numberObjects);
00327 if (numberObjects>pseudoCosts_.numberObjects()) {
00328
00329
00330
00331
00332
00333 int saveNumberBeforeTrusted = pseudoCosts_.numberBeforeTrusted();
00334 pseudoCosts_.initialize(numberObjects);
00335 pseudoCosts_.setNumberBeforeTrusted(saveNumberBeforeTrusted);
00336 }
00337 double check = -COIN_DBL_MAX;
00338 int checkIndex=0;
00339 int bestPriority=COIN_INT_MAX;
00340 int maximumStrong= CoinMin(CoinMax(numberStrong_,numberStrongRoot_),
00341 numberObjects) ;
00342 int putOther = numberObjects;
00343 int i;
00344 for (i=0;i<numberObjects;i++) {
00345 list_[i]=-1;
00346 useful_[i]=0.0;
00347 }
00348
00349 int* list2 = NULL;
00350 double* useful2 = NULL;
00351 double check2 = -COIN_DBL_MAX;
00352 int checkIndex2=0;
00353 int max_most_fra = setup_pseudo_frac_ > 0. ? (int)floor(setup_pseudo_frac_*(double)maximumStrong): 0;
00354 if (setup_pseudo_frac_ > 0.) {
00355 max_most_fra = CoinMax(1, max_most_fra);
00356 }
00357 if (max_most_fra) {
00358 list2 = new int[max_most_fra];
00359 useful2 = new double[max_most_fra];
00360 for (i=0;i<max_most_fra;i++) {
00361 list2[i]=-1;
00362 useful2[i]=0.0;
00363 }
00364 }
00365
00366 OsiObject ** object = info->solver_->objects();
00367 double upMultiplier, downMultiplier;
00368 computeMultipliers(upMultiplier, downMultiplier);
00369
00370
00371 bool feasible = true;
00372 const double MAXMIN_CRITERION = maxminCrit(info);
00373 for ( i=0;i<numberObjects;i++) {
00374 int way;
00375 double value = object[i]->infeasibility(info,way);
00376 if (value>0.0) {
00377 numberUnsatisfied_++;
00378 if (value>=1e50) {
00379
00380 feasible=false;
00381 break;
00382 }
00383 int priorityLevel = object[i]->priority();
00384
00385 if (priorityLevel<bestPriority) {
00386 for (int j=maximumStrong-1;j>=0;j--) {
00387 if (list_[j]>=0) {
00388 int iObject = list_[j];
00389 list_[j]=-1;
00390 useful_[j]=0.0;
00391 list_[--putOther]=iObject;
00392 }
00393 }
00394 maximumStrong = CoinMin(maximumStrong,putOther);
00395 bestPriority = priorityLevel;
00396 check=-COIN_DBL_MAX;
00397 checkIndex=0;
00398 check2=-COIN_DBL_MAX;
00399 checkIndex2=0;
00400 number_not_trusted_=0;
00401 if (max_most_fra>0) {
00402 for (int j=0;j<max_most_fra;j++) {
00403 list2[j]=-1;
00404 useful2[j]=0.0;
00405 }
00406 }
00407 }
00408 if (priorityLevel==bestPriority) {
00409
00410 double value2;
00411 value = computeUsefulness(MAXMIN_CRITERION,
00412 upMultiplier, downMultiplier, value,
00413 object[i], i, value2);
00414 if (value>check) {
00415
00416 int iObject = list_[checkIndex];
00417 if (iObject>=0) {
00418 assert (list_[putOther-1]<0);
00419 list_[--putOther]=iObject;
00420 }
00421 list_[checkIndex]=i;
00422 assert (checkIndex<putOther);
00423 useful_[checkIndex]=value;
00424
00425 check=COIN_DBL_MAX;
00426 maximumStrong = CoinMin(maximumStrong,putOther);
00427 for (int j=0;j<maximumStrong;j++) {
00428 if (list_[j]>=0) {
00429 if (useful_[j]<check) {
00430 check=useful_[j];
00431 checkIndex=j;
00432 }
00433 }
00434 else {
00435 check=0.0;
00436 checkIndex = j;
00437 break;
00438 }
00439 }
00440 }
00441 else {
00442
00443 assert (list_[putOther-1]<0);
00444 list_[--putOther]=i;
00445 maximumStrong = CoinMin(maximumStrong,putOther);
00446 }
00447 if (max_most_fra > 0 && value2>check2) {
00448
00449 number_not_trusted_++;
00450 list2[checkIndex2]=i;
00451 useful2[checkIndex2]=value2;
00452
00453 check2=COIN_DBL_MAX;
00454 for (int j=0;j<max_most_fra;j++) {
00455 if (list2[j]>=0) {
00456 if (useful2[j]<check2) {
00457 check2=useful2[j];
00458 checkIndex2=j;
00459 }
00460 }
00461 else {
00462 check2=0.0;
00463 checkIndex2 = j;
00464 break;
00465 }
00466 }
00467 }
00468 }
00469 else {
00470
00471
00472 assert (list_[putOther-1]<0);
00473 list_[--putOther]=i;
00474 maximumStrong = CoinMin(maximumStrong,putOther);
00475 }
00476 }
00477 }
00478 #if 0
00479 for (int i=0; i<maximumStrong; i++) {
00480 int way;
00481 message(CANDIDATE_LIST)<<i
00482 <<list_[i]<<i<<useful_[i]<<object[list_[i]]->infeasibility(info,way)
00483 <<CoinMessageEol;
00484 }
00485 #endif
00486
00487 numberOnList_=0;
00488 if (feasible) {
00489 maximumStrong = CoinMin(maximumStrong,putOther);
00490 for (i=0;i<maximumStrong;i++) {
00491 if (list_[i]>=0) {
00492 #ifdef OLD_USEFULLNESS
00493 list_[numberOnList_]=list_[i];
00494 useful_[numberOnList_++]=-useful_[i];
00495
00496 #else
00497 list_[numberOnList_]=list_[i];
00498 if ((sortCrit_ & 1) == 0) {
00499 useful_[numberOnList_++]=-useful_[i];
00500 }
00501 else useful_[numberOnList_++] = useful_[i];
00502 #endif
00503 message(CANDIDATE_LIST2)<<numberOnList_-1
00504 <<list_[numberOnList_-1]<<numberOnList_-1<<useful_[numberOnList_-1]
00505 <<CoinMessageEol;
00506 }
00507 }
00508 if (numberOnList_) {
00509 int tmp_on_list = 0;
00510 if (max_most_fra > 0 && numberOnList_ >= maximumStrong) {
00511
00512
00513 number_not_trusted_=0;
00514 for (i=0;i<max_most_fra;i++) {
00515 if (list2[i]>=0) {
00516 list2[number_not_trusted_] = list2[i];
00517 useful2[number_not_trusted_++] = useful2[i];
00518 message(CANDIDATE_LIST3)<<number_not_trusted_-1
00519 <<list2[number_not_trusted_-1]<<number_not_trusted_-1
00520 <<useful2[number_not_trusted_-1]<<CoinMessageEol;
00521 }
00522 }
00523 if (number_not_trusted_) {
00524 CoinSort_2(list_,list_+numberOnList_,useful_);
00525 CoinSort_2(list2,list2+number_not_trusted_,useful2);
00526 int i1=0;
00527 int i2=0;
00528 for (i=0; i<numberObjects; i++) {
00529 bool found1 = (list_[i1]==i);
00530 bool found2 = (list2[i2]==i);
00531 if (found1 && found2) {
00532 useful_[i1] = -1e150*(1.+useful2[i2]);
00533 list2[i2] = -1;
00534 }
00535 if (found1) i1++;
00536 if (found2) i2++;
00537 if (i2==max_most_fra) break;
00538 }
00539 for (i=0; i<number_not_trusted_; i++) {
00540 if (list2[i] >= 0) {
00541 list_[numberOnList_+tmp_on_list] = list2[i];
00542 useful_[numberOnList_+tmp_on_list] = -1e150*(1.+useful2[i]);
00543 tmp_on_list++;
00544 }
00545 }
00546 }
00547 }
00548
00549 CoinSort_2(useful_,useful_+numberOnList_+tmp_on_list,list_);
00550
00551 i = numberOnList_;
00552 for (;putOther<numberObjects;putOther++)
00553 list_[i++]=list_[putOther];
00554 assert (i==numberUnsatisfied_);
00555 if (!CoinMax(numberStrong_,numberStrongRoot_))
00556 numberOnList_=0;
00557 }
00558 }
00559 else {
00560
00561 numberUnsatisfied_=-1;
00562 }
00563
00564 info->defaultDual_ = -1.0;
00565 delete [] info->usefulRegion_;
00566 delete [] info->indexRegion_;
00567 delete [] list2;
00568 delete [] useful2;
00569 int way;
00570 if (bb_log_level_>3) {
00571
00572 for (int i=0; i<numberOnList_; i++){
00573 message(CANDIDATE_LIST)<<i<< list_[i]<< i<< useful_[i]
00574 <<object[list_[i]]->infeasibility(info,way)
00575 <<CoinMessageEol;
00576 }
00577 }
00578 return numberUnsatisfied_;
00579
00580 }
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594 int
00595 BonChooseVariable::chooseVariable(
00596 OsiSolverInterface * solver,
00597 OsiBranchingInformation *info,
00598 bool fixVariables)
00599 {
00600
00601
00602
00603 bool isRoot = isRootNode(info);
00604 int numberStrong = numberStrong_;
00605 if (isRoot) {
00606 numberStrong = CoinMax(numberStrong_, numberStrongRoot_);
00607 }
00608 if (numberUnsatisfied_) {
00609 const double* upTotalChange = pseudoCosts_.upTotalChange();
00610 const double* downTotalChange = pseudoCosts_.downTotalChange();
00611 const int* upNumber = pseudoCosts_.upNumber();
00612 const int* downNumber = pseudoCosts_.downNumber();
00613 int numberBeforeTrusted = pseudoCosts_.numberBeforeTrusted();
00614 int numberLeft = CoinMin(numberStrong -numberStrongDone_,numberUnsatisfied_);
00615 results_.clear();
00616 int returnCode=0;
00617 bestObjectIndex_ = -1;
00618 bestWhichWay_ = -1;
00619 firstForcedObjectIndex_ = -1;
00620 firstForcedWhichWay_ =-1;
00621 double bestTrusted=-COIN_DBL_MAX;
00622 for (int i=0;i<numberLeft;i++) {
00623 int iObject = list_[i];
00624 if (numberBeforeTrusted == 0||
00625 i < minNumberStrongBranch_ ||
00626 (
00627 only_pseudo_when_trusted_ && number_not_trusted_>0 ) ||
00628 !isRoot && (upNumber[iObject]<numberBeforeTrusted ||
00629 downNumber[iObject]<numberBeforeTrusted )||
00630 isRoot && (!upNumber[iObject] && !downNumber[iObject]) ) {
00631
00632 results_.push_back(HotInfo(solver, info,
00633 solver->objects(), iObject));
00634 }
00635 else {
00636 const OsiObject * obj = solver->object(iObject);
00637 double upEstimate = (upTotalChange[iObject]*obj->upEstimate())/upNumber[iObject];
00638 double downEstimate = (downTotalChange[iObject]*obj->downEstimate())/downNumber[iObject];
00639 double MAXMIN_CRITERION = maxminCrit(info);
00640 double value = MAXMIN_CRITERION*CoinMin(upEstimate,downEstimate) + (1.0-MAXMIN_CRITERION)*CoinMax(upEstimate,downEstimate);
00641 if (value > bestTrusted) {
00642 bestObjectIndex_=iObject;
00643 bestWhichWay_ = upEstimate>downEstimate ? 0 : 1;
00644 bestTrusted = value;
00645 }
00646 }
00647 }
00648 int numberFixed=0;
00649 if (results_.size() > 0) {
00650 returnCode = doStrongBranching(solver, info, results_.size(), 1);
00651 if (bb_log_level_>=3) {
00652 const char* stat_msg[] = {"NOTDON", "FEAS", "INFEAS", "NOFINI"};
00653 message(SB_HEADER)<<CoinMessageEol;
00654 for (unsigned int i = 0; i< results_.size(); i++) {
00655 double up_change = results_[i].upChange();
00656 double down_change = results_[i].downChange();
00657 int up_status = results_[i].upStatus();
00658 int down_status = results_[i].downStatus();
00659 message(SB_RES)<<(int) i<<stat_msg[down_status+1]<<down_change
00660 <<stat_msg[up_status+1]<< up_change<< CoinMessageEol;
00661 }
00662 }
00663 if (returnCode>=0&&returnCode<=2) {
00664 if (returnCode) {
00665 returnCode=4;
00666 if (bestObjectIndex_>=0)
00667 returnCode=3;
00668 }
00669 for (unsigned int i=0;i < results_.size();i++) {
00670 int iObject = results_[i].whichObject();
00671 double upEstimate;
00672 if (results_[i].upStatus()!=1) {
00673 assert (results_[i].upStatus()>=0);
00674 upEstimate = results_[i].upChange();
00675 }
00676 else {
00677
00678 if (info->cutoff_<1.0e50)
00679 upEstimate = 2.0*(info->cutoff_-info->objectiveValue_);
00680 else
00681 upEstimate = 2.0*fabs(info->objectiveValue_);
00682 if (firstForcedObjectIndex_ <0) {
00683
00684 firstForcedObjectIndex_ = iObject;
00685 firstForcedWhichWay_ =0;
00686 }
00687 numberFixed++;
00688 if (fixVariables) {
00689 const OsiObject * obj = solver->object(iObject);
00690 OsiBranchingObject * branch = obj->createBranch(solver,info,0);
00691 branch->branch(solver);
00692 delete branch;
00693 }
00694 }
00695 double downEstimate;
00696 if (results_[i].downStatus()!=1) {
00697 assert (results_[i].downStatus()>=0);
00698 downEstimate = results_[i].downChange();
00699 }
00700 else {
00701
00702 if (info->cutoff_<1.0e50)
00703 downEstimate = 2.0*(info->cutoff_-info->objectiveValue_);
00704 else
00705 downEstimate = 2.0*fabs(info->objectiveValue_);
00706 if (firstForcedObjectIndex_ <0) {
00707 firstForcedObjectIndex_ = iObject;
00708 firstForcedWhichWay_ =1;
00709 }
00710 numberFixed++;
00711 if (fixVariables) {
00712 const OsiObject * obj = solver->object(iObject);
00713 OsiBranchingObject * branch = obj->createBranch(solver,info,1);
00714 branch->branch(solver);
00715 delete branch;
00716 }
00717 }
00718 double MAXMIN_CRITERION = maxminCrit(info);
00719 double value = MAXMIN_CRITERION*CoinMin(upEstimate,downEstimate) + (1.0-MAXMIN_CRITERION)*CoinMax(upEstimate,downEstimate);
00720 if (value>bestTrusted) {
00721 bestTrusted = value;
00722 bestObjectIndex_ = iObject;
00723 bestWhichWay_ = upEstimate>downEstimate ? 0 : 1;
00724
00725 const OsiObject * obj = solver->object(iObject);
00726 if (obj->preferredWay()>=0&&obj->infeasibility())
00727 bestWhichWay_ = obj->preferredWay();
00728 if (returnCode)
00729 returnCode=2;
00730 }
00731 }
00732 }
00733 else if (returnCode==3) {
00734
00735 bestObjectIndex_ = list_[0];
00736 bestWhichWay_ = 0;
00737 returnCode=0;
00738 }
00739 }
00740 else {
00741 bestObjectIndex_=list_[0];
00742 }
00743 if ( bestObjectIndex_ >=0 ) {
00744 OsiObject * obj = solver->objects()[bestObjectIndex_];
00745 obj->setWhichWay( bestWhichWay_);
00746 message(BRANCH_VAR)<<obj->columnNumber()<< bestWhichWay_
00747 <<CoinMessageEol;
00748 }
00749 message(CHOSEN_VAR)<<bestObjectIndex_<<CoinMessageEol;
00750 if (numberFixed==numberUnsatisfied_&&numberFixed)
00751 returnCode=4;
00752 return returnCode;
00753 }
00754 else {
00755 return 1;
00756 }
00757 }
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770 int
00771 BonChooseVariable::doStrongBranching( OsiSolverInterface * solver,
00772 OsiBranchingInformation *info,
00773 int numberToDo, int returnCriterion)
00774 {
00775
00776 double bestLookAhead_ = -COIN_DBL_MAX;
00777 int trialsSinceBest_ = 0;
00778 bool isRoot = isRootNode(info);
00779
00780 double * saveLower = NULL;
00781 double * saveUpper = NULL;
00782 int numberColumns = solver->getNumCols();
00783 solver->markHotStart();
00784 const double * lower = info->lower_;
00785 const double * upper = info->upper_;
00786 saveLower = CoinCopyOfArray(info->lower_,numberColumns);
00787 saveUpper = CoinCopyOfArray(info->upper_,numberColumns);
00788 int returnCode=0;
00789 double timeStart = CoinCpuTime();
00790 int iDo = 0;
00791 for (;iDo<numberToDo;iDo++) {
00792 HotInfo * result = results_() + iDo;
00793
00794 OsiBranchingObject * branch = result->branchingObject();
00795 assert (branch->numberBranches()==2);
00796
00797
00798
00799
00800
00801 OsiSolverInterface * thisSolver = solver;
00802 if (branch->boundBranch()) {
00803
00804 branch->branch(solver);
00805
00806 solver->solveFromHotStart() ;
00807 } else {
00808
00809 thisSolver = solver->clone();
00810 branch->branch(thisSolver);
00811
00812 int limit;
00813 thisSolver->getIntParam(OsiMaxNumIterationHotStart,limit);
00814 thisSolver->setIntParam(OsiMaxNumIteration,limit);
00815 thisSolver->resolve();
00816 }
00817
00818
00819 int status0 = result->updateInformation(thisSolver,info,this);
00820 if (status0==3) {
00821
00822 if (trustStrongForSolution_) {
00823 info->cutoff_ = goodObjectiveValue_;
00824 status0=0;
00825 }
00826 }
00827 numberStrongIterations_ += thisSolver->getIterationCount();
00828 if (solver!=thisSolver)
00829 delete thisSolver;
00830
00831 for (int j=0;j<numberColumns;j++) {
00832 if (saveLower[j] != lower[j])
00833 solver->setColLower(j,saveLower[j]);
00834 if (saveUpper[j] != upper[j])
00835 solver->setColUpper(j,saveUpper[j]);
00836 }
00837
00838
00839
00840 thisSolver = solver;
00841 if (branch->boundBranch()) {
00842
00843 branch->branch(solver);
00844
00845 solver->solveFromHotStart() ;
00846 } else {
00847
00848 thisSolver = solver->clone();
00849 branch->branch(thisSolver);
00850
00851 int limit;
00852 thisSolver->getIntParam(OsiMaxNumIterationHotStart,limit);
00853 thisSolver->setIntParam(OsiMaxNumIteration,limit);
00854 thisSolver->resolve();
00855 }
00856
00857
00858 int status1 = result->updateInformation(thisSolver,info,this);
00859 numberStrongDone_++;
00860 if (status1==3) {
00861
00862 if (trustStrongForSolution_) {
00863 info->cutoff_ = goodObjectiveValue_;
00864 status1=0;
00865 }
00866 }
00867 numberStrongIterations_ += thisSolver->getIterationCount();
00868 if (solver!=thisSolver)
00869 delete thisSolver;
00870
00871 for (int j=0;j<numberColumns;j++) {
00872 if (saveLower[j] != lower[j])
00873 solver->setColLower(j,saveLower[j]);
00874 if (saveUpper[j] != upper[j])
00875 solver->setColUpper(j,saveUpper[j]);
00876 }
00877
00878
00879
00880
00881
00882
00883
00884
00885
00886
00887 if (status0==1&&status1==1) {
00888
00889 returnCode=-1;
00890 break;
00891 } else if (status0==1||status1==1) {
00892 numberStrongFixed_++;
00893 if (!returnCriterion) {
00894 returnCode=1;
00895 } else {
00896 returnCode=2;
00897 break;
00898 }
00899 }
00900 bool hitMaxTime = ( CoinCpuTime()-timeStart > info->timeRemaining_);
00901 if (hitMaxTime) {
00902 returnCode=3;
00903 break;
00904 }
00905
00906 if (!isRoot && numberLookAhead_) {
00907 assert(status0==0 && status1==0);
00908 double upEstimate = result->upChange();
00909 double downEstimate = result->downChange();
00910 double MAXMIN_CRITERION = maxminCrit(info);
00911 double value = MAXMIN_CRITERION*CoinMin(upEstimate,downEstimate) + (1.0-MAXMIN_CRITERION)*CoinMax(upEstimate,downEstimate);
00912 if (value > bestLookAhead_) {
00913 bestLookAhead_ = value;
00914 trialsSinceBest_ = 0;
00915 }
00916 else {
00917 trialsSinceBest_++;
00918 if (trialsSinceBest_ >= numberLookAhead_) {
00919 break;
00920 }
00921 }
00922 }
00923 }
00924 if(iDo < numberToDo) iDo++;
00925 assert(iDo <= (int) results_.size());
00926 results_.resize(iDo);
00927 delete [] saveLower;
00928 delete [] saveUpper;
00929
00930 solver->unmarkHotStart();
00931 return returnCode;
00932 }
00933
00934 bool BonChooseVariable::isRootNode(const OsiBranchingInformation *info) const
00935 {
00936 return info->depth_ == 0;
00937 }
00938
00939 double
00940 BonChooseVariable::maxminCrit(const OsiBranchingInformation *info) const
00941 {
00942 double retval = maxmin_crit_no_sol_;
00943 if (cbc_model_) {
00944
00945 const int stateOfSearch = cbc_model_->stateOfSearch();
00946 const int depth = info->depth_;
00947 if (stateOfSearch>1 && depth>10) {
00948 retval = maxmin_crit_have_sol_;
00949 }
00950 }
00951 return retval;
00952 }
00953
00954
00955 void
00956 BonChooseVariable::updateInformation(const OsiBranchingInformation *info,
00957 int branch, OsiHotInfo * hotInfo)
00958 {
00959 if(!trustStrongForPseudoCosts_) return;
00960 int index = hotInfo->whichObject();
00961 assert (index<solver_->numberObjects());
00962 const OsiObject * object = info->solver_->object(index);
00963 assert (object->upEstimate()>0.0&&object->downEstimate()>0.0);
00964 assert (branch<2);
00965 double* upTotalChange = pseudoCosts_.upTotalChange();
00966 double* downTotalChange = pseudoCosts_.downTotalChange();
00967 int* upNumber = pseudoCosts_.upNumber();
00968 int* downNumber = pseudoCosts_.downNumber();
00969 if (branch) {
00970
00971
00972
00973 if (hotInfo->upStatus()==0) {
00974 assert (hotInfo->upStatus()>=0);
00975 upTotalChange[index] += hotInfo->upChange()/object->upEstimate();
00976 upNumber[index]++;
00977 }
00978 else if (hotInfo->upStatus()==1) {
00979
00980 upNumber[index]++;
00981 if (info->cutoff_<1.0e50)
00982 upTotalChange[index] += 2.0*(info->cutoff_-info->objectiveValue_)/object->upEstimate();
00983 else
00984 upTotalChange[index] += 2.0*fabs(info->objectiveValue_)/object->upEstimate();
00985 }
00986 }
00987 else {
00988 if (hotInfo->downStatus()==0) {
00989 assert (hotInfo->downStatus()>=0);
00990 downTotalChange[index] += hotInfo->downChange()/object->downEstimate();
00991 downNumber[index]++;
00992 }
00993 else if (hotInfo->downStatus()==1) {
00994 downNumber[index]++;
00995
00996 if (info->cutoff_<1.0e50)
00997 downTotalChange[index] += 2.0*(info->cutoff_-info->objectiveValue_)/object->downEstimate();
00998 else
00999 downTotalChange[index] += 2.0*fabs(info->objectiveValue_)/object->downEstimate();
01000 }
01001 }
01002 }
01003
01004
01005 void
01006 BonChooseVariable::updateInformation( int index, int branch,
01007 double changeInObjective, double changeInValue,
01008 int status)
01009 {
01010 if(cbc_model_ == NULL) return;
01011 assert (index<solver_->numberObjects());
01012 assert (branch<2);
01013 assert (changeInValue>0.0);
01014 assert (branch<2);
01015 double* upTotalChange = pseudoCosts_.upTotalChange();
01016 double* downTotalChange = pseudoCosts_.downTotalChange();
01017 int* upNumber = pseudoCosts_.upNumber();
01018 int* downNumber = pseudoCosts_.downNumber();
01019 message(UPDATE_PS_COST)<<index<< branch
01020 <<changeInObjective<<changeInValue<<status
01021 <<CoinMessageEol;
01022
01023 if (branch) {
01024 if (status!=1) {
01025 assert (status>=0);
01026 upTotalChange[index] += changeInObjective/changeInValue;
01027 upNumber[index]++;
01028 } else {
01029
01030 upNumber[index]++;
01031 assert(cbc_model_);
01032 double cutoff = cbc_model_->getCutoff();
01033 double objectiveValue = cbc_model_->getCurrentObjValue();
01034 if (cutoff<1.0e50)
01035 upTotalChange[index] += 2.0*(cutoff-objectiveValue)/changeInValue;
01036 else
01037 upTotalChange[index] += 2.0*fabs(objectiveValue)/changeInValue;
01038 }
01039 } else {
01040 if (status!=1) {
01041 assert (status>=0);
01042 downTotalChange[index] += changeInObjective/changeInValue;
01043 downNumber[index]++;
01044 } else {
01045 assert(cbc_model_);
01046
01047 downNumber[index]++;
01048 double cutoff = cbc_model_->getCutoff();
01049 double objectiveValue = cbc_model_->getCurrentObjValue();
01050 if (cutoff<1.0e50)
01051 downTotalChange[index] += 2.0*(cutoff-objectiveValue)/changeInValue;
01052 else
01053 downTotalChange[index] += 2.0*fabs(objectiveValue)/changeInValue;
01054 }
01055 }
01056 }
01057
01058
01059 HotInfo::HotInfo(): OsiHotInfo(), infeasibilities_(){
01060 }
01061
01062 HotInfo::HotInfo( OsiSolverInterface * solver,
01063 const OsiBranchingInformation *info,
01064 const OsiObject * const * objects,
01065 int whichObject):
01066 OsiHotInfo(solver, info, objects, whichObject),
01067 infeasibilities_(){
01068 infeasibilities_.resize(branchingObject_->numberBranches());
01069 }
01070
01071 HotInfo::HotInfo(const HotInfo& other): OsiHotInfo(other),
01072 infeasibilities_(other.infeasibilities_){
01073 }
01074
01075 OsiHotInfo *
01076 HotInfo::clone() const {
01077 return new HotInfo(*this);
01078 }
01079
01080 HotInfo &
01081 HotInfo::operator=(const HotInfo &rhs){
01082 if(this != &rhs){
01083 OsiHotInfo::operator=(rhs);
01084 infeasibilities_ = rhs.infeasibilities_;
01085 }
01086 return (*this);
01087 }
01088
01089 HotInfo::~HotInfo(){
01090 }
01091
01092 int
01093 HotInfo::updateInformation(const OsiSolverInterface * solver,
01094 const OsiBranchingInformation * info,
01095 OsiChooseVariable * choose){
01096
01097 int iBranch = branchingObject_->branchIndex()-1;
01098 double & infeasibility = infeasibilities_[iBranch] = 0.;
01099
01100 OsiObject ** objects = solver->objects();
01101 int numObject = solver->numberObjects();
01102 for(int i = 0 ; i < numObject ; i++){
01103 infeasibility += objects[i]->checkInfeasibility(info);
01104 }
01105 return OsiHotInfo::updateInformation(solver, info, choose);
01106 }
01107
01108 }
01109