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

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