00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #include "BonNlpHeuristic.hpp"
00011 #include "BonCouenneInterface.hpp"
00012 #include "CouenneObject.hpp"
00013 #include "CouenneProblem.hpp"
00014 #include "CbcCutGenerator.hpp"
00015 #include "CbcBranchActual.hpp"
00016 #include "BonAuxInfos.hpp"
00017 #include "CoinHelperFunctions.hpp"
00018
00019 #include "CouenneCutGenerator.hpp"
00020 #include "CouenneProblem.hpp"
00021
00022 namespace Bonmin{
00023 NlpSolveHeuristic::NlpSolveHeuristic():
00024 CbcHeuristic(),
00025 nlp_(NULL),
00026 hasCloned_(false),
00027 maxNlpInf_(maxNlpInf_0),
00028 numberSolvePerLevel_(-1),
00029 couenne_(NULL){
00030 setHeuristicName("NlpSolveHeuristic");
00031 }
00032
00033 NlpSolveHeuristic::NlpSolveHeuristic(CbcModel & model, OsiSolverInterface &nlp, bool cloneNlp, CouenneProblem * couenne):
00034 CbcHeuristic(model), nlp_(&nlp), hasCloned_(cloneNlp),maxNlpInf_(maxNlpInf_0),
00035 numberSolvePerLevel_(-1),
00036 couenne_(couenne){
00037 setHeuristicName("NlpSolveHeuristic");
00038 if(cloneNlp)
00039 nlp_ = nlp.clone();
00040 }
00041
00042 NlpSolveHeuristic::NlpSolveHeuristic(const NlpSolveHeuristic & other):
00043 CbcHeuristic(other), nlp_(other.nlp_),
00044 hasCloned_(other.hasCloned_),
00045 maxNlpInf_(other.maxNlpInf_),
00046 numberSolvePerLevel_(other.numberSolvePerLevel_),
00047 couenne_(other.couenne_){
00048 if(hasCloned_ && nlp_ != NULL)
00049 nlp_ = other.nlp_->clone();
00050 }
00051
00052 CbcHeuristic *
00053 NlpSolveHeuristic::clone() const{
00054 return new NlpSolveHeuristic(*this);
00055 }
00056
00057 NlpSolveHeuristic &
00058 NlpSolveHeuristic::operator=(const NlpSolveHeuristic & rhs){
00059 if(this != &rhs){
00060 CbcHeuristic::operator=(rhs);
00061 if(hasCloned_ && nlp_)
00062 delete nlp_;
00063
00064 hasCloned_ = rhs.hasCloned_;
00065 if(nlp_ != NULL){
00066 if(hasCloned_)
00067 nlp_ = rhs.nlp_->clone();
00068 else
00069 nlp_ = rhs.nlp_;
00070 }
00071 }
00072 maxNlpInf_ = rhs.maxNlpInf_;
00073 numberSolvePerLevel_ = rhs.numberSolvePerLevel_;
00074 couenne_ = rhs.couenne_;
00075 return *this;
00076 }
00077
00078 NlpSolveHeuristic::~NlpSolveHeuristic(){
00079 if(hasCloned_)
00080 delete nlp_;
00081 nlp_ = NULL;
00082 }
00083
00084 void
00085 NlpSolveHeuristic::setNlp(OsiSolverInterface &nlp, bool cloneNlp){
00086 if(hasCloned_ && nlp_ != NULL)
00087 delete nlp_;
00088 hasCloned_ = cloneNlp;
00089 if(cloneNlp)
00090 nlp_ = nlp.clone();
00091 else
00092 nlp_ = &nlp;
00093 }
00094
00095 void
00096 NlpSolveHeuristic::setCouenneProblem(CouenneProblem * couenne){
00097 couenne_ = couenne;}
00098
00099
00100 int
00101 NlpSolveHeuristic::solution( double & objectiveValue, double * newSolution){
00102 OsiSolverInterface * solver = model_->solver();
00103
00104 OsiAuxInfo * auxInfo = solver->getAuxiliaryInfo();
00105 BabInfo * babInfo = dynamic_cast<BabInfo *> (auxInfo);
00106
00107 if(babInfo){
00108 babInfo->setHasNlpSolution(false);
00109 if(babInfo->infeasibleNode()){
00110 return 0;
00111 }
00112 }
00113
00114
00115
00116 bool too_deep = false;
00117
00118
00119 if (numberSolvePerLevel_ > -1){
00120 if (numberSolvePerLevel_ == 0)
00121 return 0;
00122
00123 const int depth = (model_ -> currentNode ()) ? model_ -> currentNode () -> depth () : 0;
00124
00125
00126 if (CoinDrand48 () > 1. / CoinMax
00127 (1., (double) ((depth - numberSolvePerLevel_) * (depth - numberSolvePerLevel_))))
00128 too_deep = true;
00129 }
00130
00131 if (too_deep)
00132 return 0;
00133
00134 double *lower = new double [couenne_ -> nVars ()];
00135 double *upper = new double [couenne_ -> nVars ()];
00136
00137 CoinFillN (lower, couenne_ -> nVars (), -COUENNE_INFINITY);
00138 CoinFillN (upper, couenne_ -> nVars (), COUENNE_INFINITY);
00139
00140 CoinCopyN (solver->getColLower(), nlp_ -> getNumCols (), lower);
00141 CoinCopyN (solver->getColUpper(), nlp_ -> getNumCols (), upper);
00142
00143
00144
00145
00146
00147
00148 const double * solution = solver->getColSolution();
00149 OsiBranchingInformation info (solver, true);
00150 const int & numberObjects = model_->numberObjects();
00151 OsiObject ** objects = model_->objects();
00152 double maxInfeasibility = 0;
00153
00154 bool haveRoundedIntVars = false;
00155
00156 for(int i = 0 ; i < numberObjects ; i++){
00157 CouenneObject * couObj = dynamic_cast <CouenneObject *> (objects [i]);
00158 if (couObj) {
00159 if (too_deep) {
00160 int dummy;
00161 double infeas;
00162 maxInfeasibility = max ( maxInfeasibility, infeas = couObj->infeasibility(&info, dummy));
00163 if(maxInfeasibility > maxNlpInf_){
00164 delete [] lower;
00165 delete [] upper;
00166 return 0;
00167 }
00168 }
00169 } else {
00170
00171 OsiSimpleInteger * intObj = dynamic_cast<OsiSimpleInteger *>(objects[i]);
00172
00173 if (intObj) {
00174 const int & i = intObj -> columnNumber ();
00175
00176 double value = solution [i];
00177 if (value < lower[i])
00178 value = lower[i];
00179 else if(value > upper[i])
00180 value = upper[i];
00181
00182 double rounded = floor (value + 0.5);
00183
00184 if (fabs (value - rounded) > COUENNE_EPS) {
00185 haveRoundedIntVars = true;
00186
00187 }
00188
00189
00190
00191
00192 }
00193 else{
00194 throw CoinError("Bonmin::NlpSolveHeuristic","solution",
00195 "Unknown object.");
00196 }
00197 }
00198 }
00199
00200
00201
00202
00203 bool skipOnInfeasibility = false;
00204
00205 double *Y = new double [couenne_ -> nVars ()];
00206 CoinFillN (Y, couenne_ -> nVars (), 0.);
00207 CoinCopyN (solution, nlp_ -> getNumCols (), Y);
00208
00209
00210
00211
00212
00213
00214
00215
00216 if (haveRoundedIntVars)
00217 skipOnInfeasibility = (couenne_ -> getIntegerCandidate (solution, Y, lower, upper) < 0);
00218
00219
00220
00221
00222
00223
00224
00225
00226 bool foundSolution = false;
00227
00228 if (haveRoundedIntVars && skipOnInfeasibility)
00229
00230
00231 for (int i = couenne_ -> nOrigVars (); i--;)
00232
00233 if (couenne_ -> Var (i) -> isDefinedInteger ())
00234 lower [i] = upper [i] = Y [i] =
00235 (CoinDrand48 () < 0.5) ?
00236 floor (Y [i] + COUENNE_EPS) :
00237 ceil (Y [i] - COUENNE_EPS);
00238
00239 else if (lower [i] > upper [i]) {
00240
00241
00242
00243
00244 double swap = lower [i];
00245 lower [i] = upper [i];
00246 upper [i] = swap;
00247 }
00248
00249
00250 {
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261 double * saveColLower = CoinCopyOfArray (nlp_ -> getColLower (), nlp_ -> getNumCols ());
00262 double * saveColUpper = CoinCopyOfArray (nlp_ -> getColUpper (), nlp_ -> getNumCols ());
00263
00264 nlp_ -> setColLower (lower);
00265 nlp_ -> setColUpper (upper);
00266 nlp_ -> setColSolution (Y);
00267
00268
00269 nlp_ -> initialSolve ();
00270
00271 double obj = (nlp_ -> isProvenOptimal()) ? nlp_ -> getObjValue (): COIN_DBL_MAX;
00272
00273 if (nlp_ -> isProvenOptimal () &&
00274 (obj < couenne_ -> getCutOff ()) &&
00275 couenne_ -> checkNLP (nlp_ -> getColSolution (), obj)) {
00276
00277
00278
00279 const int nVars = solver->getNumCols();
00280 double* tmpSolution = new double [nVars];
00281 CoinCopyN (nlp_ -> getColSolution(), nlp_ -> getNumCols(), tmpSolution);
00282
00283
00284 CouenneInterface * couenne = dynamic_cast <CouenneInterface *> (nlp_);
00285
00286 if (couenne)
00287 couenne_ -> getAuxs (tmpSolution);
00288
00289 if (babInfo){
00290 babInfo->setNlpSolution (tmpSolution, nVars, obj);
00291 babInfo->setHasNlpSolution (true);
00292 }
00293
00294 if (obj < objectiveValue) {
00295
00296 const CouNumber
00297 *lb = solver -> getColLower (),
00298 *ub = solver -> getColUpper ();
00299
00300
00301
00302 for (int i=0; i < nVars; i++, lb++, ub++) {
00303
00304 CouNumber &t = tmpSolution [i];
00305 if (t < *lb) t = *lb;
00306 else if (t > *ub) t = *ub;
00307 }
00308
00309 couenne_ -> setCutOff (obj);
00310 foundSolution = true;
00311 objectiveValue = obj;
00312 CoinCopyN (tmpSolution, nVars, newSolution);
00313 }
00314 delete [] tmpSolution;
00315 }
00316
00317 nlp_->setColLower(saveColLower);
00318 nlp_->setColUpper(saveColUpper);
00319
00320 delete [] saveColLower;
00321 delete [] saveColUpper;
00322 }
00323
00324 delete [] Y;
00325
00326 delete [] lower;
00327 delete [] upper;
00328
00329 return foundSolution;
00330 }
00331 }