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