/home/coin/SVN-release/OS-2.4.0/Bonmin/src/Algorithms/OaGenerators/BonOaFeasChecker.cpp

Go to the documentation of this file.
00001 // (C) Copyright International Business Machines 2006-2011
00002 // All Rights Reserved.
00003 // This code is published under the Common Public License.
00004 //
00005 // Authors :
00006 // P. Bonami, Carnegie Mellon University
00007 //
00008 // Date : 12/26/2006
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     //int numcols = lp->getNumCols();
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       //setup the nlp
00056 
00057       //Fix the variable which have to be fixed, after having saved the bounds
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       //Now solve the NLP get the cuts, and intall them in the local LP
00064       nlp_->resolve(txt_id);
00065       if (post_nlp_solve(babInfo, cutoff)) {
00066         //nlp solved and feasible
00067         // Update the cutoff
00068         cutoff = nlp_->getObjValue() *(1 - parameters_.cbcCutoffIncrement_);
00069         // Update the lp solver cutoff
00070         lp->setDblParam(OsiDualObjectiveLimit, cutoff);
00071       }
00072       // Get the cuts outer approximation at the current point
00073 
00074       nlpSol = const_cast<double *>(nlp_->getColSolution());
00075 
00076       const double * toCut = (parameter().addOnlyViolated_)?
00077                              colsol:NULL;
00078       if(cut_count_ <= maximum_oa_cuts_ && type_ == OA)
00079         nlp_->getOuterApproximation(cs, nlpSol, 1, toCut,
00080                                     true);
00081       else {//if (type_ == Benders)
00082         nlp_->getBendersCut(cs, parameter().global_);
00083       }
00084       if(pol_ == DetectCycles)
00085         nlp_->getBendersCut(savedCuts_, parameter().global_);
00086 
00087       int numberCuts = cs.sizeRowCuts() - numberCutsBefore;
00088       cut_count_ += numberCuts;
00089       if (numberCuts > 0)
00090         installCuts(*lp, cs, numberCuts);
00091 
00092       lp->resolve();
00093       double objvalue = lp->getObjValue();
00094       //milpBound = max(milpBound, lp->getObjValue());
00095       feasible = (lp->isProvenOptimal() &&
00096           !lp->isDualObjectiveLimitReached() && (objvalue<cutoff)) ;
00097       //if value of integers are unchanged then we have to get out
00098       bool changed = true;//if lp is infeasible we don't have to check anything
00099       isInteger = 0;
00100       //          if(!fixed)//fathom on bounds
00101       //           milpBound = 1e200;
00102       if (feasible) {
00103         changed = isDifferentOnIntegers(*nlp_, objects_, nObjects_,
00104                                         0.1,
00105                                         nlp_->getColSolution(), lp->getColSolution());
00106       }
00107       if (changed) {
00108        branch_info.solution_ = lp->getColSolution();
00109         isInteger = integerFeasible(*lp,branch_info, parameters_.cbcIntegerTolerance_,
00110                                      objects_, nObjects_);
00111       }
00112       else {
00113         isInteger = 0;
00114         //        if(!fixed)//fathom on bounds
00115          milpBound = 1e200;
00116       }
00117 #ifdef OA_DEBUG
00118       printf("Obj value after cuts %g, %d rows\n",lp->getObjValue(),
00119           numberCuts) ;
00120 #endif
00121     }
00122     int num_cuts_now = cs.sizeRowCuts();
00123     if(pol_ == KeepAll){
00124       for(int i = numberCutsBefore ; i < num_cuts_now ; i++){
00125         cs.rowCut(i).setEffectiveness(99.9e99);
00126       }
00127     }
00128 
00129 #ifdef OA_DEBUG
00130     debug_.printEndOfProcedureDebugMessage(cs, true, cutoff, milpBound, isInteger, feasible, std::cout);
00131     std::cout<<"milpBound found: "<<milpBound<<std::endl;
00132 #endif
00133     return milpBound;
00134   }
00135 
00136 
00138   void
00139   OaFeasibilityChecker::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00140   {
00141     roptions->SetRegisteringCategory("Options for feasibility checker using OA cuts", RegisteredOptions::BonminCategory);
00142     roptions->AddStringOption2("feas_check_cut_types", "Choose the type of cuts generated when an integer feasible solution is found",
00143                                "outer-approx",
00144                                "outer-approx", "Generate a set of Outer Approximations cuts.",
00145                                "Benders", "Generate a single Benders cut.",
00146                                "If it seems too much memory is used should try Benders to use less");
00147     roptions->setOptionExtraInfo("feas_check_cut_types", 19);
00148     
00149 
00150     roptions->AddStringOption3("feas_check_discard_policy", "How cuts from feasibility checker are discarded",
00151                                "detect-cycles",
00152                                "detect-cycles", "Detect if a cycle occurs and only in this case force not to discard.",
00153                                "keep-all", "Force cuts from feasibility checker not to be discarded (memory hungry but sometimes better).",
00154                                "treated-as-normal", "Cuts from memory checker can be discarded as any other cuts (code may cycle then)",
00155                                "Normally to avoid cycle cuts from feasibility checker should not be discarded in the node where they are generated. "
00156                                "However Cbc sometimes does it if no care is taken which can lead to an infinite loop in Bonmin (usualy on simple problems). "
00157                                "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. "
00158                                "The default policy here is to detect cycles and only then impose to Cbc to keep the cut. "
00159                                "The two other alternative are to instruct Cbc to keep all cuts or to just ignore the problem and hope for the best");
00160     roptions->setOptionExtraInfo("feas_check_discard_policy", 19);
00161 
00162     roptions->AddLowerBoundedIntegerOption("generate_benders_after_so_many_oa", "Specify that after so many oa cuts have been generated Benders cuts should be generated instead.",
00163                                            0, 5000,
00164                                            "It seems that sometimes generating too many oa cuts slows down the optimization compared to Benders due to the size of the LP. "
00165                                            "With this option we specify that after so many OA cuts have been generated we should switch to Benders cuts.");
00166     roptions->setOptionExtraInfo("generate_benders_after_so_many_oa", 19);
00167   }
00168 
00169 }/* End namespace Bonmin. */

Generated on Thu Sep 22 03:05:53 2011 by  doxygen 1.4.7