00001
00002
00003 #if defined(_MSC_VER)
00004
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
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
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
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
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
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
00119
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
00128 if(warm_start_mode_ == Clone){
00129 lin = lin_->clone();
00130
00131 }
00132
00133
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
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
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 }