00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "BonOaFeasChecker.hpp"
00012 #include "BonminConfig.h"
00013
00014 #include "OsiAuxInfo.hpp"
00015 #include "BonSolverHelp.hpp"
00016
00017 namespace Bonmin
00018 {
00019 static const char * txt_id = "check integer sol.";
00020
00022 OaFeasibilityChecker::OaFeasibilityChecker(BabSetupBase &b):
00023 OaDecompositionBase(b, false, true),
00024 cut_count_(0)
00025 {
00026 int ival;
00027 b.options()->GetEnumValue("feas_check_cut_types", ival, b.prefix());
00028 type_ = CutsTypes(ival);
00029 b.options()->GetEnumValue("feas_check_discard_policy", ival, b.prefix());
00030 pol_ = CutsPolicies(ival);
00031 b.options()->GetIntegerValue("generate_benders_after_so_many_oa", ival, b.prefix());
00032 maximum_oa_cuts_ = static_cast<unsigned int>(ival);
00033 }
00034 OaFeasibilityChecker ::~OaFeasibilityChecker ()
00035 {}
00036
00038 double
00039 OaFeasibilityChecker::performOa(OsiCuts & cs, solverManip &lpManip,
00040 SubMipSolver * &subMip, BabInfo * babInfo, double &cutoff,const CglTreeInfo & info) const
00041 {
00042 bool isInteger = true;
00043 bool feasible = 1;
00044
00045 OsiSolverInterface * lp = lpManip.si();
00046 OsiBranchingInformation branch_info(lp,false);
00047
00048 double milpBound = -COIN_DBL_MAX;
00049 int numberPasses = 0;
00050 double * nlpSol = NULL;
00051 int numberCutsBefore = cs.sizeRowCuts();
00052
00053 while (isInteger && feasible ) {
00054 numberPasses++;
00055
00056
00057
00058
00059 double * colsol = const_cast<double *>(lp->getColSolution());
00060 branch_info.solution_ = colsol;
00061 fixIntegers(*nlp_,branch_info, parameters_.cbcIntegerTolerance_,objects_, nObjects_);
00062
00063
00064
00065 nlp_->resolve(txt_id);
00066 if (post_nlp_solve(babInfo, cutoff)) {
00067
00068
00069 cutoff = nlp_->getObjValue() *(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 parameter().global_);
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("Options for 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-approximations",
00145 "outer-approximations", "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 (usualy 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 }