00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #include "BonOaFeasChecker.hpp"
00011 #include "BonminConfig.h"
00012
00013 #include "OsiAuxInfo.hpp"
00014 #include "BonSolverHelp.hpp"
00015
00016 namespace Bonmin
00017 {
00018 static const char * txt_id = "check integer sol.";
00019
00021 OaFeasibilityChecker::OaFeasibilityChecker(BabSetupBase &b):
00022 OaDecompositionBase(b, false, true),
00023 cut_count_(0)
00024 {
00025 int ival;
00026 b.options()->GetEnumValue("feas_check_cut_types", ival, b.prefix());
00027 type_ = CutsTypes(ival);
00028 b.options()->GetEnumValue("feas_check_discard_policy", ival, b.prefix());
00029 pol_ = CutsPolicies(ival);
00030 b.options()->GetIntegerValue("generate_benders_after_so_many_oa", ival, b.prefix());
00031 maximum_oa_cuts_ = static_cast<unsigned int>(ival);
00032 }
00033 OaFeasibilityChecker ::~OaFeasibilityChecker ()
00034 {}
00035
00037 double
00038 OaFeasibilityChecker::performOa(OsiCuts & cs, solverManip &lpManip,
00039 BabInfo * babInfo, double &cutoff,const CglTreeInfo & info) const
00040 {
00041 bool isInteger = true;
00042 bool feasible = 1;
00043
00044 OsiSolverInterface * lp = lpManip.si();
00045 OsiBranchingInformation branch_info(lp,false);
00046
00047 double milpBound = -COIN_DBL_MAX;
00048 int numberPasses = 0;
00049 double * nlpSol = NULL;
00050 int numberCutsBefore = cs.sizeRowCuts();
00051
00052 while (isInteger && feasible ) {
00053 numberPasses++;
00054
00055
00056
00057
00058 double * colsol = const_cast<double *>(lp->getColSolution());
00059 branch_info.solution_ = colsol;
00060 fixIntegers(*nlp_,branch_info, parameters_.cbcIntegerTolerance_,objects_, nObjects_);
00061
00062
00063
00064 nlp_->resolve(txt_id);
00065 if (post_nlp_solve(babInfo, cutoff)) {
00066
00067
00068 double ub = nlp_->getObjValue();
00069 cutoff = ub > 0 ? ub *(1 - parameters_.cbcCutoffIncrement_) : ub*(1 + parameters_.cbcCutoffIncrement_);
00070
00071 lp->setDblParam(OsiDualObjectiveLimit, cutoff);
00072 }
00073
00074
00075 nlpSol = const_cast<double *>(nlp_->getColSolution());
00076
00077 const double * toCut = (parameter().addOnlyViolated_)?
00078 colsol:NULL;
00079 if(cut_count_ <= maximum_oa_cuts_ && type_ == OA)
00080 nlp_->getOuterApproximation(cs, nlpSol, 1, toCut,
00081 true);
00082 else {
00083 nlp_->getBendersCut(cs, parameter().global_);
00084 }
00085 if(pol_ == DetectCycles)
00086 nlp_->getBendersCut(savedCuts_, parameter().global_);
00087
00088 int numberCuts = cs.sizeRowCuts() - numberCutsBefore;
00089 cut_count_ += numberCuts;
00090 if (numberCuts > 0)
00091 installCuts(*lp, cs, numberCuts);
00092
00093 lp->resolve();
00094 double objvalue = lp->getObjValue();
00095
00096 feasible = (lp->isProvenOptimal() &&
00097 !lp->isDualObjectiveLimitReached() && (objvalue<cutoff)) ;
00098
00099 bool changed = true;
00100 isInteger = 0;
00101
00102
00103 if (feasible) {
00104 changed = isDifferentOnIntegers(*nlp_, objects_, nObjects_,
00105 0.1,
00106 nlp_->getColSolution(), lp->getColSolution());
00107 }
00108 if (changed) {
00109 branch_info.solution_ = lp->getColSolution();
00110 isInteger = integerFeasible(*lp,branch_info, parameters_.cbcIntegerTolerance_,
00111 objects_, nObjects_);
00112 }
00113 else {
00114 isInteger = 0;
00115
00116 milpBound = 1e200;
00117 }
00118 #ifdef OA_DEBUG
00119 printf("Obj value after cuts %g, %d rows\n",lp->getObjValue(),
00120 numberCuts) ;
00121 #endif
00122 }
00123 int num_cuts_now = cs.sizeRowCuts();
00124 if(pol_ == KeepAll){
00125 for(int i = numberCutsBefore ; i < num_cuts_now ; i++){
00126 cs.rowCut(i).setEffectiveness(99.9e99);
00127 }
00128 }
00129
00130 #ifdef OA_DEBUG
00131 debug_.printEndOfProcedureDebugMessage(cs, true, cutoff, milpBound, isInteger, feasible, std::cout);
00132 std::cout<<"milpBound found: "<<milpBound<<std::endl;
00133 #endif
00134 return milpBound;
00135 }
00136
00137
00139 void
00140 OaFeasibilityChecker::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00141 {
00142 roptions->SetRegisteringCategory("Feasibility checker using OA cuts", RegisteredOptions::BonminCategory);
00143 roptions->AddStringOption2("feas_check_cut_types", "Choose the type of cuts generated when an integer feasible solution is found",
00144 "outer-approx",
00145 "outer-approx", "Generate a set of Outer Approximations cuts.",
00146 "Benders", "Generate a single Benders cut.",
00147 "If it seems too much memory is used should try Benders to use less");
00148 roptions->setOptionExtraInfo("feas_check_cut_types", 19);
00149
00150
00151 roptions->AddStringOption3("feas_check_discard_policy", "How cuts from feasibility checker are discarded",
00152 "detect-cycles",
00153 "detect-cycles", "Detect if a cycle occurs and only in this case force not to discard.",
00154 "keep-all", "Force cuts from feasibility checker not to be discarded (memory hungry but sometimes better).",
00155 "treated-as-normal", "Cuts from memory checker can be discarded as any other cuts (code may cycle then)",
00156 "Normally to avoid cycle cuts from feasibility checker should not be discarded in the node where they are generated. "
00157 "However Cbc sometimes does it if no care is taken which can lead to an infinite loop in Bonmin (usually on simple problems). "
00158 "To avoid this one can instruct Cbc to never discard a cut but if we do that for all cuts it can lead to memory problems. "
00159 "The default policy here is to detect cycles and only then impose to Cbc to keep the cut. "
00160 "The two other alternative are to instruct Cbc to keep all cuts or to just ignore the problem and hope for the best");
00161 roptions->setOptionExtraInfo("feas_check_discard_policy", 19);
00162
00163 roptions->AddLowerBoundedIntegerOption("generate_benders_after_so_many_oa", "Specify that after so many oa cuts have been generated Benders cuts should be generated instead.",
00164 0, 5000,
00165 "It seems that sometimes generating too many oa cuts slows down the optimization compared to Benders due to the size of the LP. "
00166 "With this option we specify that after so many OA cuts have been generated we should switch to Benders cuts.");
00167 roptions->setOptionExtraInfo("generate_benders_after_so_many_oa", 19);
00168 }
00169
00170 }