Ignore:
Timestamp:
Nov 25, 2009 12:58:07 PM (10 years ago)
Author:
EdwinStraver
Message:

Broke up CbcCompareActual?.cpp into CbcCompareDepth?, CbcCompareDefault?, CbcCompareObjective? and CbcCompareEstimate?.
Carved CbcCutModifier? and CbcCutSubsetModifier? out of CbcCutGenerator?.
Updated spreadsheets.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/sandbox/Cbc/src/CbcCompareActual.cpp

    r1286 r1314  
    1 /* $Id$ */
    2 // Copyright (C) 2004, International Business Machines
    3 // Corporation and others.  All Rights Reserved.
    4 #if defined(_MSC_VER)
    5 // Turn off compiler warning about long names
    6 #  pragma warning(disable:4786)
    7 #endif
    8 #include <cassert>
    9 #include <cstdlib>
    10 #include <cmath>
    11 #include <cfloat>
    12 //#define CBC_DEBUG
    13 
    14 #include "CbcMessage.hpp"
    15 #include "CbcModel.hpp"
    16 #include "CbcTree.hpp"
    17 #include "CbcCompareActual.hpp"
    18 #include "CoinError.hpp"
    191
    202
    21 /** Default Constructor
    22 
    23 */
    24 CbcCompareDepth::CbcCompareDepth ()
    25         : CbcCompareBase()
    26 {
    27     test_ = this;
    28 }
    29 
    30 // Copy constructor
    31 CbcCompareDepth::CbcCompareDepth ( const CbcCompareDepth & rhs)
    32         : CbcCompareBase(rhs)
    33 
    34 {
    35 }
    36 
    37 // Clone
    38 CbcCompareBase *
    39 CbcCompareDepth::clone() const
    40 {
    41     return new CbcCompareDepth(*this);
    42 }
    43 
    44 // Assignment operator
    45 CbcCompareDepth &
    46 CbcCompareDepth::operator=( const CbcCompareDepth & rhs)
    47 {
    48     if (this != &rhs) {
    49         CbcCompareBase::operator=(rhs);
    50     }
    51     return *this;
    52 }
    53 
    54 // Destructor
    55 CbcCompareDepth::~CbcCompareDepth ()
    56 {
    57 }
    58 
    59 // Returns true if y better than x
    60 bool
    61 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     else
    68         return equalityTest(x, y); // so ties will be broken in consistent manner
    69 }
    70 // Create C++ lines to get to current state
    71 void
    72 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 Constructor
    80 
    81 */
    82 CbcCompareObjective::CbcCompareObjective ()
    83         : CbcCompareBase()
    84 {
    85     test_ = this;
    86 }
    87 
    88 // Copy constructor
    89 CbcCompareObjective::CbcCompareObjective ( const CbcCompareObjective & rhs)
    90         : CbcCompareBase(rhs)
    91 
    92 {
    93 }
    94 
    95 // Clone
    96 CbcCompareBase *
    97 CbcCompareObjective::clone() const
    98 {
    99     return new CbcCompareObjective(*this);
    100 }
    101 
    102 // Assignment operator
    103 CbcCompareObjective &
    104 CbcCompareObjective::operator=( const CbcCompareObjective & rhs)
    105 {
    106     if (this != &rhs) {
    107         CbcCompareBase::operator=(rhs);
    108     }
    109     return *this;
    110 }
    111 
    112 // Destructor
    113 CbcCompareObjective::~CbcCompareObjective ()
    114 {
    115 }
    116 
    117 // Returns true if y better than x
    118 bool
    119 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     else
    126         return equalityTest(x, y); // so ties will be broken in consistent manner
    127 }
    128 // Create C++ lines to get to current state
    129 void
    130 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 Constructor
    139 
    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 weight
    155 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 constructor
    170 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 // Clone
    184 CbcCompareBase *
    185 CbcCompareDefault::clone() const
    186 {
    187     return new CbcCompareDefault(*this);
    188 }
    189 
    190 // Assignment operator
    191 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 // Destructor
    208 CbcCompareDefault::~CbcCompareDefault ()
    209 {
    210 }
    211 
    212 // Returns true if y better than x
    213 bool
    214 CbcCompareDefault::test (CbcNode * x, CbcNode * y)
    215 {
    216 #if 0
    217     // 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         else
    224             return equalityTest(x, y); // so ties will be broken in consistent manner
    225     }
    226     if (weight_ == -1.0 || weight_ == -3.0) {
    227         int adjust =  (weight_ == -3.0) ? 10000 : 0;
    228         // before solution
    229         /*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             else
    242                 return equalityTest(x, y); // so ties will be broken in consistent manner
    243         }
    244     } else {
    245         // after solution
    246         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         else
    252             return equalityTest(x, y); // so ties will be broken in consistent manner
    253     }
    254 #else
    255     //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 solution
    259         /*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             else
    272                 return equalityTest(x, y); // so ties will be broken in consistent manner
    273         }
    274     } else {
    275         // always choose *greatest* depth if both <= breadthDepth_ otherwise <= breadthDepth_ if just one
    276         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.999
    293 #define TRY_THIS 0
    294 #if TRY_THIS==0
    295         double weight = CoinMax(weight_, 1.0e-9);
    296         double testX =  x->objectiveValue() + weight * x->numberUnsatisfied();
    297         double testY = y->objectiveValue() + weight * y->numberUnsatisfied();
    298 #elif TRY_THIS==1
    299     /* compute what weight would have to be to hit target
    300        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==2
    310     // Use estimates
    311     double testX = x->guessedObjectiveValue();
    312     double testY = y->guessedObjectiveValue();
    313 #elif TRY_THIS==3
    314 #define THRESH 0.95
    315     // Use estimates
    316     double testX = x->guessedObjectiveValue();
    317     double testY = y->guessedObjectiveValue();
    318     if (x->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
    319         testX *= 2.0; // make worse
    320     if (y->objectiveValue() - bestPossible_ > THRESH*(cutoff_ - bestPossible_))
    321         testY *= 2.0; // make worse
    322 #endif
    323         if (testX != testY)
    324             return testX > testY;
    325         else
    326             return equalityTest(x, y); // so ties will be broken in consistent manner
    327     }
    328 #endif
    329 }
    330 // This allows method to change behavior as it is called
    331 // after each solution
    332 void
    333 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 rounding
    341     // set to get close to this solution
    342     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 objective
    350 }
    351 // This allows method to change behavior
    352 bool
    353 CbcCompareDefault::every1000Nodes(CbcModel * model, int numberNodes)
    354 {
    355 #if 0
    356     // was
    357     if (numberNodes > 10000)
    358         weight_ = 0.0; // this searches on objective
    359     // get size of tree
    360     treeSize_ = model->tree()->size();
    361 #else
    362     double saveWeight = weight_;
    363     int numberNodes1000 = numberNodes / 1000;
    364     if (numberNodes > 10000) {
    365         weight_ = 0.0; // this searches on objective
    366         // but try a bit of other stuff
    367         if ((numberNodes1000 % 4) == 1)
    368             weight_ = saveWeight_;
    369     } else if (numberNodes == 1000 && weight_ == -2.0) {
    370         weight_ = -1.0; // Go to depth first
    371     }
    372     // get size of tree
    373     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 time
    379         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         else
    386             weight_ = saveWeight_;
    387     }
    388 #endif
    389     //return numberNodes==11000; // resort if first time
    390     return (weight_ != saveWeight);
    391 }
    392 
    393 // Create C++ lines to get to current state
    394 void
    395 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 Constructor
    406 
    407 */
    408 CbcCompareEstimate::CbcCompareEstimate ()
    409         : CbcCompareBase()
    410 {
    411     test_ = this;
    412 }
    413 
    414 // Copy constructor
    415 CbcCompareEstimate::CbcCompareEstimate ( const CbcCompareEstimate & rhs)
    416         : CbcCompareBase(rhs)
    417 
    418 {
    419 }
    420 
    421 // Clone
    422 CbcCompareBase *
    423 CbcCompareEstimate::clone() const
    424 {
    425     return new CbcCompareEstimate(*this);
    426 }
    427 
    428 // Assignment operator
    429 CbcCompareEstimate &
    430 CbcCompareEstimate::operator=( const CbcCompareEstimate & rhs)
    431 {
    432     if (this != &rhs) {
    433         CbcCompareBase::operator=(rhs);
    434     }
    435     return *this;
    436 }
    437 
    438 // Destructor
    439 CbcCompareEstimate::~CbcCompareEstimate ()
    440 {
    441 }
    442 
    443 // Returns true if y better than x
    444 bool
    445 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     else
    452         return equalityTest(x, y); // so ties will be broken in consistent manner
    453 }
    454 
    455 // Create C++ lines to get to current state
    456 void
    457 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.