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,6,"%3d up %3d %15.8e down %3d %15.8e");
00025 ADD_MSG(PS_COST_MULT,std_m, 6, "upMultiplier = %e downMultiplier = %e");
00026 ADD_MSG(PS_COST_ESTIMATES, std_m, 6, "%3d value = %e upEstimate = %e downEstimate = %e infeas = %e value2 = %e");
00027 ADD_MSG(CANDIDATE_LIST,std_m,5,
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 Ipopt::SmartPtr<Ipopt::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].downStatus()== 2 || results_[i].upStatus()==2) {
00678
00679 }
00680 if (results_[i].upStatus()!=1) {
00681 assert (results_[i].upStatus()>=0);
00682 upEstimate = results_[i].upChange();
00683 }
00684 else {
00685
00686 if (info->cutoff_<1.0e50)
00687 upEstimate = 2.0*(info->cutoff_-info->objectiveValue_);
00688 else
00689 upEstimate = 2.0*fabs(info->objectiveValue_);
00690 if (firstForcedObjectIndex_ <0) {
00691
00692 firstForcedObjectIndex_ = iObject;
00693 firstForcedWhichWay_ =0;
00694 }
00695 numberFixed++;
00696 if (fixVariables) {
00697 const OsiObject * obj = solver->object(iObject);
00698 OsiBranchingObject * branch = obj->createBranch(solver,info,0);
00699 branch->branch(solver);
00700 delete branch;
00701 }
00702 }
00703 double downEstimate;
00704 if (results_[i].downStatus()!=1) {
00705 assert (results_[i].downStatus()>=0);
00706 downEstimate = results_[i].downChange();
00707 }
00708 else {
00709
00710 if (info->cutoff_<1.0e50)
00711 downEstimate = 2.0*(info->cutoff_-info->objectiveValue_);
00712 else
00713 downEstimate = 2.0*fabs(info->objectiveValue_);
00714 if (firstForcedObjectIndex_ <0) {
00715 firstForcedObjectIndex_ = iObject;
00716 firstForcedWhichWay_ =1;
00717 }
00718 numberFixed++;
00719 if (fixVariables) {
00720 const OsiObject * obj = solver->object(iObject);
00721 OsiBranchingObject * branch = obj->createBranch(solver,info,1);
00722 branch->branch(solver);
00723 delete branch;
00724 }
00725 }
00726 double MAXMIN_CRITERION = maxminCrit(info);
00727 double value = MAXMIN_CRITERION*CoinMin(upEstimate,downEstimate) + (1.0-MAXMIN_CRITERION)*CoinMax(upEstimate,downEstimate);
00728 if (value>bestTrusted) {
00729 bestTrusted = value;
00730 bestObjectIndex_ = iObject;
00731 bestWhichWay_ = upEstimate>downEstimate ? 0 : 1;
00732
00733 const OsiObject * obj = solver->object(iObject);
00734 if (obj->preferredWay()>=0&&obj->infeasibility())
00735 bestWhichWay_ = obj->preferredWay();
00736 if (returnCode)
00737 returnCode=2;
00738 }
00739 }
00740 }
00741 else if (returnCode==3) {
00742
00743 bestObjectIndex_ = list_[0];
00744 bestWhichWay_ = 0;
00745 returnCode=0;
00746 }
00747 }
00748 else {
00749 bestObjectIndex_=list_[0];
00750 }
00751 if ( bestObjectIndex_ >=0 ) {
00752 OsiObject * obj = solver->objects()[bestObjectIndex_];
00753 obj->setWhichWay(bestWhichWay_);
00754 message(BRANCH_VAR)<<obj->columnNumber()<< bestWhichWay_
00755 <<CoinMessageEol;
00756 }
00757 message(CHOSEN_VAR)<<bestObjectIndex_<<CoinMessageEol;
00758 if (numberFixed==numberUnsatisfied_&&numberFixed)
00759 returnCode=4;
00760 return returnCode;
00761 }
00762 else {
00763 return 1;
00764 }
00765 }
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778 int
00779 BonChooseVariable::doStrongBranching( OsiSolverInterface * solver,
00780 OsiBranchingInformation *info,
00781 int numberToDo, int returnCriterion)
00782 {
00783
00784 double bestLookAhead_ = -COIN_DBL_MAX;
00785 int trialsSinceBest_ = 0;
00786 bool isRoot = isRootNode(info);
00787
00788 double * saveLower = NULL;
00789 double * saveUpper = NULL;
00790 int numberColumns = solver->getNumCols();
00791 solver->markHotStart();
00792 const double * lower = info->lower_;
00793 const double * upper = info->upper_;
00794 saveLower = CoinCopyOfArray(info->lower_,numberColumns);
00795 saveUpper = CoinCopyOfArray(info->upper_,numberColumns);
00796 int returnCode=0;
00797 double timeStart = CoinCpuTime();
00798 int iDo = 0;
00799 for (;iDo<numberToDo;iDo++) {
00800 HotInfo * result = results_() + iDo;
00801
00802 OsiBranchingObject * branch = result->branchingObject();
00803 assert (branch->numberBranches()==2);
00804
00805
00806
00807
00808
00809 OsiSolverInterface * thisSolver = solver;
00810 if (branch->boundBranch()) {
00811
00812 branch->branch(solver);
00813
00814 solver->solveFromHotStart() ;
00815
00816
00817 } else {
00818
00819 thisSolver = solver->clone();
00820 branch->branch(thisSolver);
00821
00822 int limit;
00823 thisSolver->getIntParam(OsiMaxNumIterationHotStart,limit);
00824 thisSolver->setIntParam(OsiMaxNumIteration,limit);
00825 thisSolver->resolve();
00826 }
00827
00828
00829 int status0 = result->updateInformation(thisSolver,info,this);
00830 if (status0==3) {
00831
00832 if (trustStrongForSolution_) {
00833 info->cutoff_ = goodObjectiveValue_;
00834 status0=0;
00835 }
00836 }
00837 if(solver->getRowCutDebugger() && status0 == 1 ){
00838 OsiTMINLPInterface * tminlp_solver = dynamic_cast<OsiTMINLPInterface *> (solver);
00839 throw tminlp_solver->newUnsolvedError(1, tminlp_solver->problem(), "SB");
00840 }
00841 numberStrongIterations_ += thisSolver->getIterationCount();
00842 if (solver!=thisSolver)
00843 delete thisSolver;
00844
00845 for (int j=0;j<numberColumns;j++) {
00846 if (saveLower[j] != lower[j])
00847 solver->setColLower(j,saveLower[j]);
00848 if (saveUpper[j] != upper[j])
00849 solver->setColUpper(j,saveUpper[j]);
00850 }
00851
00852
00853
00854 thisSolver = solver;
00855 if (branch->boundBranch()) {
00856
00857 branch->branch(solver);
00858
00859 fflush(stdout);
00860 solver->solveFromHotStart() ;
00861 } else {
00862
00863 thisSolver = solver->clone();
00864 branch->branch(thisSolver);
00865
00866 int limit;
00867 thisSolver->getIntParam(OsiMaxNumIterationHotStart,limit);
00868 thisSolver->setIntParam(OsiMaxNumIteration,limit);
00869
00870
00871 thisSolver->resolve();
00872 }
00873
00874
00875 int status1 = result->updateInformation(thisSolver,info,this);
00876 numberStrongDone_++;
00877 if (status1==3) {
00878
00879 if (trustStrongForSolution_) {
00880 info->cutoff_ = goodObjectiveValue_;
00881 status1=0;
00882 }
00883 }
00884 if(solver->getRowCutDebugger() && status1 == 1){
00885 OsiTMINLPInterface * tminlp_solver = dynamic_cast<OsiTMINLPInterface *> (solver);
00886 throw tminlp_solver->newUnsolvedError(1, tminlp_solver->problem(), "SB");
00887 }
00888 numberStrongIterations_ += thisSolver->getIterationCount();
00889 if (solver!=thisSolver)
00890 delete thisSolver;
00891
00892 for (int j=0;j<numberColumns;j++) {
00893 if (saveLower[j] != lower[j])
00894 solver->setColLower(j,saveLower[j]);
00895 if (saveUpper[j] != upper[j])
00896 solver->setColUpper(j,saveUpper[j]);
00897 }
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907
00908 if (status0==1&&status1==1) {
00909
00910 returnCode=-1;
00911 break;
00912 } else if (status0==1||status1==1) {
00913 numberStrongFixed_++;
00914 if (!returnCriterion) {
00915 returnCode=1;
00916 } else {
00917 returnCode=2;
00918 break;
00919 }
00920 }
00921 bool hitMaxTime = ( CoinCpuTime()-timeStart > info->timeRemaining_)
00922 || ( CoinCpuTime() - start_time_ > time_limit_);
00923 if (hitMaxTime) {
00924 returnCode=3;
00925 break;
00926 }
00927
00928 if (!isRoot && numberLookAhead_) {
00929 assert(status0==0 && status1==0);
00930 double upEstimate = result->upChange();
00931 double downEstimate = result->downChange();
00932 double MAXMIN_CRITERION = maxminCrit(info);
00933 double value = MAXMIN_CRITERION*CoinMin(upEstimate,downEstimate) + (1.0-MAXMIN_CRITERION)*CoinMax(upEstimate,downEstimate);
00934 if (value > bestLookAhead_) {
00935 bestLookAhead_ = value;
00936 trialsSinceBest_ = 0;
00937 }
00938 else {
00939 trialsSinceBest_++;
00940 if (trialsSinceBest_ >= numberLookAhead_) {
00941 break;
00942 }
00943 }
00944 }
00945 }
00946 if(iDo < numberToDo) iDo++;
00947 assert(iDo <= (int) results_.size());
00948 results_.resize(iDo);
00949 delete [] saveLower;
00950 delete [] saveUpper;
00951
00952 solver->unmarkHotStart();
00953 return returnCode;
00954 }
00955
00956 bool BonChooseVariable::isRootNode(const OsiBranchingInformation *info) const
00957 {
00958 return info->depth_ == 0;
00959 }
00960
00961 double
00962 BonChooseVariable::maxminCrit(const OsiBranchingInformation *info) const
00963 {
00964 double retval = maxmin_crit_no_sol_;
00965 if (cbc_model_) {
00966
00967 const int stateOfSearch = cbc_model_->stateOfSearch();
00968 const int depth = info->depth_;
00969 if (stateOfSearch>1 && depth>10) {
00970 retval = maxmin_crit_have_sol_;
00971 }
00972 }
00973 return retval;
00974 }
00975
00976
00977 void
00978 BonChooseVariable::updateInformation(const OsiBranchingInformation *info,
00979 int branch, OsiHotInfo * hotInfo)
00980 {
00981 if(!trustStrongForPseudoCosts_) return;
00982 int index = hotInfo->whichObject();
00983 assert (index<solver_->numberObjects());
00984 const OsiObject * object = info->solver_->object(index);
00985 assert (object->upEstimate()>0.0&&object->downEstimate()>0.0);
00986 assert (branch<2);
00987 double* upTotalChange = pseudoCosts_.upTotalChange();
00988 double* downTotalChange = pseudoCosts_.downTotalChange();
00989 int* upNumber = pseudoCosts_.upNumber();
00990 int* downNumber = pseudoCosts_.downNumber();
00991 if (branch) {
00992
00993
00994
00995 if (hotInfo->upStatus()==0) {
00996 assert (hotInfo->upStatus()>=0);
00997 upTotalChange[index] += hotInfo->upChange()/object->upEstimate();
00998 upNumber[index]++;
00999 }
01000 else if (hotInfo->upStatus()==1) {
01001
01002 upNumber[index]++;
01003 if (info->cutoff_<1.0e50)
01004 upTotalChange[index] += 2.0*(info->cutoff_-info->objectiveValue_)/object->upEstimate();
01005 else
01006 upTotalChange[index] += 2.0*fabs(info->objectiveValue_)/object->upEstimate();
01007 }
01008 }
01009 else {
01010 if (hotInfo->downStatus()==0) {
01011 assert (hotInfo->downStatus()>=0);
01012 downTotalChange[index] += hotInfo->downChange()/object->downEstimate();
01013 downNumber[index]++;
01014 }
01015 else if (hotInfo->downStatus()==1) {
01016 downNumber[index]++;
01017
01018 if (info->cutoff_<1.0e50)
01019 downTotalChange[index] += 2.0*(info->cutoff_-info->objectiveValue_)/object->downEstimate();
01020 else
01021 downTotalChange[index] += 2.0*fabs(info->objectiveValue_)/object->downEstimate();
01022 }
01023 }
01024 }
01025
01026
01027 void
01028 BonChooseVariable::updateInformation( int index, int branch,
01029 double changeInObjective, double changeInValue,
01030 int status)
01031 {
01032 if(cbc_model_ == NULL) return;
01033 assert (index<solver_->numberObjects());
01034 assert (branch<2);
01035
01036 if(fabs(changeInValue) < 1e-6) return;
01037
01038 double* upTotalChange = pseudoCosts_.upTotalChange();
01039 double* downTotalChange = pseudoCosts_.downTotalChange();
01040 int* upNumber = pseudoCosts_.upNumber();
01041 int* downNumber = pseudoCosts_.downNumber();
01042 message(UPDATE_PS_COST)<<index<< branch
01043 <<changeInObjective<<changeInValue<<status
01044 <<CoinMessageEol;
01045
01046 if (branch) {
01047 if (status!=1) {
01048 assert (status>=0);
01049 upTotalChange[index] += changeInObjective/changeInValue;
01050 upNumber[index]++;
01051 } else {
01052
01053 upNumber[index]++;
01054 assert(cbc_model_);
01055 double cutoff = cbc_model_->getCutoff();
01056 double objectiveValue = cbc_model_->getCurrentObjValue();
01057 if (cutoff<1.0e50)
01058 upTotalChange[index] += 2.0*(cutoff-objectiveValue)/changeInValue;
01059 else
01060 upTotalChange[index] += 2.0*fabs(objectiveValue)/changeInValue;
01061 }
01062 } else {
01063 if (status!=1) {
01064 assert (status>=0);
01065 downTotalChange[index] += changeInObjective/changeInValue;
01066 downNumber[index]++;
01067 } else {
01068 assert(cbc_model_);
01069
01070 downNumber[index]++;
01071 double cutoff = cbc_model_->getCutoff();
01072 double objectiveValue = cbc_model_->getCurrentObjValue();
01073 if (cutoff<1.0e50)
01074 downTotalChange[index] += 2.0*(cutoff-objectiveValue)/changeInValue;
01075 else
01076 downTotalChange[index] += 2.0*fabs(objectiveValue)/changeInValue;
01077 }
01078 }
01079 }
01080
01081
01082 HotInfo::HotInfo(): OsiHotInfo(), infeasibilities_(){
01083 }
01084
01085 HotInfo::HotInfo( OsiSolverInterface * solver,
01086 const OsiBranchingInformation *info,
01087 const OsiObject * const * objects,
01088 int whichObject):
01089 OsiHotInfo(solver, info, objects, whichObject),
01090 infeasibilities_(){
01091 infeasibilities_.resize(branchingObject_->numberBranches());
01092 }
01093
01094 HotInfo::HotInfo(const HotInfo& other): OsiHotInfo(other),
01095 infeasibilities_(other.infeasibilities_){
01096 }
01097
01098 OsiHotInfo *
01099 HotInfo::clone() const {
01100 return new HotInfo(*this);
01101 }
01102
01103 HotInfo &
01104 HotInfo::operator=(const HotInfo &rhs){
01105 if(this != &rhs){
01106 OsiHotInfo::operator=(rhs);
01107 infeasibilities_ = rhs.infeasibilities_;
01108 }
01109 return (*this);
01110 }
01111
01112 HotInfo::~HotInfo(){
01113 }
01114
01115 int
01116 HotInfo::updateInformation(const OsiSolverInterface * solver,
01117 const OsiBranchingInformation * info,
01118 OsiChooseVariable * choose){
01119
01120 int iBranch = branchingObject_->branchIndex()-1;
01121 double & infeasibility = infeasibilities_[iBranch] = 0.;
01122
01123 OsiObject ** objects = solver->objects();
01124 int numObject = solver->numberObjects();
01125 for(int i = 0 ; i < numObject ; i++){
01126 infeasibility += objects[i]->checkInfeasibility(info);
01127 }
01128 int status = OsiHotInfo::updateInformation(solver, info, choose);
01129 #if 1
01130 if(!solver->isProvenPrimalInfeasible() && !solver->isProvenOptimal()){
01131 status = 2;
01132 statuses_[iBranch] = status;
01133 }
01134 else if(solver->isProvenPrimalInfeasible() && fabs(solver->getObjValue()) < 1e-06) {
01135 fprintf(stderr, "Very small infeasibility: %g\n", solver->getObjValue());
01136 status = 2;
01137 statuses_[iBranch] = status;
01138 }
01139 #endif
01140 return status;
01141 }
01142
01143 }
01144