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