1 // Copyright (C) 2006, 2007 International Business Machines
2 // Corporation and others.  All Rights Reserved.
3 
4 #include "CoinPragma.hpp"
5 #include "BonLpBranchingSolver.hpp"
6 #include "OsiClpSolverInterface.hpp"
7 #include <vector>
8 
9 namespace Bonmin
10 {
11 
LpBranchingSolver(BabSetupBase * b)12   LpBranchingSolver::LpBranchingSolver(BabSetupBase * b) :
13       StrongBranchingSolver(b->nonlinearSolver()),
14       lin_(NULL),
15       warm_(NULL),
16       ecp_(NULL)
17   {
18     Ipopt::SmartPtr<TNLPSolver> tnlp_solver =
19        static_cast<TNLPSolver *> (b->nonlinearSolver()->solver());
20     Ipopt::SmartPtr<Ipopt::OptionsList> options = tnlp_solver->options();
21 
22 	    options->GetIntegerValue("ecp_max_rounds_strong",
23 	                             maxCuttingPlaneIterations_,
24                                      b->nonlinearSolver()->prefix());
25 	    options->GetNumericValue("ecp_abs_tol_strong",
26                                      abs_ecp_tol_,
27                                      b->nonlinearSolver()->prefix());
28 	    options->GetNumericValue("ecp_rel_tol_strong",
29                                      rel_ecp_tol_,
30                                      b->nonlinearSolver()->prefix());
31 	    int dummy;
32 	    options->GetEnumValue("lp_strong_warmstart_method",
33                                   dummy,
34                                   b->nonlinearSolver()->prefix());
35 	    warm_start_mode_ = (WarmStartMethod) dummy;
36 	  }
37 
LpBranchingSolver(const LpBranchingSolver & rhs)38   LpBranchingSolver::LpBranchingSolver(const LpBranchingSolver & rhs) :
39       StrongBranchingSolver(rhs),
40       lin_(NULL),
41       warm_(NULL),
42       ecp_(NULL),
43       maxCuttingPlaneIterations_(rhs.maxCuttingPlaneIterations_),
44       abs_ecp_tol_(rhs.abs_ecp_tol_),
45       rel_ecp_tol_(rhs.rel_ecp_tol_),
46       warm_start_mode_(rhs.warm_start_mode_)
47   {}
48 
49   LpBranchingSolver &
operator =(const LpBranchingSolver & rhs)50   LpBranchingSolver::operator=(const LpBranchingSolver & rhs)
51   {
52     if (this != &rhs) {
53       StrongBranchingSolver::operator=(rhs);
54     }
55     maxCuttingPlaneIterations_ = rhs.maxCuttingPlaneIterations_;
56     abs_ecp_tol_ = rhs.abs_ecp_tol_;
57     rel_ecp_tol_ = rhs.rel_ecp_tol_;
58     warm_start_mode_ = rhs.warm_start_mode_;
59     // I assume that no LP solver information is ever copied
60     delete lin_;
61     delete warm_;
62     delete ecp_;
63     lin_ = NULL;
64     warm_ = NULL;
65     ecp_ = NULL;
66     return *this;
67   }
68 
~LpBranchingSolver()69   LpBranchingSolver::~LpBranchingSolver ()
70   {
71     delete lin_;
72     delete warm_;
73     delete ecp_;
74   }
75 
76   void LpBranchingSolver::
markHotStart(OsiTMINLPInterface * tminlp_interface)77   markHotStart(OsiTMINLPInterface* tminlp_interface)
78   {
79     lin_ = new OsiClpSolverInterface();
80     tminlp_interface->extractLinearRelaxation(*lin_, tminlp_interface->getColSolution(),
81                                               true);
82     double cutoff = -DBL_MAX;
83     tminlp_interface->getDblParam(OsiDualObjectiveLimit, cutoff);
84     lin_->setDblParam(OsiDualObjectiveLimit, cutoff);
85     //printf("Cutoff %g # ecp iteration %i\n",cutoff, maxCuttingPlaneIterations_);
86     lin_->messageHandler()->setLogLevel(0);
87     lin_->resolve();
88     warm_ = lin_->getWarmStart();
89     //if (maxCuttingPlaneIterations_)
90     //  ecp_ = new EcpCuts(tminlp_interface, maxCuttingPlaneIterations_,
91     //      abs_ecp_tol_, rel_ecp_tol_, -1.);
92   }
93 
94   void LpBranchingSolver::
unmarkHotStart(OsiTMINLPInterface * tminlp_interface)95   unmarkHotStart(OsiTMINLPInterface* tminlp_interface)
96   {
97     // Free memory
98     delete lin_;
99     delete warm_;
100     delete ecp_;
101     lin_ = NULL;
102     warm_ = NULL;
103     ecp_ = NULL;
104   }
105 
106   TNLPSolver::ReturnStatus LpBranchingSolver::
solveFromHotStart(OsiTMINLPInterface * tminlp_interface)107   solveFromHotStart(OsiTMINLPInterface* tminlp_interface)
108   {
109     TNLPSolver::ReturnStatus retstatus = TNLPSolver::solvedOptimal;
110 
111     // updated the bounds of the linear solver
112     std::vector<int> diff_low_bnd_index;
113     std::vector<double> diff_low_bnd_value;
114     std::vector<int> diff_up_bnd_index;
115     std::vector<double> diff_up_bnd_value;
116 
117     // Get the bounds.  We assume that the bounds in the linear solver
118     // are always the original ones
119     const int numCols = tminlp_interface->getNumCols();
120     const double* colLow_orig = lin_->getColLower();
121     const double* colUp_orig = lin_->getColUpper();
122     const double* colLow = tminlp_interface->getColLower();
123     const double* colUp = tminlp_interface->getColUpper();
124 
125     OsiSolverInterface * lin = lin_;
126     // eventualy clone lin_
127     if(warm_start_mode_ == Clone){
128       lin = lin_->clone();
129 //      std::cout<<"Cloning it"<<std::endl;
130     }
131     // Set the bounds on the LP solver according to the changes in
132     // tminlp_interface
133     for (int i=0; i<numCols; i++) {
134       const double& lo = colLow[i];
135       if (colLow_orig[i] < lo) {
136         if(warm_start_mode_ == Basis){
137           diff_low_bnd_value.push_back(colLow_orig[i]);
138           diff_low_bnd_index.push_back(i);
139         }
140         lin->setColLower(i,lo);
141       }
142       const double& up = colUp[i];
143       if (colUp_orig[i] > up) {
144         if(warm_start_mode_ == Basis){
145           diff_up_bnd_index.push_back(i);
146           diff_up_bnd_value.push_back(colUp_orig[i]);
147         }
148         lin->setColUpper(i,lo);
149       }
150     }
151 
152     if(warm_start_mode_ == Basis){
153       lin->setWarmStart(warm_);
154     }
155 
156     lin->resolve();
157 
158     double obj = lin->getObjValue();
159     bool go_on = true;
160     if (lin->isProvenPrimalInfeasible() ||
161         lin->isDualObjectiveLimitReached()) {
162       retstatus = TNLPSolver::provenInfeasible;
163       go_on = false;
164     }
165     else if (lin->isIterationLimitReached()) {
166       retstatus = TNLPSolver::iterationLimit;
167       go_on = false;
168     }
169     else {
170       if (maxCuttingPlaneIterations_ > 0 && go_on) {
171         double violation;
172         obj = ecp_->doEcpRounds(*lin, true, &violation);
173         if (obj == COIN_DBL_MAX) {
174           retstatus = TNLPSolver::provenInfeasible;
175         }
176         else if (violation <= 1e-8) {
177           retstatus = TNLPSolver::solvedOptimal;
178         }
179       }
180     }
181     tminlp_interface->problem()->set_obj_value(obj);
182     tminlp_interface->problem()->Set_x_sol(numCols, lin_->getColSolution());
183 
184     //restore the original bounds
185     if(warm_start_mode_ == Basis){
186       for (unsigned int i = 0; i < diff_low_bnd_index.size(); i++) {
187         lin_->setColLower(diff_low_bnd_index[i],diff_low_bnd_value[i]);
188       }
189       for (unsigned int i = 0; i < diff_up_bnd_index.size(); i++) {
190         lin_->setColUpper(diff_up_bnd_index[i],diff_up_bnd_value[i]);
191       }
192     }
193     else {
194       delete lin;
195     }
196     return retstatus;
197   }
198 
199   void
registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)200   LpBranchingSolver::registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)
201   {
202     roptions->SetRegisteringCategory("ECP based strong branching",RegisteredOptions::UndocumentedCategory);
203     roptions->AddLowerBoundedIntegerOption
204     ("ecp_max_rounds_strong",
205      "Set the maximal number of rounds of ECP cuts in strong branching.",
206      0,0,
207      "");
208     roptions->setOptionExtraInfo("ecp_max_rounds_strong",63);
209     roptions->AddLowerBoundedNumberOption
210     ("ecp_abs_tol_strong",
211      "Set the absolute termination tolerance for ECP rounds in strong branching.",
212      0,false,1e-6,
213      "");
214     roptions->setOptionExtraInfo("ecp_abs_tol_strong",63);
215     roptions->AddLowerBoundedNumberOption
216     ("ecp_rel_tol_strong",
217      "Set the relative termination tolerance for ECP rounds in strong branching.",
218      0,false,1e-1,
219      "");
220     roptions->setOptionExtraInfo("ecp_rel_tol_strong",63);
221     roptions->AddStringOption2
222     ("lp_strong_warmstart_method",
223      "Choose method to use for warm starting lp in strong branching",
224      "Basis",
225      "Basis", "Use optimal basis of node",
226      "Clone", "Clone optimal problem of node",
227      "(Advanced stuff)");
228     roptions->setOptionExtraInfo("lp_strong_warmstart_method",63);
229   }
230 
231 }
232