/home/coin/SVN-release/OS-2.1.0/Bonmin/src/Algorithms/Branching/BonLpBranchingSolver.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2006, 2007 International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #if defined(_MSC_VER)
00004 // Turn off compiler warning about long names
00005 #  pragma warning(disable:4786)
00006 #endif
00007 
00008 #include "BonLpBranchingSolver.hpp"
00009 #include "OsiClpSolverInterface.hpp"
00010 #include <vector>
00011 
00012 namespace Bonmin
00013 {
00014 
00015   LpBranchingSolver::LpBranchingSolver(BabSetupBase * b) :
00016       StrongBranchingSolver(b->nonlinearSolver()),
00017       lin_(NULL),
00018       warm_(NULL),
00019       ecp_(NULL)
00020   {
00021     SmartPtr<TNLPSolver> tnlp_solver =
00022        static_cast<TNLPSolver *> (b->nonlinearSolver()->solver());
00023     SmartPtr<OptionsList> options = tnlp_solver->options();
00024 
00025             options->GetIntegerValue("ecp_max_rounds_strong",
00026                                      maxCuttingPlaneIterations_,
00027                                      b->nonlinearSolver()->prefix());
00028             options->GetNumericValue("ecp_abs_tol_strong",
00029                                      abs_ecp_tol_,
00030                                      b->nonlinearSolver()->prefix());
00031             options->GetNumericValue("ecp_rel_tol_strong",
00032                                      rel_ecp_tol_,
00033                                      b->nonlinearSolver()->prefix());
00034             int dummy;
00035             options->GetEnumValue("lp_strong_warmstart_method", 
00036                                   dummy,
00037                                   b->nonlinearSolver()->prefix());
00038             warm_start_mode_ = (WarmStartMethod) dummy;
00039           }
00040 
00041   LpBranchingSolver::LpBranchingSolver(const LpBranchingSolver & rhs) :
00042       StrongBranchingSolver(rhs),
00043       lin_(NULL),
00044       warm_(NULL),
00045       ecp_(NULL),
00046       maxCuttingPlaneIterations_(rhs.maxCuttingPlaneIterations_),
00047       abs_ecp_tol_(rhs.abs_ecp_tol_),
00048       rel_ecp_tol_(rhs.rel_ecp_tol_),
00049       warm_start_mode_(rhs.warm_start_mode_)
00050   {}
00051 
00052   LpBranchingSolver &
00053   LpBranchingSolver::operator=(const LpBranchingSolver & rhs)
00054   {
00055     if (this != &rhs) {
00056       StrongBranchingSolver::operator=(rhs);
00057     }
00058     maxCuttingPlaneIterations_ = rhs.maxCuttingPlaneIterations_;
00059     abs_ecp_tol_ = rhs.abs_ecp_tol_;
00060     rel_ecp_tol_ = rhs.rel_ecp_tol_;
00061     warm_start_mode_ = rhs.warm_start_mode_;
00062     // I assume that no LP solver information is ever copied
00063     delete lin_;
00064     delete warm_;
00065     delete ecp_;
00066     lin_ = NULL;
00067     warm_ = NULL;
00068     ecp_ = NULL;
00069     return *this;
00070   }
00071 
00072   LpBranchingSolver::~LpBranchingSolver ()
00073   {
00074     delete lin_;
00075     delete warm_;
00076     delete ecp_;
00077   }
00078 
00079   void LpBranchingSolver::
00080   markHotStart(OsiTMINLPInterface* tminlp_interface)
00081   {
00082     lin_ = new OsiClpSolverInterface();
00083     tminlp_interface->extractLinearRelaxation(*lin_, tminlp_interface->getColSolution(),
00084                                               true);
00085     double cutoff = -DBL_MAX;
00086     tminlp_interface->getDblParam(OsiDualObjectiveLimit, cutoff);
00087     lin_->setDblParam(OsiDualObjectiveLimit, cutoff);
00088     //printf("Cutoff %g # ecp iteration %i\n",cutoff, maxCuttingPlaneIterations_);
00089     lin_->messageHandler()->setLogLevel(0);
00090     lin_->resolve();
00091     warm_ = lin_->getWarmStart();
00092     //if (maxCuttingPlaneIterations_)
00093     //  ecp_ = new EcpCuts(tminlp_interface, maxCuttingPlaneIterations_,
00094     //      abs_ecp_tol_, rel_ecp_tol_, -1.);
00095   }
00096 
00097   void LpBranchingSolver::
00098   unmarkHotStart(OsiTMINLPInterface* tminlp_interface)
00099   {
00100     // Free memory
00101     delete lin_;
00102     delete warm_;
00103     delete ecp_;
00104     lin_ = NULL;
00105     warm_ = NULL;
00106     ecp_ = NULL;
00107   }
00108 
00109   TNLPSolver::ReturnStatus LpBranchingSolver::
00110   solveFromHotStart(OsiTMINLPInterface* tminlp_interface)
00111   {
00112     TNLPSolver::ReturnStatus retstatus = TNLPSolver::solvedOptimal;
00113 
00114     // updated the bounds of the linear solver
00115     std::vector<int> diff_low_bnd_index;
00116     std::vector<double> diff_low_bnd_value;
00117     std::vector<int> diff_up_bnd_index;
00118     std::vector<double> diff_up_bnd_value;
00119 
00120 #if 0
00121     // deleteme
00122     for (int i=0; i<tminlp_interface->getNumCols(); i++) {
00123       printf("%3d ol = %e nl = %e   ou = %e nu = %e\n",i,tminlp_interface->getColLower()[i],lin_->getColLower()[i],tminlp_interface->getColUpper()[i],lin_->getColUpper()[i]);
00124     }
00125 #endif
00126     // Get the bounds.  We assume that the bounds in the linear solver
00127     // are always the original ones
00128     const int numCols = tminlp_interface->getNumCols();
00129     const double* colLow_orig = lin_->getColLower();
00130     const double* colUp_orig = lin_->getColUpper();
00131     const double* colLow = tminlp_interface->getColLower();
00132     const double* colUp = tminlp_interface->getColUpper();
00133 
00134     OsiSolverInterface * lin = lin_;
00135     // eventualy clone lin_
00136     if(warm_start_mode_ == Clone){
00137       lin = lin_->clone();
00138 //      std::cout<<"Cloning it"<<std::endl;
00139     }
00140     // Set the bounds on the LP solver according to the changes in
00141     // tminlp_interface
00142     for (int i=0; i<numCols; i++) {
00143       const double& lo = colLow[i];
00144       if (colLow_orig[i] < lo) {
00145         if(warm_start_mode_ == Basis){
00146           diff_low_bnd_value.push_back(colLow_orig[i]);
00147           diff_low_bnd_index.push_back(i);
00148         }
00149         lin->setColLower(i,lo);
00150       }
00151       const double& up = colUp[i];
00152       if (colUp_orig[i] > up) {
00153         if(warm_start_mode_ == Basis){
00154           diff_up_bnd_index.push_back(i);
00155           diff_up_bnd_value.push_back(colUp_orig[i]);
00156         }
00157         lin->setColUpper(i,lo);
00158       }
00159     }
00160 
00161 #if 0
00162     // deleteme
00163     for (int i=0; i<numCols; i++) {
00164       printf("%3d ol = %e nl = %e   ou = %e nu = %e\n",i,tminlp_interface->getColLower()[i],lin_->getColLower()[i],tminlp_interface->getColUpper()[i],lin_->getColUpper()[i]);
00165     }
00166 #endif
00167     if(warm_start_mode_ == Basis){
00168       lin->setWarmStart(warm_);
00169     }
00170 
00171     lin->resolve();
00172 
00173     double obj = lin->getObjValue();
00174     bool go_on = true;
00175     if (lin->isProvenPrimalInfeasible() || 
00176         lin->isDualObjectiveLimitReached()) {
00177       retstatus = TNLPSolver::provenInfeasible;
00178       go_on = false;
00179     }
00180     else if (lin->isIterationLimitReached()) {
00181       retstatus = TNLPSolver::iterationLimit;
00182       go_on = false;
00183     }
00184     else {
00185       if (maxCuttingPlaneIterations_ > 0 && go_on) {
00186         double violation;
00187         obj = ecp_->doEcpRounds(*lin, true, &violation);
00188         if (obj == COIN_DBL_MAX) {
00189           retstatus = TNLPSolver::provenInfeasible;
00190         }
00191         else if (violation <= 1e-8) {
00192           retstatus = TNLPSolver::solvedOptimal;
00193         }
00194       }
00195     }
00196     tminlp_interface->problem()->set_obj_value(obj);
00197     tminlp_interface->problem()->Set_x_sol(numCols, lin_->getColSolution());
00198 
00199     //restore the original bounds
00200     if(warm_start_mode_ == Basis){
00201       for (unsigned int i = 0; i < diff_low_bnd_index.size(); i++) {
00202         lin_->setColLower(diff_low_bnd_index[i],diff_low_bnd_value[i]);
00203       }
00204       for (unsigned int i = 0; i < diff_up_bnd_index.size(); i++) {
00205         lin_->setColUpper(diff_up_bnd_index[i],diff_up_bnd_value[i]);
00206       }
00207     }
00208     else {
00209       delete lin;
00210     }
00211     return retstatus;
00212   }
00213 
00214   void
00215   LpBranchingSolver::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
00216   {
00217     roptions->SetRegisteringCategory("Bonmin ecp based strong branching",RegisteredOptions::UndocumentedCategory);
00218     roptions->AddLowerBoundedIntegerOption
00219     ("ecp_max_rounds_strong",
00220      "Set the maximal number of rounds of ECP cuts in strong branching.",
00221      0,0,
00222      "");
00223     roptions->setOptionExtraInfo("ecp_max_rounds_strong",63);
00224     roptions->AddLowerBoundedNumberOption
00225     ("ecp_abs_tol_strong",
00226      "Set the absolute termination tolerance for ECP rounds in strong branching.",
00227      0,false,1e-6,
00228      "");
00229     roptions->setOptionExtraInfo("ecp_abs_tol_strong",63);
00230     roptions->AddLowerBoundedNumberOption
00231     ("ecp_rel_tol_strong",
00232      "Set the relative termination tolerance for ECP rounds in strong branching.",
00233      0,false,1e-1,
00234      "");
00235     roptions->setOptionExtraInfo("ecp_rel_tol_strong",63);
00236     roptions->AddStringOption2
00237     ("lp_strong_warmstart_method",
00238      "Choose method to use for warm starting lp in strong branching",
00239      "Basis",
00240      "Basis", "Use optimal basis of node",
00241      "Clone", "Clone optimal problem of node",
00242      "(Advanced stuff)");
00243     roptions->setOptionExtraInfo("lp_strong_warmstart_method",63);
00244   }
00245 
00246 }

Generated on Tue Mar 30 03:04:33 2010 by  doxygen 1.4.7