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

Go to the documentation of this file.
00001 // (C) Copyright International Business Machines 2006
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 //#define OA_DEBUG
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     //int numcols = lp->getNumCols();
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       //setup the nlp
00057 
00058       //Fix the variable which have to be fixed, after having saved the bounds
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       //Now solve the NLP get the cuts, and intall them in the local LP
00065       nlp_->resolve(txt_id);
00066       if (post_nlp_solve(babInfo, cutoff)) {
00067         //nlp solved and feasible
00068         // Update the cutoff
00069         cutoff = nlp_->getObjValue() *(1 - parameters_.cbcCutoffIncrement_);
00070         // Update the lp solver cutoff
00071         lp->setDblParam(OsiDualObjectiveLimit, cutoff);
00072       }
00073       // Get the cuts outer approximation at the current point
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 {//if (type_ == Benders)
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       //milpBound = max(milpBound, lp->getObjValue());
00096       feasible = (lp->isProvenOptimal() &&
00097           !lp->isDualObjectiveLimitReached() && (objvalue<cutoff)) ;
00098       //if value of integers are unchanged then we have to get out
00099       bool changed = true;//if lp is infeasible we don't have to check anything
00100       isInteger = 0;
00101       //          if(!fixed)//fathom on bounds
00102       //           milpBound = 1e200;
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         //        if(!fixed)//fathom on bounds
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 }/* End namespace Bonmin. */

Generated on Thu Aug 5 03:02:54 2010 by  doxygen 1.4.7