00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include "BonSubMipSolver.hpp"
00013 #include "BonminConfig.h"
00014 #include "CbcModel.hpp"
00015 #include "CbcStrategy.hpp"
00016 #include "OsiAuxInfo.hpp"
00017 #include "OsiClpSolverInterface.hpp"
00018
00019 #include <climits>
00020 #ifdef COIN_HAS_CPX
00021 #include "OsiCpxSolverInterface.hpp"
00022 #include "cplex.h"
00023 void throw_error(const std::string &s, const std::string &f, const std::string &func){
00024 throw CoinError(s,f,func);
00025 }
00026 #define CHECK_CPX_STAT(a,b) if(b) throw_error("Error in CPLEX call",__FILE__,a);
00027
00028 #endif
00029
00030 #include "BonRegisteredOptions.hpp"
00031 #include "BonBabSetupBase.hpp"
00032 #include "BonCbcLpStrategy.hpp"
00033
00034
00035 namespace Bonmin {
00037 SubMipSolver::SubMipSolver(BabSetupBase &b, const std::string &prefix):
00038 clp_(NULL),
00039 cpx_(NULL),
00040 lowBound_(-DBL_MAX),
00041 optimal_(false),
00042 integerSolution_(NULL),
00043 strategy_(NULL),
00044 ownClp_(false)
00045 {
00046 int ivalue;
00047 b.options()->GetEnumValue("milp_solver",ivalue,prefix);
00048 if (ivalue <= 0) {
00049 strategy_ = new CbcStrategyDefault;
00050 clp_ = new OsiClpSolverInterface;
00051 ownClp_ = true;
00052 }
00053 else if (ivalue == 1) {
00054 CbcStrategyChooseCuts strategy(b, prefix);
00055 strategy_ = new CbcStrategyChooseCuts(b, prefix);
00056 clp_ = new OsiClpSolverInterface;
00057 ownClp_ = true;
00058 }
00059 else if (ivalue == 2) {
00060 #ifdef COIN_HAS_CPX
00061 OsiCpxSolverInterface * cpxSolver = new OsiCpxSolverInterface;
00062 #if 1
00063 b.options()->GetIntegerValue("number_cpx_threads",ivalue,prefix);
00064 CPXsetintparam(cpxSolver->getEnvironmentPtr(), CPX_PARAM_THREADS, ivalue);
00065 b.options()->GetIntegerValue("cpx_parallel_strategy",ivalue,prefix);
00066 CPXsetintparam(cpxSolver->getEnvironmentPtr(), CPX_PARAM_PARALLELMODE, ivalue);
00067 #endif
00068 cpx_ = cpxSolver;
00069 #else
00070 std::cerr << "You have set an option to use CPLEX as the milp\n"
00071 << "subsolver in oa decomposition. However, apparently\n"
00072 << "CPLEX is not configured to be used in bonmin.\n"
00073 << "See the manual for configuring CPLEX\n";
00074 throw -1;
00075 #endif
00076 }
00077
00078 b.options()->GetEnumValue("milp_strategy",ivalue,prefix);
00079 if(ivalue == 0){
00080 milp_strat_ = FindGoodSolution;
00081 }
00082 else {
00083 milp_strat_ = GetOptimum;
00084 }
00085
00086 b.options()->GetNumericValue("allowable_fraction_gap", gap_tol_, prefix);
00087
00088
00089 }
00090 SubMipSolver::SubMipSolver(const SubMipSolver ©):
00091 clp_(NULL),
00092 cpx_(NULL),
00093 lowBound_(-DBL_MAX),
00094 optimal_(false),
00095 integerSolution_(NULL),
00096 strategy_(NULL),
00097 milp_strat_(copy.milp_strat_),
00098 gap_tol_(copy.gap_tol_),
00099 ownClp_(copy.ownClp_)
00100 {
00101 #ifdef COIN_HAS_CPX
00102 if(copy.cpx_ != NULL){
00103 cpx_ = new OsiCpxSolverInterface(*copy.cpx_);
00104 int ival;
00105 CPXgetintparam(copy.cpx_->getEnvironmentPtr(), CPX_PARAM_THREADS, &ival);
00106 CPXsetintparam(cpx_->getEnvironmentPtr(), CPX_PARAM_THREADS, ival);
00107 CPXgetintparam(copy.cpx_->getEnvironmentPtr(), CPX_PARAM_PARALLELMODE, &ival);
00108 CPXsetintparam(cpx_->getEnvironmentPtr(), CPX_PARAM_PARALLELMODE, ival);
00109 }
00110 #endif
00111 if(copy.clp_ != NULL){
00112 if(ownClp_) clp_ = new OsiClpSolverInterface(*copy.clp_);
00113 else clp_ = copy.clp_;
00114 }
00115 if(copy.strategy_){
00116 strategy_ = dynamic_cast<CbcStrategyDefault *>(copy.strategy_->clone());
00117 assert(strategy_);
00118 }
00119 }
00120 SubMipSolver::~SubMipSolver()
00121 {
00122 if (strategy_) delete strategy_;
00123 if (integerSolution_) delete [] integerSolution_;
00124 #ifdef COIN_HAS_CPX
00125 if(cpx_) delete cpx_;
00126 #endif
00127 if(ownClp_) delete clp_;
00128 }
00129
00131 void
00132 SubMipSolver::setLpSolver(OsiSolverInterface * lp)
00133 {
00134 #ifdef COIN_HAS_CPX
00135 if(cpx_){
00136 clp_ = NULL;
00137 cpx_->loadProblem(*lp->getMatrixByCol(), lp->getColLower(), lp->getColUpper(), lp->getObjCoefficients(), lp->getRowLower(), lp->getRowUpper());
00138 int ncols = lp->getNumCols();
00139 for(int i = 0 ; i < ncols ; i++){
00140 if(lp->isInteger(i) || lp->isBinary(i))
00141 cpx_->setInteger(i);
00142 else
00143 cpx_->setContinuous(i);
00144 }
00145 }
00146 else {
00147 #endif
00148 if(ownClp_) delete clp_;
00149 ownClp_ = false;
00150 clp_ = (lp == NULL) ? NULL :
00151 dynamic_cast<OsiClpSolverInterface *>(lp);
00152 assert(clp_);
00153 #ifdef COIN_HAS_CPX
00154 }
00155 #endif
00156 lowBound_ = -COIN_DBL_MAX;
00157 optimal_ = false;
00158 if (integerSolution_) {
00159 delete [] integerSolution_;
00160 integerSolution_ = NULL;
00161 }
00162 }
00163
00164 OsiSolverInterface *
00165 SubMipSolver::solver(){
00166 if(clp_ != NULL)
00167 return clp_;
00168 else
00169 #ifdef COIN_HAS_CPX
00170 return cpx_;
00171 #else
00172 return NULL;
00173 #endif
00174 }
00175
00176 void
00177 SubMipSolver::find_good_sol(double cutoff, int loglevel, double max_time){
00178
00179 if(clp_){
00180 CbcStrategyDefault * strat_default = NULL;
00181 if (!strategy_){
00182 strat_default = new CbcStrategyDefault(1,5,5, loglevel);
00183 strat_default->setupPreProcessing();
00184 strategy_ = strat_default;
00185 }
00186 OsiBabSolver empty;
00187 CbcModel cbc(*clp_);
00188 cbc.solver()->setAuxiliaryInfo(&empty);
00189
00190
00191 strcpy(cbc.messagesPointer()->source_,"OCbc");
00192
00193 cbc.setLogLevel(loglevel);
00194 cbc.solver()->messageHandler()->setLogLevel(0);
00195 clp_->resolve();
00196 cbc.setStrategy(*strategy_);
00197 cbc.setLogLevel(loglevel);
00198 cbc.solver()->messageHandler()->setLogLevel(0);
00199 cbc.setMaximumSeconds(max_time);
00200 cbc.setMaximumSolutions(1);
00201 cbc.setCutoff(cutoff);
00202
00203
00204 cbc.branchAndBound();
00205 lowBound_ = cbc.getBestPossibleObjValue();
00206
00207 if (cbc.isProvenOptimal() || cbc.isProvenInfeasible())
00208 optimal_ = true;
00209 else optimal_ = false;
00210
00211 if (cbc.getSolutionCount()) {
00212 if (!integerSolution_)
00213 integerSolution_ = new double[clp_->getNumCols()];
00214 CoinCopyN(cbc.bestSolution(), clp_->getNumCols(), integerSolution_);
00215 }
00216 else if (integerSolution_) {
00217 delete [] integerSolution_;
00218 integerSolution_ = NULL;
00219 }
00220 nodeCount_ = cbc.getNodeCount();
00221 iterationCount_ = cbc.getIterationCount();
00222
00223 if(strat_default != NULL){
00224 delete strat_default;
00225 strategy_ = NULL;
00226 }
00227 }
00228 else if (cpx_){
00229 #ifndef COIN_HAS_CPX
00230 throw CoinError("Unsuported solver, for local searches you should use clp or cplex",
00231 "performLocalSearch",
00232 "OaDecompositionBase::SubMipSolver");
00233 #else
00234 cpx_->messageHandler()->setLogLevel(loglevel);
00235 cpx_->switchToMIP();
00236 CPXENVptr env = cpx_->getEnvironmentPtr();
00237 CPXLPptr cpxlp = cpx_->getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL);
00238 CPXsetdblparam(env, CPX_PARAM_TILIM, max_time);
00239 CPXsetdblparam(env, CPX_PARAM_EPINT, 1e-08);
00240 CPXsetdblparam(env, CPX_PARAM_CUTUP, cutoff);
00241 CPXsetdblparam(env, CPX_PARAM_EPGAP, gap_tol_);
00242
00243 #if 0
00244 CPXsetintparam(env, CPX_PARAM_THREADS, 16);
00245 CPXsetintparam(env, CPX_PARAM_PARALLELMODE, -1);
00246 #endif
00247
00248 CPXsetintparam(env,CPX_PARAM_INTSOLLIM, 10000);
00249 CPXsetintparam(env,CPX_PARAM_NODELIM, 1000000);
00250
00251 nodeCount_ = 0;
00252 iterationCount_ = 0;
00253 int status = CPXmipopt(env,cpxlp);
00254 CHECK_CPX_STAT("mipopt",status)
00255
00256
00257 status = CPXgetbestobjval(env, cpxlp, &lowBound_);
00258 CHECK_CPX_STAT("bestobjvalue",status)
00259
00260 int stat = CPXgetstat( env, cpxlp);
00261 optimal_ = (stat == CPXMIP_INFEASIBLE) || (stat == CPXMIP_OPTIMAL) || (stat == CPXMIP_OPTIMAL_TOL);
00262 nodeCount_ = CPXgetnodecnt(env , cpxlp);
00263 iterationCount_ = CPXgetmipitcnt(env , cpxlp);
00264
00265 if(stat == CPXMIP_NODE_LIM_INFEAS){
00266 CPXsetintparam(env, CPX_PARAM_INTSOLLIM, 1);
00267 CPXsetintparam(env,CPX_PARAM_NODELIM, 2100000000);
00268 status = CPXmipopt(env,cpxlp);
00269 CHECK_CPX_STAT("mipopt",status)
00270
00271 status = CPXgetstat( env, cpxlp);
00272 optimal_ = (stat == CPXMIP_INFEASIBLE) || (stat == CPXMIP_OPTIMAL) || (stat == CPXMIP_OPTIMAL_TOL);
00273 nodeCount_ = CPXgetnodecnt(env , cpxlp);
00274 iterationCount_ = CPXgetmipitcnt(env , cpxlp);
00275 }
00276 bool infeasible = (stat == CPXMIP_INFEASIBLE) || (stat == CPXMIP_ABORT_INFEAS) || (stat == CPXMIP_TIME_LIM_INFEAS)
00277 || (stat == CPXMIP_NODE_LIM_INFEAS) || (stat == CPXMIP_FAIL_INFEAS)
00278 || (stat == CPXMIP_MEM_LIM_INFEAS) || (stat == CPXMIP_INForUNBD);
00279
00280
00281 if(!infeasible){
00282 nodeCount_ += CPXgetnodecnt(env, cpxlp);
00283
00284 if(!integerSolution_){
00285 integerSolution_ = new double[cpx_->getNumCols()];
00286 }
00287 CPXgetmipx(env, cpxlp, integerSolution_, 0, cpx_->getNumCols() -1);
00288 CHECK_CPX_STAT("getmipx",status)
00289 }
00290 else {
00291 if (integerSolution_) {
00292 delete [] integerSolution_;
00293 integerSolution_ = NULL;
00294 }
00295 }
00296 cpx_->switchToLP();
00297 #endif
00298 }
00299 else {
00300 throw CoinError("Unsuported solver, for local searches you should use clp or cplex",
00301 "performLocalSearch",
00302 "OaDecompositionBase::SubMipSolver");
00303 }
00304 }
00305
00306 void
00307 SubMipSolver::optimize(double cutoff, int loglevel, double maxTime)
00308 {
00309 if (clp_) {
00310 assert(strategy_);
00311 CbcStrategyDefault * strat_default = dynamic_cast<CbcStrategyDefault *>(strategy_->clone());
00312 assert(strat_default);
00313 strat_default->setupPreProcessing();
00314
00315 OsiBabSolver empty;
00316 CbcModel cbc(*clp_);
00317 cbc.solver()->setAuxiliaryInfo(&empty);
00318
00319
00320 strcpy(cbc.messagesPointer()->source_,"OCbc");
00321
00322 cbc.setLogLevel(loglevel);
00323 cbc.solver()->messageHandler()->setLogLevel(0);
00324 clp_->resolve();
00325 cbc.setStrategy(*strategy_);
00326 cbc.setLogLevel(loglevel);
00327 cbc.solver()->messageHandler()->setLogLevel(0);
00328 cbc.setMaximumSeconds(maxTime);
00329 cbc.setCutoff(cutoff);
00330 cbc.setDblParam( CbcModel::CbcAllowableFractionGap, gap_tol_);
00331
00332
00333 cbc.branchAndBound();
00334 lowBound_ = cbc.getBestPossibleObjValue();
00335
00336 if (cbc.isProvenOptimal() || cbc.isProvenInfeasible())
00337 optimal_ = true;
00338 else optimal_ = false;
00339
00340 if (cbc.getSolutionCount()) {
00341 if (!integerSolution_)
00342 integerSolution_ = new double[clp_->getNumCols()];
00343 CoinCopyN(cbc.bestSolution(), clp_->getNumCols(), integerSolution_);
00344 }
00345 else if (integerSolution_) {
00346 delete [] integerSolution_;
00347 integerSolution_ = NULL;
00348 }
00349 nodeCount_ = cbc.getNodeCount();
00350 iterationCount_ = cbc.getIterationCount();
00351 delete strat_default;
00352 }
00353 else
00354 #ifdef COIN_HAS_CPX
00355 if (cpx_) {
00356 cpx_->switchToMIP();
00357 CPXENVptr env = cpx_->getEnvironmentPtr();
00358 CPXLPptr cpxlp = cpx_->getLpPtr(OsiCpxSolverInterface::KEEPCACHED_ALL);
00359
00360 CPXsetdblparam(env, CPX_PARAM_TILIM, maxTime);
00361 CPXsetdblparam(env, CPX_PARAM_CUTUP, cutoff);
00362 CPXsetdblparam(env, CPX_PARAM_EPGAP, gap_tol_);
00363 cpx_->messageHandler()->setLogLevel(loglevel);
00364 #if 0
00365 CPXsetintparam(env, CPX_PARAM_THREADS, 16);
00366 CPXsetintparam(env, CPX_PARAM_PARALLELMODE, -1);
00367 #endif
00368 int status = CPXmipopt(env,cpxlp);
00369 CHECK_CPX_STAT("mipopt",status)
00370
00371 int stat = CPXgetstat( env, cpxlp);
00372 bool infeasible = (stat == CPXMIP_INFEASIBLE) || (stat == CPXMIP_ABORT_INFEAS) || (stat == CPXMIP_TIME_LIM_INFEAS) || (stat == CPXMIP_NODE_LIM_INFEAS) || (stat == CPXMIP_FAIL_INFEAS)
00373 || (stat == CPXMIP_MEM_LIM_INFEAS) || (stat == CPXMIP_INForUNBD);
00374 optimal_ = (stat == CPXMIP_INFEASIBLE) || (stat == CPXMIP_OPTIMAL) || (stat == CPXMIP_OPTIMAL_TOL);
00375 nodeCount_ = CPXgetnodecnt(env , cpxlp);
00376 iterationCount_ = CPXgetmipitcnt(env , cpxlp);
00377 status = CPXgetbestobjval(env, cpxlp, &lowBound_);
00378 CHECK_CPX_STAT("getbestobjval",status)
00379
00380 if(!infeasible){
00381 if(!integerSolution_){
00382 integerSolution_ = new double[cpx_->getNumCols()];
00383 }
00384 CPXgetmipx(env, cpxlp, integerSolution_, 0, cpx_->getNumCols() -1);
00385 CHECK_CPX_STAT("getmipx",status)
00386 }
00387 else {
00388 if (integerSolution_) {
00389 delete [] integerSolution_;
00390 integerSolution_ = NULL;
00391 }
00392 }
00393 cpx_->switchToLP();
00394 }
00395 else {
00396 #else
00397 {
00398 #endif
00399 throw CoinError("Unsuported solver, for local searches you should use clp or cplex",
00400 "performLocalSearch",
00401 "OaDecompositionBase::SubMipSolver");
00402 }
00403 }
00404
00406 void
00407 SubMipSolver::setStrategy(CbcStrategyDefault * strategy)
00408 {
00409 if (strategy_) delete strategy_;
00410 strategy_ = dynamic_cast<CbcStrategyDefault *>(strategy->clone());
00411 assert(strategy_);
00412 }
00413
00415 void
00416 SubMipSolver::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00417 {
00418 roptions->SetRegisteringCategory("Options for MILP solver", RegisteredOptions::BonminCategory);
00419 roptions->AddStringOption3("milp_solver",
00420 "Choose the subsolver to solve MILP sub-problems in OA decompositions.",
00421 "Cbc_D",
00422 "Cbc_D","Coin Branch and Cut with its default",
00423 "Cbc_Par", "Coin Branch and Cut with passed parameters",
00424 "Cplex","Ilog Cplex",
00425 " To use Cplex, a valid license is required and you should have compiled OsiCpx in COIN-OR (see Osi documentation).");
00426 roptions->setOptionExtraInfo("milp_solver",64);
00427
00428 roptions->AddBoundedIntegerOption("milp_log_level",
00429 "specify MILP solver log level.",
00430 0,4,0,
00431 "Set the level of output of the MILP subsolver in OA : "
00432 "0 - none, 1 - minimal, 2 - normal low, 3 - normal high"
00433 );
00434 roptions->setOptionExtraInfo("milp_log_level",64);
00435
00436 roptions->AddBoundedIntegerOption("cpx_parallel_strategy",
00437 "Strategy of parallel search mode in CPLEX.",
00438 -1, 1, 0,
00439 "-1 = opportunistic, 0 = automatic, 1 = deterministic (refer to CPLEX documentation)"
00440 );
00441 roptions->setOptionExtraInfo("cpx_parallel_strategy",64);
00442
00443 roptions->AddLowerBoundedIntegerOption("number_cpx_threads",
00444 "Set number of threads to use with cplex.",
00445 0, 0,
00446 "(refer to CPLEX documentation)"
00447 );
00448 roptions->setOptionExtraInfo("number_cpx_threads",64);
00449
00450
00451 roptions->AddStringOption2("milp_strategy",
00452 "Choose a strategy for MILPs.",
00453 "find_good_sol",
00454 "find_good_sol","Stop sub milps when a solution improving the incumbent is found",
00455 "solve_to_optimality", "Solve MILPs to optimality",
00456 "");
00457 roptions->setOptionExtraInfo("milp_strategy",64);
00458
00459 }
00460 }