/home/coin/SVN-release/OS-2.0.1/Bonmin/src/Algorithms/OaGenerators/BonOACutGenerator2.cpp

Go to the documentation of this file.
00001 // (C) Copyright Carnegie Mellon University 2005, 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 : 05/26/2005
00009 //#define OA_DEBUG
00010 
00011 #include "BonOACutGenerator2.hpp"
00012 #include "BonminConfig.h"
00013 
00014 #include "OsiClpSolverInterface.hpp"
00015 
00016 #include "CbcModel.hpp"
00017 #include "BonCbcLpStrategy.hpp"
00018 #ifdef COIN_HAS_CPX
00019 #include "OsiCpxSolverInterface.hpp"
00020 #endif
00021 #include "OsiAuxInfo.hpp"
00022 
00023 
00024 
00025 namespace Bonmin
00026 {
00027 
00029   OACutGenerator2::OACutGenerator2(BabSetupBase & b):
00030       OaDecompositionBase(b, true, false)
00031   {
00032     int ivalue;
00033     b.options()->GetEnumValue("milp_subsolver",ivalue,"bonmin.");
00034     if (ivalue <= 0) {//uses cbc
00035       //nothing to do?
00036     }
00037     else if (ivalue == 1) {
00038       int nodeS, nStrong, nTrust, mig, mir, probe, cover;
00039       b.options()->GetEnumValue("node_comparison",nodeS,"milp_sub.");
00040       b.options()->GetIntegerValue("number_strong_branch",nStrong,"milp_sub.");
00041       b.options()->GetIntegerValue("number_before_trust", nTrust,"milp_sub.");
00042       b.options()->GetIntegerValue("Gomory_cuts", mig,"milp_sub.");
00043       b.options()->GetIntegerValue("probing_cuts",probe,"milp_sub.");
00044       b.options()->GetIntegerValue("mir_cuts",mir,"milp_sub.");
00045       b.options()->GetIntegerValue("cover_cuts",cover,"milp_sub.");
00046       
00047       CbcStrategy * strategy =
00048         new CbcOaStrategy(mig, probe, mir, cover, nTrust,
00049             nStrong, nodeS, parameters_.cbcIntegerTolerance_, parameters_.subMilpLogLevel_);
00050       setStrategy(*strategy);
00051       delete strategy;
00052 
00053     }
00054     else if (ivalue == 2) {
00055 #ifdef COIN_HAS_CPX
00056       OsiCpxSolverInterface * cpxSolver = new OsiCpxSolverInterface;
00057       b.nonlinearSolver()->extractLinearRelaxation(*cpxSolver);
00058       assignLpInterface(cpxSolver);
00059 #else
00060       std::cerr << "You have set an option to use CPLEX as the milp\n"
00061       << "subsolver in oa decomposition. However, apparently\n"
00062       << "CPLEX is not configured to be used in bonmin.\n"
00063       << "See the manual for configuring CPLEX\n";
00064       throw -1;
00065 #endif
00066     }
00067 
00068     double oaTime;
00069     b.options()->GetNumericValue("oa_dec_time_limit",oaTime,"bonmin.");
00070     parameter().localSearchNodeLimit_ = 1000000;
00071     parameter().maxLocalSearch_ = 100000;
00072     parameter().maxLocalSearchPerNode_ = 10000;
00073     parameter().maxLocalSearchTime_ =
00074       Ipopt::Min(b.getDoubleParameter(BabSetupBase::MaxTime), oaTime);
00075   }
00076   OACutGenerator2::~OACutGenerator2()
00077   {}
00078 
00080   bool
00081   OACutGenerator2::doLocalSearch() const
00082   {
00083     return (nLocalSearch_<parameters_.maxLocalSearch_ &&
00084         parameters_.localSearchNodeLimit_ > 0 &&
00085         CoinCpuTime() - timeBegin_ < parameters_.maxLocalSearchTime_);
00086   }
00088   double
00089   OACutGenerator2::performOa(OsiCuts &cs,
00090       solverManip &nlpManip,
00091       solverManip &lpManip,
00092       SubMipSolver * &subMip,
00093       OsiBabSolver * babInfo,
00094       double & cutoff) const
00095   {
00096     double lastPeriodicLog= CoinCpuTime();
00097 
00098     //const int numcols = nlp_->getNumCols();
00099 
00100 
00101     bool isInteger = false;
00102 
00103     OsiSolverInterface * lp = lpManip.si();
00104     OsiBranchingInformation info(lp, false);
00105     bool milpOptimal = 1;
00106 
00107 
00108     double milpBound = -COIN_DBL_MAX;
00109     bool milpFeasible = 1;
00110     bool feasible = 1;
00111     if (subMip)//Perform a local search
00112     {
00113       subMip->performLocalSearch(cutoff, parameters_.subMilpLogLevel_,
00114           (parameters_.maxLocalSearchTime_ + timeBegin_ - CoinCpuTime()) /* time limit */,
00115           parameters_.localSearchNodeLimit_);
00116       milpBound = subMip->lowBound();
00117       milpOptimal = subMip->optimal();
00118 
00119       feasible = milpBound < cutoff;
00120       milpFeasible = feasible;
00121       isInteger = subMip->getLastSolution() != NULL;
00122       nLocalSearch_++;
00123 
00124       if (milpOptimal)
00125         handler_->message(SOLVED_LOCAL_SEARCH, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
00126       else
00127       {
00128         handler_->message(LOCAL_SEARCH_ABORT, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
00129       }
00130     }
00131     int numberPasses = 0;
00132 
00133 #ifdef OA_DEBUG
00134     bool foundSolution = 0;
00135 #endif
00136     double * nlpSol = NULL;
00137 
00138     while (isInteger && feasible ) {
00139       numberPasses++;
00140 
00141       //after a prescribed elapsed time give some information to user
00142       double time = CoinCpuTime();
00143       if (time - lastPeriodicLog > parameters_.logFrequency_) {
00144         double lb = (subMip == NULL) ?lp->getObjValue() : subMip->getLowerBound();
00145         handler_->message(PERIODIC_MSG,messages_)
00146         <<time - timeBegin_<<cutoff
00147         <<lb
00148         <<CoinMessageEol;
00149         lastPeriodicLog = CoinCpuTime();
00150       }
00151 
00152 
00153       //setup the nlp
00154       int numberCutsBefore = cs.sizeRowCuts();
00155 
00156       //Fix the variable which have to be fixed, after having saved the bounds
00157       const double * colsol = subMip == NULL ? lp->getColSolution():
00158           subMip->getLastSolution();
00159       info.solution_ = colsol;
00160       nlpManip.fixIntegers(info);
00161 
00162 
00163       if (solveNlp(babInfo, cutoff)) {
00164         //nlp solved and feasible
00165         // Update the cutoff
00166         cutoff = nlp_->getObjValue() *(1 - parameters_.cbcCutoffIncrement_);
00167         // Update the lp solver cutoff
00168         lp->setDblParam(OsiDualObjectiveLimit, cutoff);
00169       }
00170 
00171       nlpSol = const_cast<double *>(nlp_->getColSolution());
00172 
00173       // Get the cuts outer approximation at the current point
00174       const double * toCut = (parameter().addOnlyViolated_)?
00175           colsol:NULL;
00176       nlp_->getOuterApproximation(cs, nlpSol, 1, toCut,
00177                                   parameter().global_);
00178 
00179       int numberCuts = cs.sizeRowCuts() - numberCutsBefore;
00180       if (numberCuts > 0)
00181         lpManip.installCuts(cs, numberCuts);
00182 
00183       lp->resolve();
00184       double objvalue = lp->getObjValue();
00185       //milpBound = max(milpBound, lp->getObjValue());
00186       feasible = (lp->isProvenOptimal() &&
00187           !lp->isDualObjectiveLimitReached() && (objvalue<cutoff)) ;
00188       //if value of integers are unchanged then we have to get out
00189       bool changed = !feasible;//if lp is infeasible we don't have to check anything
00190       info.solution_ = lp->getColSolution();
00191       if (!changed)
00192         changed = nlpManip.isDifferentOnIntegers(lp->getColSolution());
00193       if (changed) {
00194 
00195         isInteger = lpManip.integerFeasible(info);
00196       }
00197       else {
00198         isInteger = 0;
00199         //        if(!fixed)//fathom on bounds
00200         milpBound = 1e200;
00201       }
00202 #ifdef OA_DEBUG
00203       printf("Obj value after cuts %g %d rows\n",lp->getObjValue(),
00204           numberCuts) ;
00205 #endif
00206       //check time
00207       if (CoinCpuTime() - timeBegin_ > parameters_.maxLocalSearchTime_)
00208         break;
00209       //do we perform a new local search ?
00210       if (milpOptimal && feasible && !isInteger &&
00211           nLocalSearch_ < parameters_.maxLocalSearch_ &&
00212           numberPasses < parameters_.maxLocalSearchPerNode_ &&
00213           parameters_.localSearchNodeLimit_ > 0) {
00214 
00216         if (subMip == NULL) subMip = new SubMipSolver(lp, parameters_.strategy());
00217 
00218         nLocalSearch_++;
00219 
00220         subMip->performLocalSearch(cutoff, parameters_.subMilpLogLevel_,
00221             parameters_.maxLocalSearchTime_ + timeBegin_ - CoinCpuTime(),
00222             parameters_.localSearchNodeLimit_);
00223 
00224         milpBound = subMip->lowBound();
00225 
00226         if (subMip->optimal())
00227           handler_->message(SOLVED_LOCAL_SEARCH, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
00228         else
00229           handler_->message(LOCAL_SEARCH_ABORT, messages_)<<subMip->nodeCount()<<subMip->iterationCount()<<CoinMessageEol;
00230 
00231 
00232         colsol = const_cast<double *> (subMip->getLastSolution());
00233         isInteger = colsol != 0;
00234 
00235         feasible =  (milpBound < cutoff);
00236 
00237         if (feasible && isInteger) {
00238           bool changed = false;
00239           changed = nlpManip.isDifferentOnIntegers(colsol);//If integer solution is the same as nlp
00240           //solution problem is solved
00241           if (!changed) {
00242             feasible = 0;
00243             milpBound = 1e50;
00244           }
00245           milpFeasible = feasible;
00246         }
00247         if (subMip->optimal())
00248           milpOptimal = 1;
00249         else {
00250           milpOptimal = 0;
00251         }
00252 
00253         if (milpBound < cutoff)
00254           handler_->message(UPDATE_LB, messages_)<<milpBound<<CoinCpuTime() - timeBegin_<<CoinMessageEol;
00255         else {
00256           milpBound = 1e50;
00257           feasible = 0;
00258           handler_->message(OASUCCESS, messages_)<<CoinCpuTime() - timeBegin_ <<CoinMessageEol;
00259         }
00260       }
00261       else if (subMip!=NULL) {
00262         delete subMip;
00263         subMip = NULL;
00264       }
00265     }
00266 
00267 #ifdef OA_DEBUG
00268     debug_.printEndOfProcedureDebugMessage(cs, foundSolution, cutoff, milpBound, isInteger, feasible, std::cout);
00269 #endif
00270     return milpBound;
00271   }
00272 
00274   void
00275   OACutGenerator2::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00276   {
00277     roptions->SetRegisteringCategory("Options for OA decomposition", RegisteredOptions::BonminCategory);
00278     roptions->AddLowerBoundedNumberOption("oa_dec_time_limit",
00279         "Specify the maximum number of seconds spent overall in OA decomposition iterations.",
00280         0.,0,30.,
00281         "");
00282 
00283     roptions->AddBoundedIntegerOption("oa_log_level",
00284         "specify OA iterations log level.",
00285         0,2,1,
00286         "Set the level of output of OA decomposition solver : "
00287         "0 - none, 1 - normal, 2 - verbose"
00288                                      );
00289 
00290     roptions->AddLowerBoundedNumberOption("oa_log_frequency",
00291         "display an update on lower and upper bounds in OA every n seconds",
00292         0.,1.,100.,
00293         "");
00294 
00295     roptions->SetRegisteringCategory("Options for MILP subsolver in OA decomposition", RegisteredOptions::BonminCategory);
00296     roptions->AddStringOption3("milp_subsolver",
00297         "Choose the subsolver to solve MILP sub-problems in OA decompositions.",
00298         "Cbc_D",
00299         "Cbc_D","Coin Branch and Cut with its default",
00300         "Cbc_Par", "Coin Branch and Cut with passed parameters",
00301         "Cplex","Ilog Cplex",
00302         " To use Cplex, a valid license is required and you should have compiled OsiCpx in COIN-OR  (see Osi documentation).");
00303     roptions->setOptionExtraInfo("milp_subsolver",5);
00304 
00305     roptions->AddBoundedIntegerOption("milp_log_level",
00306         "specify MILP subsolver log level.",
00307         0,3,0,
00308         "Set the level of output of the MILP subsolver in OA : "
00309         "0 - none, 1 - minimal, 2 - normal low, 3 - normal high"
00310                                      );
00311     roptions->setOptionExtraInfo("milp_log_level",5);
00312 
00313 
00314   }
00315 
00316 
00317 }/* End namespace Bonmin. */

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