[13] | 1 | // Copyright (C) 2004, International Business Machines |
---|
| 2 | // Corporation and others. All Rights Reserved. |
---|
| 3 | #if defined(_MSC_VER) |
---|
| 4 | // Turn off compiler warning about long names |
---|
| 5 | # pragma warning(disable:4786) |
---|
| 6 | #endif |
---|
| 7 | #include <cassert> |
---|
| 8 | #include <cmath> |
---|
| 9 | #include <cfloat> |
---|
| 10 | //#define CBC_DEBUG |
---|
| 11 | |
---|
| 12 | #include "CbcMessage.hpp" |
---|
| 13 | #include "CbcModel.hpp" |
---|
[27] | 14 | #include "CbcTree.hpp" |
---|
[13] | 15 | #include "CbcCompareActual.hpp" |
---|
| 16 | #include "CoinError.hpp" |
---|
| 17 | |
---|
| 18 | |
---|
| 19 | /** Default Constructor |
---|
| 20 | |
---|
| 21 | */ |
---|
| 22 | CbcCompareDepth::CbcCompareDepth () |
---|
| 23 | : CbcCompareBase() |
---|
| 24 | { |
---|
| 25 | test_=this; |
---|
| 26 | } |
---|
| 27 | |
---|
| 28 | // Copy constructor |
---|
| 29 | CbcCompareDepth::CbcCompareDepth ( const CbcCompareDepth & rhs) |
---|
| 30 | :CbcCompareBase(rhs) |
---|
| 31 | |
---|
| 32 | { |
---|
| 33 | } |
---|
| 34 | |
---|
| 35 | // Clone |
---|
| 36 | CbcCompareBase * |
---|
| 37 | CbcCompareDepth::clone() const |
---|
| 38 | { |
---|
| 39 | return new CbcCompareDepth(*this); |
---|
| 40 | } |
---|
| 41 | |
---|
| 42 | // Assignment operator |
---|
| 43 | CbcCompareDepth & |
---|
| 44 | CbcCompareDepth::operator=( const CbcCompareDepth& rhs) |
---|
| 45 | { |
---|
| 46 | if (this!=&rhs) { |
---|
| 47 | CbcCompareBase::operator=(rhs); |
---|
| 48 | } |
---|
| 49 | return *this; |
---|
| 50 | } |
---|
| 51 | |
---|
| 52 | // Destructor |
---|
| 53 | CbcCompareDepth::~CbcCompareDepth () |
---|
| 54 | { |
---|
| 55 | } |
---|
| 56 | |
---|
| 57 | // Returns true if y better than x |
---|
| 58 | bool |
---|
| 59 | CbcCompareDepth::test (CbcNode * x, CbcNode * y) |
---|
| 60 | { |
---|
| 61 | return x->depth() < y->depth(); |
---|
| 62 | } |
---|
[356] | 63 | // Create C++ lines to get to current state |
---|
| 64 | void |
---|
| 65 | CbcCompareDepth::generateCpp( FILE * fp) |
---|
| 66 | { |
---|
| 67 | fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n"); |
---|
| 68 | fprintf(fp,"3 CbcCompareDepth compare;\n"); |
---|
| 69 | fprintf(fp,"3 cbcModel->setNodeComparison(compare);\n"); |
---|
| 70 | } |
---|
[13] | 71 | |
---|
| 72 | /** Default Constructor |
---|
| 73 | |
---|
| 74 | */ |
---|
| 75 | CbcCompareObjective::CbcCompareObjective () |
---|
| 76 | : CbcCompareBase() |
---|
| 77 | { |
---|
| 78 | test_=this; |
---|
| 79 | } |
---|
| 80 | |
---|
| 81 | // Copy constructor |
---|
| 82 | CbcCompareObjective::CbcCompareObjective ( const CbcCompareObjective & rhs) |
---|
| 83 | :CbcCompareBase(rhs) |
---|
| 84 | |
---|
| 85 | { |
---|
| 86 | } |
---|
| 87 | |
---|
| 88 | // Clone |
---|
| 89 | CbcCompareBase * |
---|
| 90 | CbcCompareObjective::clone() const |
---|
| 91 | { |
---|
| 92 | return new CbcCompareObjective(*this); |
---|
| 93 | } |
---|
| 94 | |
---|
| 95 | // Assignment operator |
---|
| 96 | CbcCompareObjective & |
---|
| 97 | CbcCompareObjective::operator=( const CbcCompareObjective& rhs) |
---|
| 98 | { |
---|
| 99 | if (this!=&rhs) { |
---|
| 100 | CbcCompareBase::operator=(rhs); |
---|
| 101 | } |
---|
| 102 | return *this; |
---|
| 103 | } |
---|
| 104 | |
---|
| 105 | // Destructor |
---|
| 106 | CbcCompareObjective::~CbcCompareObjective () |
---|
| 107 | { |
---|
| 108 | } |
---|
| 109 | |
---|
| 110 | // Returns true if y better than x |
---|
| 111 | bool |
---|
| 112 | CbcCompareObjective::test (CbcNode * x, CbcNode * y) |
---|
| 113 | { |
---|
| 114 | return x->objectiveValue() > y->objectiveValue(); |
---|
| 115 | } |
---|
[356] | 116 | // Create C++ lines to get to current state |
---|
| 117 | void |
---|
| 118 | CbcCompareObjective::generateCpp( FILE * fp) |
---|
| 119 | { |
---|
| 120 | fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n"); |
---|
| 121 | fprintf(fp,"3 CbcCompareObjective compare;\n"); |
---|
| 122 | fprintf(fp,"3 cbcModel->setNodeComparison(compare);\n"); |
---|
| 123 | } |
---|
[13] | 124 | |
---|
[356] | 125 | |
---|
[13] | 126 | /** Default Constructor |
---|
| 127 | |
---|
| 128 | */ |
---|
| 129 | CbcCompareDefault::CbcCompareDefault () |
---|
| 130 | : CbcCompareBase(), |
---|
| 131 | weight_(-1.0), |
---|
[97] | 132 | saveWeight_(0.0), |
---|
[27] | 133 | numberSolutions_(0), |
---|
| 134 | treeSize_(0) |
---|
[13] | 135 | { |
---|
| 136 | test_=this; |
---|
| 137 | } |
---|
| 138 | |
---|
| 139 | // Constructor with weight |
---|
| 140 | CbcCompareDefault::CbcCompareDefault (double weight) |
---|
| 141 | : CbcCompareBase(), |
---|
| 142 | weight_(weight) , |
---|
[97] | 143 | saveWeight_(0.0), |
---|
[27] | 144 | numberSolutions_(0), |
---|
| 145 | treeSize_(0) |
---|
[13] | 146 | { |
---|
| 147 | test_=this; |
---|
| 148 | } |
---|
| 149 | |
---|
| 150 | |
---|
| 151 | // Copy constructor |
---|
| 152 | CbcCompareDefault::CbcCompareDefault ( const CbcCompareDefault & rhs) |
---|
| 153 | :CbcCompareBase(rhs) |
---|
| 154 | |
---|
| 155 | { |
---|
| 156 | weight_=rhs.weight_; |
---|
[97] | 157 | saveWeight_ = rhs.saveWeight_; |
---|
[13] | 158 | numberSolutions_=rhs.numberSolutions_; |
---|
[27] | 159 | treeSize_ = rhs.treeSize_; |
---|
[13] | 160 | } |
---|
| 161 | |
---|
| 162 | // Clone |
---|
| 163 | CbcCompareBase * |
---|
| 164 | CbcCompareDefault::clone() const |
---|
| 165 | { |
---|
| 166 | return new CbcCompareDefault(*this); |
---|
| 167 | } |
---|
| 168 | |
---|
| 169 | // Assignment operator |
---|
| 170 | CbcCompareDefault & |
---|
| 171 | CbcCompareDefault::operator=( const CbcCompareDefault& rhs) |
---|
| 172 | { |
---|
| 173 | if (this!=&rhs) { |
---|
| 174 | CbcCompareBase::operator=(rhs); |
---|
| 175 | weight_=rhs.weight_; |
---|
[97] | 176 | saveWeight_ = rhs.saveWeight_; |
---|
[13] | 177 | numberSolutions_=rhs.numberSolutions_; |
---|
[27] | 178 | treeSize_ = rhs.treeSize_; |
---|
[13] | 179 | } |
---|
| 180 | return *this; |
---|
| 181 | } |
---|
| 182 | |
---|
| 183 | // Destructor |
---|
| 184 | CbcCompareDefault::~CbcCompareDefault () |
---|
| 185 | { |
---|
| 186 | } |
---|
| 187 | |
---|
| 188 | // Returns true if y better than x |
---|
| 189 | bool |
---|
| 190 | CbcCompareDefault::test (CbcNode * x, CbcNode * y) |
---|
| 191 | { |
---|
[97] | 192 | #if 0 |
---|
| 193 | // was |
---|
[27] | 194 | if (weight_<0.0||treeSize_>100000) { |
---|
[13] | 195 | // before solution |
---|
| 196 | /* printf("x %d %d %g, y %d %d %g\n", |
---|
| 197 | x->numberUnsatisfied(),x->depth(),x->objectiveValue(), |
---|
| 198 | y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */ |
---|
| 199 | if (x->numberUnsatisfied() > y->numberUnsatisfied()) |
---|
| 200 | return true; |
---|
| 201 | else if (x->numberUnsatisfied() < y->numberUnsatisfied()) |
---|
| 202 | return false; |
---|
| 203 | else |
---|
| 204 | return x->depth() < y->depth(); |
---|
| 205 | } else { |
---|
| 206 | // after solution |
---|
| 207 | return x->objectiveValue()+ weight_*x->numberUnsatisfied() > |
---|
| 208 | y->objectiveValue() + weight_*y->numberUnsatisfied(); |
---|
| 209 | } |
---|
[97] | 210 | #else |
---|
[208] | 211 | if (weight_==-1.0&&(y->depth()>7||x->depth()>7)) { |
---|
[97] | 212 | // before solution |
---|
| 213 | /* printf("x %d %d %g, y %d %d %g\n", |
---|
| 214 | x->numberUnsatisfied(),x->depth(),x->objectiveValue(), |
---|
| 215 | y->numberUnsatisfied(),y->depth(),y->objectiveValue()); */ |
---|
| 216 | if (x->numberUnsatisfied() > y->numberUnsatisfied()) |
---|
| 217 | return true; |
---|
| 218 | else if (x->numberUnsatisfied() < y->numberUnsatisfied()) |
---|
| 219 | return false; |
---|
| 220 | else |
---|
| 221 | return x->depth() < y->depth(); |
---|
| 222 | } else { |
---|
| 223 | // after solution |
---|
| 224 | double weight = CoinMax(weight_,0.0); |
---|
| 225 | return x->objectiveValue()+ weight*x->numberUnsatisfied() > |
---|
| 226 | y->objectiveValue() + weight*y->numberUnsatisfied(); |
---|
| 227 | } |
---|
| 228 | #endif |
---|
[13] | 229 | } |
---|
| 230 | // This allows method to change behavior as it is called |
---|
| 231 | // after each solution |
---|
| 232 | void |
---|
| 233 | CbcCompareDefault::newSolution(CbcModel * model, |
---|
| 234 | double objectiveAtContinuous, |
---|
| 235 | int numberInfeasibilitiesAtContinuous) |
---|
| 236 | { |
---|
[181] | 237 | if (model->getSolutionCount()==model->getNumberHeuristicSolutions()&& |
---|
| 238 | model->getSolutionCount()<5&&model->getNodeCount()<500) |
---|
[13] | 239 | return; // solution was got by rounding |
---|
| 240 | // set to get close to this solution |
---|
| 241 | double costPerInteger = |
---|
| 242 | (model->getObjValue()-objectiveAtContinuous)/ |
---|
| 243 | ((double) numberInfeasibilitiesAtContinuous); |
---|
[197] | 244 | weight_ = 0.95*costPerInteger; |
---|
| 245 | saveWeight_ = 0.95*weight_; |
---|
[13] | 246 | numberSolutions_++; |
---|
| 247 | if (numberSolutions_>5) |
---|
| 248 | weight_ =0.0; // this searches on objective |
---|
| 249 | } |
---|
| 250 | // This allows method to change behavior |
---|
[26] | 251 | bool |
---|
[13] | 252 | CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes) |
---|
| 253 | { |
---|
[97] | 254 | #if 0 |
---|
| 255 | // was |
---|
[13] | 256 | if (numberNodes>10000) |
---|
| 257 | weight_ =0.0; // this searches on objective |
---|
[27] | 258 | // get size of tree |
---|
| 259 | treeSize_ = model->tree()->size(); |
---|
[97] | 260 | #else |
---|
[197] | 261 | double saveWeight=weight_; |
---|
[200] | 262 | int numberNodes1000 = numberNodes/1000; |
---|
| 263 | if (numberNodes>10000) { |
---|
[97] | 264 | weight_ =0.0; // this searches on objective |
---|
[200] | 265 | // but try a bit of other stuff |
---|
| 266 | if ((numberNodes1000%4)==1) |
---|
| 267 | weight_=saveWeight_; |
---|
| 268 | } else if (numberNodes==1000&&weight_==-2.0) { |
---|
[97] | 269 | weight_=-1.0; // Go to depth first |
---|
[200] | 270 | } |
---|
[97] | 271 | // get size of tree |
---|
| 272 | treeSize_ = model->tree()->size(); |
---|
| 273 | if (treeSize_>10000) { |
---|
[202] | 274 | int n1 = model->solver()->getNumRows()+model->solver()->getNumCols(); |
---|
| 275 | int n2 = model->numberObjects(); |
---|
| 276 | double size = n1*0.1 + n2*2.0; |
---|
[97] | 277 | // set weight to reduce size most of time |
---|
[202] | 278 | if (treeSize_*size>5.0e7) |
---|
[97] | 279 | weight_=-1.0; |
---|
[202] | 280 | else if ((numberNodes1000%4)==0&&treeSize_*size>1.0e6) |
---|
[97] | 281 | weight_=-1.0; |
---|
[200] | 282 | else if ((numberNodes1000%4)==1) |
---|
[197] | 283 | weight_=0.0; |
---|
[97] | 284 | else |
---|
| 285 | weight_=saveWeight_; |
---|
| 286 | } |
---|
| 287 | #endif |
---|
[197] | 288 | //return numberNodes==11000; // resort if first time |
---|
| 289 | return (weight_!=saveWeight); |
---|
[13] | 290 | } |
---|
| 291 | |
---|
[356] | 292 | // Create C++ lines to get to current state |
---|
| 293 | void |
---|
| 294 | CbcCompareDefault::generateCpp( FILE * fp) |
---|
| 295 | { |
---|
| 296 | CbcCompareDefault other; |
---|
| 297 | fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n"); |
---|
| 298 | fprintf(fp,"3 CbcCompareDefault compare;\n"); |
---|
| 299 | if (weight_!=other.weight_) |
---|
| 300 | fprintf(fp,"3 compare.setWeight(%g);\n",weight_); |
---|
| 301 | fprintf(fp,"3 cbcModel->setNodeComparison(compare);\n"); |
---|
| 302 | } |
---|
| 303 | |
---|
[13] | 304 | /** Default Constructor |
---|
| 305 | |
---|
| 306 | */ |
---|
| 307 | CbcCompareEstimate::CbcCompareEstimate () |
---|
| 308 | : CbcCompareBase() |
---|
| 309 | { |
---|
| 310 | test_=this; |
---|
| 311 | } |
---|
| 312 | |
---|
| 313 | // Copy constructor |
---|
| 314 | CbcCompareEstimate::CbcCompareEstimate ( const CbcCompareEstimate & rhs) |
---|
| 315 | :CbcCompareBase(rhs) |
---|
| 316 | |
---|
| 317 | { |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | // Clone |
---|
| 321 | CbcCompareBase * |
---|
| 322 | CbcCompareEstimate::clone() const |
---|
| 323 | { |
---|
| 324 | return new CbcCompareEstimate(*this); |
---|
| 325 | } |
---|
| 326 | |
---|
| 327 | // Assignment operator |
---|
| 328 | CbcCompareEstimate & |
---|
| 329 | CbcCompareEstimate::operator=( const CbcCompareEstimate& rhs) |
---|
| 330 | { |
---|
| 331 | if (this!=&rhs) { |
---|
| 332 | CbcCompareBase::operator=(rhs); |
---|
| 333 | } |
---|
| 334 | return *this; |
---|
| 335 | } |
---|
| 336 | |
---|
| 337 | // Destructor |
---|
| 338 | CbcCompareEstimate::~CbcCompareEstimate () |
---|
| 339 | { |
---|
| 340 | } |
---|
| 341 | |
---|
| 342 | // Returns true if y better than x |
---|
| 343 | bool |
---|
| 344 | CbcCompareEstimate::test (CbcNode * x, CbcNode * y) |
---|
| 345 | { |
---|
| 346 | return x->guessedObjectiveValue() > y->guessedObjectiveValue() ; |
---|
| 347 | } |
---|
| 348 | |
---|
[356] | 349 | // Create C++ lines to get to current state |
---|
| 350 | void |
---|
| 351 | CbcCompareEstimate::generateCpp( FILE * fp) |
---|
| 352 | { |
---|
| 353 | fprintf(fp,"0#include \"CbcCompareActual.hpp\"\n"); |
---|
| 354 | fprintf(fp,"3 CbcCompareEstimate compare;\n"); |
---|
| 355 | fprintf(fp,"3 cbcModel->setNodeComparison(compare);\n"); |
---|
| 356 | } |
---|
| 357 | |
---|