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