/home/coin/SVN-release/OS-2.0.1/Bonmin/src/Algorithms/Branching/BonChooseVariable.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2006, 2008 International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #if defined(_MSC_VER)
00004 // Turn off compiler warning about long names
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 // This couples Cbc code into Bonmin code...
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     //std::cout<<"Number objects "<<numberObjects<<std::endl;
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       // default is to use the same value as for numberBeforeTrusted
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   //if (numberUp<numberBeforeTrusted_)
00246   //  upEst *= (numberBeforeTrusted_+1.0)/(numberUp+1.0);
00247   downEst = numberDown ? ((downEst*sumDown)/numberDown) : (downEst*downMult);
00248   //if (numberDown<numberBeforeTrusted_)
00249   //  downEst *= (numberBeforeTrusted_+1.0)/(numberDown+1.0);
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    // FIXME: Hanlding initialization correctly
00259     int numberUp = pseudoCosts_.upNumber()[i];
00260     int numberDown = pseudoCosts_.downNumber()[i];
00261     if (sortCrit_ >= DecrPs && sortCrit_ <= IncrPs) {//Using pseudo costs
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       //if (numberUp<numberBeforeTrusted_)
00268       //  upEst *= (numberBeforeTrusted_+1.0)/(numberUp+1.0);
00269       downEst = numberDown ? ((downEst*sumDown)/numberDown) : (downEst*downMult);
00270       //if (numberDown<numberBeforeTrusted_)
00271       //  downEst *= (numberBeforeTrusted_+1.0)/(numberDown+1.0);
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)//Sort on max infeasibility
00277           useful =  CoinMin(upEst, downEst);
00278         else {//Do min infeasibility
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) {//Just return infeasibility
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       //std::cout<<"Number objects "<<numberObjects<<std::endl;
00333       //AW : How could that ever happen?
00334       //PB : It happens for instance when SOS constraints are added. They are added after the creation of this.
00335       //   assert(false && "Right now, all old content is deleted!");
00336       // redo useful arrays
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     // We make a second list for most fractional variables
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     // Say feasible
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           // infeasible
00384           feasible=false;
00385           break;
00386         }
00387         int priorityLevel = object[i]->priority();
00388         // Better priority? Flush choices.
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           // Modify value
00414           double value2;
00415           value = computeUsefulness(MAXMIN_CRITERION,
00416               upMultiplier, downMultiplier, value,
00417               object[i], i, value2);
00418           if (value>check) {
00419             //add to list
00420             int iObject = list_[checkIndex];
00421             if (iObject>=0) {
00422               assert (list_[putOther-1]<0);
00423               list_[--putOther]=iObject;  // to end
00424             }
00425             list_[checkIndex]=i;
00426             assert (checkIndex<putOther);
00427             useful_[checkIndex]=value;
00428             // find worst
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             // to end
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             // add to list of integer infeasibilities
00453             number_not_trusted_++;
00454             list2[checkIndex2]=i;
00455             useful2[checkIndex2]=value2;
00456             // find worst
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           // worse priority
00475           // to end
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     // Get list
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           // If we want to force non-trusted in the list, give them huge
00516           // weight here
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         // Sort
00553         CoinSort_2(useful_,useful_+numberOnList_+tmp_on_list,list_);
00554         // move others
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       // not feasible
00565       numberUnsatisfied_=-1;
00566     }
00567     // Get rid of any shadow prices info
00568     info->defaultDual_ = -1.0; // switch off
00569     delete [] info->usefulRegion_;
00570     delete [] info->indexRegion_;
00571     delete [] list2;
00572     delete [] useful2;
00573     int way;
00574     if (bb_log_level_>3) {
00575       //for (int i=0; i<Min(numberUnsatisfied_,numberStrong_); i++)
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   /* Choose a variable
00587      Returns -
00588      -1 Node is infeasible
00589      0  Normal termination - we have a candidate
00590      1  All looks satisfied - no candidate
00591      2  We can change the bound on a variable - but we also have a strong branching candidate
00592      3  We can change the bound on a variable - but we have a non-strong branching candidate
00593      4  We can change the bound on a variable - no other candidates
00594      We can pick up branch from whichObject() and whichWay()
00595      We can pick up a forced branch (can change bound) from whichForcedObject() and whichForcedWay()
00596      If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
00597   */
00598   int
00599   BonChooseVariable::chooseVariable(
00600     OsiSolverInterface * solver,
00601     OsiBranchingInformation *info,
00602     bool fixVariables)
00603   {
00604     // We assume here that chooseVariable is called once at the very
00605     // beginning with fixVariables set to true.  This is then the root
00606     // node.
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               // infeasible - just say expensive
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                 // first fixed variable
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               // infeasible - just say expensive
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               // but override if there is a preferred way
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           // max time - just choose one
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   /*  This is a utility function which does strong branching on
00764       a list of objects and stores the results in OsiHotInfo.objects.
00765       On entry the object sequence is stored in the OsiHotInfo object
00766       and maybe more.
00767       It returns -
00768       -1 - one branch was infeasible both ways
00769        0 - all inspected - nothing can be fixed
00770        1 - all inspected - some can be fixed (returnCriterion==0)
00771        2 - may be returning early - one can be fixed (last one done) (returnCriterion==1) 
00772        3 - returning because max time
00773   */
00774   int 
00775   BonChooseVariable::doStrongBranching( OsiSolverInterface * solver, 
00776                                     OsiBranchingInformation *info,
00777                                     int numberToDo, int returnCriterion)
00778   {
00779     // Prepare stuff for look-ahead heuristic
00780     double bestLookAhead_ = -COIN_DBL_MAX;
00781     int trialsSinceBest_ = 0;
00782     bool isRoot = isRootNode(info);
00783     // Might be faster to extend branch() to return bounds changed
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       // For now just 2 way
00798       OsiBranchingObject * branch = result->branchingObject();
00799       assert (branch->numberBranches()==2);
00800       /*
00801         Try the first direction.  Each subsequent call to branch() performs the
00802         specified branch and advances the branch object state to the next branch
00803         alternative.)
00804       */
00805       OsiSolverInterface * thisSolver = solver; 
00806       if (branch->boundBranch()) {
00807         // ordinary
00808         branch->branch(solver);
00809         // maybe we should check bounds for stupidities here?
00810         solver->solveFromHotStart() ;
00811       } else {
00812         // adding cuts or something 
00813         thisSolver = solver->clone();
00814         branch->branch(thisSolver);
00815         // set hot start iterations
00816         int limit;
00817         thisSolver->getIntParam(OsiMaxNumIterationHotStart,limit);
00818         thisSolver->setIntParam(OsiMaxNumIteration,limit); 
00819         thisSolver->resolve();
00820       }
00821       // can check if we got solution
00822       // status is 0 finished, 1 infeasible and 2 unfinished and 3 is solution
00823       int status0 = result->updateInformation(thisSolver,info,this);
00824       if (status0==3) {
00825         // new solution already saved
00826         if (trustStrongForSolution_) {
00827         info->cutoff_ = goodObjectiveValue_;
00828         status0=0;
00829         }
00830       }
00831       numberStrongIterations_ += thisSolver->getIterationCount();
00832       if (solver!=thisSolver)
00833         delete thisSolver;
00834       // Restore bounds
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         Try the next direction
00843       */
00844       thisSolver = solver; 
00845       if (branch->boundBranch()) {
00846         // ordinary
00847         branch->branch(solver);
00848         // maybe we should check bounds for stupidities here?
00849         solver->solveFromHotStart() ;
00850       } else {
00851         // adding cuts or something 
00852         thisSolver = solver->clone();
00853         branch->branch(thisSolver);
00854         // set hot start iterations
00855         int limit;
00856         thisSolver->getIntParam(OsiMaxNumIterationHotStart,limit);
00857         thisSolver->setIntParam(OsiMaxNumIteration,limit); 
00858         thisSolver->resolve();
00859       }
00860       // can check if we got solution
00861       // status is 0 finished, 1 infeasible and 2 unfinished and 3 is solution
00862       int status1 = result->updateInformation(thisSolver,info,this);
00863       numberStrongDone_++;
00864       if (status1==3) {
00865         // new solution already saved
00866         if (trustStrongForSolution_) {
00867         info->cutoff_ = goodObjectiveValue_;
00868         status1=0;
00869         }
00870       }
00871       numberStrongIterations_ += thisSolver->getIterationCount();
00872       if (solver!=thisSolver)
00873         delete thisSolver;
00874       // Restore bounds
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         End of evaluation for this candidate variable. Possibilities are:
00883         * Both sides below cutoff; this variable is a candidate for branching.
00884         * Both sides infeasible or above the objective cutoff: no further action
00885         here. Break from the evaluation loop and assume the node will be purged
00886         by the caller.
00887         * One side below cutoff: Install the branch (i.e., fix the variable). Possibly break
00888         from the evaluation loop and assume the node will be reoptimised by the
00889         caller.
00890       */
00891       if (status0==1&&status1==1) {
00892         // infeasible
00893         returnCode=-1;
00894         break; // exit loop
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       // stop if look ahead heuristic tells us so
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     // Delete the snapshot
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       // FIXME: should be replaced by info->stateOfSearch_
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 // Given a candidate  fill in useful information e.g. estimates
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       //if (hotInfo->upStatus()!=1) 
00976       // AW: Let's update the pseudo costs only if the strong branching
00977       // problem was marked as "solved"
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         // infeasible - just say expensive
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         // infeasible - just say expensive
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 // Given a branch fill in useful information e.g. estimates 
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       // infeasible - just say expensive 
01035       upNumber[index]++; 
01036       assert(cbc_model_); // Later, we need to get this information in a different way... 
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       // infeasible - just say expensive 
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     //printf("in HotInfo::updateInformation\n");
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 }/* Ends Bonmin's namespace.*/
01114 

Generated on Thu Oct 8 03:02:54 2009 by  doxygen 1.4.7