Changeset 1314 for branches/sandbox/Cbc/src/CbcCompareActual.cpp
 Timestamp:
 Nov 25, 2009 12:58:07 PM (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/sandbox/Cbc/src/CbcCompareActual.cpp
r1286 r1314 1 /* $Id$ */2 // Copyright (C) 2004, International Business Machines3 // Corporation and others. All Rights Reserved.4 #if defined(_MSC_VER)5 // Turn off compiler warning about long names6 # pragma warning(disable:4786)7 #endif8 #include <cassert>9 #include <cstdlib>10 #include <cmath>11 #include <cfloat>12 //#define CBC_DEBUG13 14 #include "CbcMessage.hpp"15 #include "CbcModel.hpp"16 #include "CbcTree.hpp"17 #include "CbcCompareActual.hpp"18 #include "CoinError.hpp"19 1 20 2 21 /** Default Constructor22 23 */24 CbcCompareDepth::CbcCompareDepth ()25 : CbcCompareBase()26 {27 test_ = this;28 }29 30 // Copy constructor31 CbcCompareDepth::CbcCompareDepth ( const CbcCompareDepth & rhs)32 : CbcCompareBase(rhs)33 34 {35 }36 37 // Clone38 CbcCompareBase *39 CbcCompareDepth::clone() const40 {41 return new CbcCompareDepth(*this);42 }43 44 // Assignment operator45 CbcCompareDepth &46 CbcCompareDepth::operator=( const CbcCompareDepth & rhs)47 {48 if (this != &rhs) {49 CbcCompareBase::operator=(rhs);50 }51 return *this;52 }53 54 // Destructor55 CbcCompareDepth::~CbcCompareDepth ()56 {57 }58 59 // Returns true if y better than x60 bool61 CbcCompareDepth::test (CbcNode * x, CbcNode * y)62 {63 int testX = x>depth();64 int testY = y>depth();65 if (testX != testY)66 return testX < testY;67 else68 return equalityTest(x, y); // so ties will be broken in consistent manner69 }70 // Create C++ lines to get to current state71 void72 CbcCompareDepth::generateCpp( FILE * fp)73 {74 fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");75 fprintf(fp, "3 CbcCompareDepth compare;\n");76 fprintf(fp, "3 cbcModel>setNodeComparison(compare);\n");77 }78 79 /** Default Constructor80 81 */82 CbcCompareObjective::CbcCompareObjective ()83 : CbcCompareBase()84 {85 test_ = this;86 }87 88 // Copy constructor89 CbcCompareObjective::CbcCompareObjective ( const CbcCompareObjective & rhs)90 : CbcCompareBase(rhs)91 92 {93 }94 95 // Clone96 CbcCompareBase *97 CbcCompareObjective::clone() const98 {99 return new CbcCompareObjective(*this);100 }101 102 // Assignment operator103 CbcCompareObjective &104 CbcCompareObjective::operator=( const CbcCompareObjective & rhs)105 {106 if (this != &rhs) {107 CbcCompareBase::operator=(rhs);108 }109 return *this;110 }111 112 // Destructor113 CbcCompareObjective::~CbcCompareObjective ()114 {115 }116 117 // Returns true if y better than x118 bool119 CbcCompareObjective::test (CbcNode * x, CbcNode * y)120 {121 double testX = x>objectiveValue();122 double testY = y>objectiveValue();123 if (testX != testY)124 return testX > testY;125 else126 return equalityTest(x, y); // so ties will be broken in consistent manner127 }128 // Create C++ lines to get to current state129 void130 CbcCompareObjective::generateCpp( FILE * fp)131 {132 fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");133 fprintf(fp, "3 CbcCompareObjective compare;\n");134 fprintf(fp, "3 cbcModel>setNodeComparison(compare);\n");135 }136 137 138 /** Default Constructor139 140 */141 CbcCompareDefault::CbcCompareDefault ()142 : CbcCompareBase(),143 weight_(1.0),144 saveWeight_(0.0),145 cutoff_(COIN_DBL_MAX),146 bestPossible_(COIN_DBL_MAX),147 numberSolutions_(0),148 treeSize_(0),149 breadthDepth_(5)150 {151 test_ = this;152 }153 154 // Constructor with weight155 CbcCompareDefault::CbcCompareDefault (double weight)156 : CbcCompareBase(),157 weight_(weight) ,158 saveWeight_(0.0),159 cutoff_(COIN_DBL_MAX),160 bestPossible_(COIN_DBL_MAX),161 numberSolutions_(0),162 treeSize_(0),163 breadthDepth_(5)164 {165 test_ = this;166 }167 168 169 // Copy constructor170 CbcCompareDefault::CbcCompareDefault ( const CbcCompareDefault & rhs)171 : CbcCompareBase(rhs)172 173 {174 weight_ = rhs.weight_;175 saveWeight_ = rhs.saveWeight_;176 cutoff_ = rhs.cutoff_;177 bestPossible_ = rhs.bestPossible_;178 numberSolutions_ = rhs.numberSolutions_;179 treeSize_ = rhs.treeSize_;180 breadthDepth_ = rhs.breadthDepth_;181 }182 183 // Clone184 CbcCompareBase *185 CbcCompareDefault::clone() const186 {187 return new CbcCompareDefault(*this);188 }189 190 // Assignment operator191 CbcCompareDefault &192 CbcCompareDefault::operator=( const CbcCompareDefault & rhs)193 {194 if (this != &rhs) {195 CbcCompareBase::operator=(rhs);196 weight_ = rhs.weight_;197 saveWeight_ = rhs.saveWeight_;198 cutoff_ = rhs.cutoff_;199 bestPossible_ = rhs.bestPossible_;200 numberSolutions_ = rhs.numberSolutions_;201 treeSize_ = rhs.treeSize_;202 breadthDepth_ = rhs.breadthDepth_;203 }204 return *this;205 }206 207 // Destructor208 CbcCompareDefault::~CbcCompareDefault ()209 {210 }211 212 // Returns true if y better than x213 bool214 CbcCompareDefault::test (CbcNode * x, CbcNode * y)215 {216 #if 0217 // always choose *smallest* depth if one or both <= breadthDepth_218 int depthX = x>depth();219 int depthY = y>depth();220 if (depthX <= breadthDepth_  depthY <= breadthDepth_) {221 if (depthX != depthY)222 return depthX > depthY;223 else224 return equalityTest(x, y); // so ties will be broken in consistent manner225 }226 if (weight_ == 1.0  weight_ == 3.0) {227 int adjust = (weight_ == 3.0) ? 10000 : 0;228 // before solution229 /*printf("x %d %d %g, y %d %d %g\n",230 x>numberUnsatisfied(),x>depth(),x>objectiveValue(),231 y>numberUnsatisfied(),y>depth(),y>objectiveValue()); */232 if (x>numberUnsatisfied() > y>numberUnsatisfied() + adjust) {233 return true;234 } else if (x>numberUnsatisfied() < y>numberUnsatisfied()  adjust) {235 return false;236 } else {237 int depthX = x>depth();238 int depthY = y>depth();239 if (depthX != depthY)240 return depthX < depthY;241 else242 return equalityTest(x, y); // so ties will be broken in consistent manner243 }244 } else {245 // after solution246 double weight = CoinMax(weight_, 0.0);247 double testX = x>objectiveValue() + weight * x>numberUnsatisfied();248 double testY = y>objectiveValue() + weight * y>numberUnsatisfied();249 if (testX != testY)250 return testX > testY;251 else252 return equalityTest(x, y); // so ties will be broken in consistent manner253 }254 #else255 //weight_=0.0;256 if ((weight_ == 1.0 && (y>depth() > breadthDepth_ && x>depth() > breadthDepth_))  weight_ == 3.0  weight_ == 2.0) {257 int adjust = (weight_ == 3.0) ? 10000 : 0;258 // before solution259 /*printf("x %d %d %g, y %d %d %g\n",260 x>numberUnsatisfied(),x>depth(),x>objectiveValue(),261 y>numberUnsatisfied(),y>depth(),y>objectiveValue()); */262 if (x>numberUnsatisfied() > y>numberUnsatisfied() + adjust) {263 return true;264 } else if (x>numberUnsatisfied() < y>numberUnsatisfied()  adjust) {265 return false;266 } else {267 int depthX = x>depth();268 int depthY = y>depth();269 if (depthX != depthY)270 return depthX < depthY;271 else272 return equalityTest(x, y); // so ties will be broken in consistent manner273 }274 } else {275 // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one276 int depthX = x>depth();277 int depthY = y>depth();278 /*if ((depthX==4&&depthY==5)(depthX==5&&depthY==4))279 printf("X %x depth %d, Y %x depth %d, breadth %d\n",280 x,depthX,y,depthY,breadthDepth_);*/281 if (depthX <= breadthDepth_  depthY <= breadthDepth_) {282 if (depthX <= breadthDepth_ && depthY <= breadthDepth_) {283 if (depthX != depthY) {284 return depthX < depthY;285 }286 } else {287 assert (depthX != depthY) ;288 return depthX > depthY;289 }290 }291 // after solution ?292 #define THRESH2 0.999293 #define TRY_THIS 0294 #if TRY_THIS==0295 double weight = CoinMax(weight_, 1.0e9);296 double testX = x>objectiveValue() + weight * x>numberUnsatisfied();297 double testY = y>objectiveValue() + weight * y>numberUnsatisfied();298 #elif TRY_THIS==1299 /* compute what weight would have to be to hit target300 then reverse sign as large weight good */301 double target = (1.0  THRESH2) * bestPossible_ + THRESH2 * cutoff_;302 double weight;303 weight = (target  x>objectiveValue()) /304 static_cast<double>(x>numberUnsatisfied());305 double testX =  weight;306 weight = (target  y>objectiveValue()) /307 static_cast<double>(y>numberUnsatisfied());308 double testY =  weight;309 #elif TRY_THIS==2310 // Use estimates311 double testX = x>guessedObjectiveValue();312 double testY = y>guessedObjectiveValue();313 #elif TRY_THIS==3314 #define THRESH 0.95315 // Use estimates316 double testX = x>guessedObjectiveValue();317 double testY = y>guessedObjectiveValue();318 if (x>objectiveValue()  bestPossible_ > THRESH*(cutoff_  bestPossible_))319 testX *= 2.0; // make worse320 if (y>objectiveValue()  bestPossible_ > THRESH*(cutoff_  bestPossible_))321 testY *= 2.0; // make worse322 #endif323 if (testX != testY)324 return testX > testY;325 else326 return equalityTest(x, y); // so ties will be broken in consistent manner327 }328 #endif329 }330 // This allows method to change behavior as it is called331 // after each solution332 void333 CbcCompareDefault::newSolution(CbcModel * model,334 double objectiveAtContinuous,335 int numberInfeasibilitiesAtContinuous)336 {337 cutoff_ = model>getCutoff();338 if (model>getSolutionCount() == model>getNumberHeuristicSolutions() &&339 model>getSolutionCount() < 5 && model>getNodeCount() < 500)340 return; // solution was got by rounding341 // set to get close to this solution342 double costPerInteger =343 (model>getObjValue()  objectiveAtContinuous) /344 static_cast<double> (numberInfeasibilitiesAtContinuous);345 weight_ = 0.95 * costPerInteger;346 saveWeight_ = 0.95 * weight_;347 numberSolutions_++;348 //if (numberSolutions_>5)349 //weight_ =0.0; // this searches on objective350 }351 // This allows method to change behavior352 bool353 CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)354 {355 #if 0356 // was357 if (numberNodes > 10000)358 weight_ = 0.0; // this searches on objective359 // get size of tree360 treeSize_ = model>tree()>size();361 #else362 double saveWeight = weight_;363 int numberNodes1000 = numberNodes / 1000;364 if (numberNodes > 10000) {365 weight_ = 0.0; // this searches on objective366 // but try a bit of other stuff367 if ((numberNodes1000 % 4) == 1)368 weight_ = saveWeight_;369 } else if (numberNodes == 1000 && weight_ == 2.0) {370 weight_ = 1.0; // Go to depth first371 }372 // get size of tree373 treeSize_ = model>tree()>size();374 if (treeSize_ > 10000) {375 int n1 = model>solver()>getNumRows() + model>solver()>getNumCols();376 int n2 = model>numberObjects();377 double size = n1 * 0.1 + n2 * 2.0;378 // set weight to reduce size most of time379 if (treeSize_*(size + 100.0) > 5.0e7)380 weight_ = 3.0;381 else if ((numberNodes1000 % 4) == 0 && treeSize_*size > 1.0e6)382 weight_ = 1.0;383 else if ((numberNodes1000 % 4) == 1)384 weight_ = 0.0;385 else386 weight_ = saveWeight_;387 }388 #endif389 //return numberNodes==11000; // resort if first time390 return (weight_ != saveWeight);391 }392 393 // Create C++ lines to get to current state394 void395 CbcCompareDefault::generateCpp( FILE * fp)396 {397 CbcCompareDefault other;398 fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");399 fprintf(fp, "3 CbcCompareDefault compare;\n");400 if (weight_ != other.weight_)401 fprintf(fp, "3 compare.setWeight(%g);\n", weight_);402 fprintf(fp, "3 cbcModel>setNodeComparison(compare);\n");403 }404 405 /** Default Constructor406 407 */408 CbcCompareEstimate::CbcCompareEstimate ()409 : CbcCompareBase()410 {411 test_ = this;412 }413 414 // Copy constructor415 CbcCompareEstimate::CbcCompareEstimate ( const CbcCompareEstimate & rhs)416 : CbcCompareBase(rhs)417 418 {419 }420 421 // Clone422 CbcCompareBase *423 CbcCompareEstimate::clone() const424 {425 return new CbcCompareEstimate(*this);426 }427 428 // Assignment operator429 CbcCompareEstimate &430 CbcCompareEstimate::operator=( const CbcCompareEstimate & rhs)431 {432 if (this != &rhs) {433 CbcCompareBase::operator=(rhs);434 }435 return *this;436 }437 438 // Destructor439 CbcCompareEstimate::~CbcCompareEstimate ()440 {441 }442 443 // Returns true if y better than x444 bool445 CbcCompareEstimate::test (CbcNode * x, CbcNode * y)446 {447 double testX = x>guessedObjectiveValue();448 double testY = y>guessedObjectiveValue();449 if (testX != testY)450 return testX > testY;451 else452 return equalityTest(x, y); // so ties will be broken in consistent manner453 }454 455 // Create C++ lines to get to current state456 void457 CbcCompareEstimate::generateCpp( FILE * fp)458 {459 fprintf(fp, "0#include \"CbcCompareActual.hpp\"\n");460 fprintf(fp, "3 CbcCompareEstimate compare;\n");461 fprintf(fp, "3 cbcModel>setNodeComparison(compare);\n");462 }
Note: See TracChangeset
for help on using the changeset viewer.