Ignore:
Timestamp:
Dec 10, 2009 10:17:35 AM (10 years ago)
Author:
caphillSNL
Message:

Start at adding documentation, removing magic numbers, removing dead code, etc.
Added an enum for type in classes derived from CbCBranchingObject. It's safer,
handier for debugging (inspection in a debugger), and clearly shows the relationship
between the dozen or so special numbers. Numbers are the same as they were before to
ensure no changes in correctness.

Location:
branches/sandbox
Files:
18 edited

Legend:

Unmodified
Added
Removed
  • branches/sandbox

    • Property svn:externals
      •  

        old new  
        55ThirdParty/Glpk   https://projects.coin-or.org/svn/BuildTools/ThirdParty/Glpk/stable/1.5
        66Data/Sample       https://projects.coin-or.org/svn/Data/stable/1.0/Sample
         7Data/Miplib       https://projects.coin-or.org/svn/Data/stable/1.0/miplib3
        78CoinUtils         https://projects.coin-or.org/svn/CoinUtils/stable/2.6/CoinUtils
        89Cgl               https://projects.coin-or.org/svn/Cgl/branches/sandbox/Cgl
  • branches/sandbox/Cbc/src/CbcBranchCut.hpp

    r1351 r1389  
    137137    virtual double branch();
    138138
    139 #if 0
    140     // No need to override. Default works fine.
    141     /** Reset every information so that the branching object appears to point to
    142         the previous child. This method does not need to modify anything in any
    143         solver. */
    144     virtual void previousBranch();
    145 #endif
    146 
    147139    using CbcBranchingObject::print ;
    148140    /** \brief Print something about branch - only if log level high
     
    155147
    156148    /** Return the type (an integer identifier) of \c this */
    157     virtual int type() const {
    158         return 200;
     149    virtual CbcBranchObjType type() const {
     150        return CutBranchingObj;
    159151    }
    160152
  • branches/sandbox/Cbc/src/CbcBranchDefaultDecision.cpp

    r1357 r1389  
    234234        // Uncomment next to force method 4
    235235        //method=4;
     236
     237        // FIXME This should be an enum.  It will be easier to
     238        // understand in the code than numbers.
    236239        /* Methods :
    237240           0 - fewest infeasibilities
  • branches/sandbox/Cbc/src/CbcBranchDynamic.cpp

    r1362 r1389  
    1919#include "CoinSort.hpp"
    2020#include "CoinError.hpp"
     21
     22// Removing magic constants.
     23
     24// This is a very small number, added to something to make sure it's non-zero.
     25// Useful, for example in denominators of ratios to avoid any possible division by zero
     26# define nonZeroAmount 1.0e-30
     27
     28// Increasing the size of an array when it grows to the end of its alloted space.
     29// In this file, only used for the history of the outcome of a branch.
     30// New size is   size_scale_numerator* <old value> / size_scale_denominator + additive_size_increase.
     31
     32#define size_scale_numerator 3
     33#define size_scale_denominator 2
     34#define additive_size_increase 100
     35
     36// Explanation of options used in this file
     37
     38// TYPE2 defines a strategy for computing pseudocosts
     39// 0 means to just use the absolute change in objective
     40// 1 means use the relative change in objective
     41// 2 means use a convex combination of absolute and relative objective changes
     42
     43// For option 2 (TYPE2 == 2), the specific combination is controlled by TYPERATIO
     44// Includes a TYPERATIO fraction of the absolute change and (1 - TYPERATIO) fraction of
     45// the relative change.  So should in general have 0 <= TYPERATIO <= 1.  But for the
     46// equality cases, you're better off using the other strategy (TYPE2) options.
     47
    2148#ifdef COIN_DEVELOP
    2249typedef struct {
     
    4067{
    4168    if (numberHistory == maxHistory) {
    42         maxHistory = 100 + (3 * maxHistory) / 2;
     69      // This was originally 3 * maxHistory/2 + 100
     70        maxHistory = additive_size_increase + (size_scale_numerator * maxHistory) / size_scale_denominator;
    4371        History * temp = new History [maxHistory];
    4472        memcpy(temp, history, numberHistory*sizeof(History));
     
    244272        double change = CoinMax(0.0, objectiveValue - originalValue);
    245273    // probably should also ignore if stopped
     274        // FIXME. Could use enum to avoid numbers for iStatus (e.g. optimal, unknown, infeasible)
    246275    int iStatus;
    247276    if (solver->isProvenOptimal())
     
    285314            //printf("(down change %g value down %g ",change,movement);
    286315            object->incrementNumberTimesDown();
    287             object->addToSumDownChange(1.0e-30 + movement);
     316            object->addToSumDownChange(nonZeroAmount + movement);
    288317            object->addToSumDownDecrease(originalUnsatisfied - unsatisfied);
    289318#if TYPE2==0
    290             object->addToSumDownCost(change / (1.0e-30 + movement));
     319            object->addToSumDownCost(change / (nonZeroAmount + movement));
    291320            object->setDownDynamicPseudoCost(object->sumDownCost() /
    292321                                             static_cast<double> (object->numberTimesDown()));
     
    295324            object->setDownDynamicPseudoCost(object->sumDownCost() / object->sumDownChange());
    296325#elif TYPE2==2
    297             object->addToSumDownCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (1.0e-30 + movement));
     326            object->addToSumDownCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (nonZeroAmount + movement));
    298327            object->setDownDynamicPseudoCost(object->sumDownCost()*(TYPERATIO / object->sumDownChange() + (1.0 - TYPERATIO) / (double) object->numberTimesDown()));
    299328#endif
     
    311340                change = object->downDynamicPseudoCost() * movement * 10.0;
    312341            change = CoinMax(1.0e-12 * (1.0 + fabs(originalValue)), change);
    313             object->addToSumDownChange(1.0e-30 + movement);
     342            object->addToSumDownChange(nonZeroAmount + movement);
    314343            object->addToSumDownDecrease(originalUnsatisfied - unsatisfied);
    315344#if TYPE2==0
    316             object->addToSumDownCost(change / (1.0e-30 + movement));
     345            object->addToSumDownCost(change / (nonZeroAmount + movement));
    317346            object->setDownDynamicPseudoCost(object->sumDownCost() / (double) object->numberTimesDown());
    318347#elif TYPE2==1
     
    320349            object->setDownDynamicPseudoCost(object->sumDownCost() / object->sumDownChange());
    321350#elif TYPE2==2
    322             object->addToSumDownCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (1.0e-30 + movement));
     351            object->addToSumDownCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (nonZeroAmount + movement));
    323352            object->setDownDynamicPseudoCost(object->sumDownCost()*(TYPERATIO / object->sumDownChange() + (1.0 - TYPERATIO) / (double) object->numberTimesDown()));
    324353#endif
     
    332361            //printf("(up change %g value down %g ",change,movement);
    333362            object->incrementNumberTimesUp();
    334             object->addToSumUpChange(1.0e-30 + movement);
     363            object->addToSumUpChange(nonZeroAmount + movement);
    335364            object->addToSumUpDecrease(unsatisfied - originalUnsatisfied);
    336365#if TYPE2==0
    337             object->addToSumUpCost(change / (1.0e-30 + movement));
     366            object->addToSumUpCost(change / (nonZeroAmount + movement));
    338367            object->setUpDynamicPseudoCost(object->sumUpCost() /
    339368                                           static_cast<double> (object->numberTimesUp()));
     
    342371            object->setUpDynamicPseudoCost(object->sumUpCost() / object->sumUpChange());
    343372#elif TYPE2==2
    344             object->addToSumUpCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (1.0e-30 + movement));
     373            object->addToSumUpCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (nonZeroAmount + movement));
    345374            object->setUpDynamicPseudoCost(object->sumUpCost()*(TYPERATIO / object->sumUpChange() + (1.0 - TYPERATIO) / (double) object->numberTimesUp()));
    346375#endif
     
    358387                change = object->upDynamicPseudoCost() * movement * 10.0;
    359388            change = CoinMax(1.0e-12 * (1.0 + fabs(originalValue)), change);
    360             object->addToSumUpChange(1.0e-30 + movement);
     389            object->addToSumUpChange(nonZeroAmount + movement);
    361390            object->addToSumUpDecrease(unsatisfied - originalUnsatisfied);
    362391#if TYPE2==0
    363             object->addToSumUpCost(change / (1.0e-30 + movement));
     392            object->addToSumUpCost(change / (nonZeroAmount + movement));
    364393            object->setUpDynamicPseudoCost(object->sumUpCost() / (double) object->numberTimesUp());
    365394#elif TYPE2==1
     
    367396            object->setUpDynamicPseudoCost(object->sumUpCost() / object->sumUpChange());
    368397#elif TYPE2==2
    369             object->addToSumUpCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (1.0e-30 + movement));
     398            object->addToSumUpCost(change*TYPERATIO + (1.0 - TYPERATIO)*change / (nonZeroAmount + movement));
    370399            object->setUpDynamicPseudoCost(object->sumUpCost()*(TYPERATIO / object->sumUpChange() + (1.0 - TYPERATIO) / (double) object->numberTimesUp()));
    371400#endif
  • branches/sandbox/Cbc/src/CbcBranchDynamic.hpp

    r1351 r1389  
    183183
    184184    /** Return the type (an integer identifier) of \c this */
    185     virtual int type() const {
    186         return 400;
     185    virtual CbcBranchObjType type() const {
     186        return DynamicPseudoCostBranchObj;
    187187    }
    188188
  • branches/sandbox/Cbc/src/CbcBranchLotsize.cpp

    r1351 r1389  
    2020/*
    2121  CBC_PRINT 1 just does sanity checks - no printing
    22             2
     22  Larger values of CBC_PRINT set various printing levels.  Larger
     23  values print more.
    2324*/
    2425//#define CBC_PRINT 1
  • branches/sandbox/Cbc/src/CbcBranchLotsize.hpp

    r1351 r1389  
    106106    */
    107107    virtual int columnNumber() const;
    108     /// Original bounds
     108    /// Original variable bounds
    109109    inline double originalLowerBound() const {
    110110        return bound_[0];
     
    206206    virtual double branch();
    207207
    208 #if 0
    209     // No need to override. Default works fine.
    210     /** Reset every information so that the branching object appears to point to
    211         the previous child. This method does not need to modify anything in any
    212         solver. */
    213     virtual void previousBranch();
    214 #endif
    215 
    216208    using CbcBranchingObject::print ;
    217209    /** \brief Print something about branch - only if log level high
     
    220212
    221213    /** Return the type (an integer identifier) of \c this */
    222     virtual int type() const {
    223         return 300;
     214    virtual CbcBranchObjType type() const {
     215        return LotsizeBranchObj;
    224216    }
    225217
  • branches/sandbox/Cbc/src/CbcBranchToFixLots.hpp

    r1357 r1389  
    4848    /** Does a lot of the work,
    4949        Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
     50        FIXME: should use enum or equivalent to make these numbers clearer.
    5051    */
    5152    int shallWe() const;
    5253
    53     /// Infeasibility - large is 0.5
     54    /// Infeasibility for an integer variable - large is 0.5, but also can be infinity when known infeasible.
    5455    virtual double infeasibility(const OsiBranchingInformation * info,
    5556                                 int &preferredWay) const;
  • branches/sandbox/Cbc/src/CbcBranchingObject.hpp

    r1357 r1389  
    88#include "OsiBranchingObject.hpp"
    99
     10
     11// The types of objects that will be derived from this class.
     12enum CbcBranchObjType
     13  {
     14    SimpleIntegerBranchObj = 100,
     15    SimpleIntegerDynamicPseudoCostBranchObj = 101,
     16    CliqueBranchObj = 102,
     17    LongCliqueBranchObj = 103,
     18    SoSBranchObj = 104,
     19    NWayBranchObj = 105,
     20    FollowOnBranchObj = 106,
     21    DummyBranchObj = 107,
     22    GeneralDepthBranchObj = 108,
     23    OneGeneralBranchingObj = 110,
     24    CutBranchingObj = 200,
     25    LotsizeBranchObj = 300,
     26    DynamicPseudoCostBranchObj = 400
     27  };
     28
    1029/** \brief Abstract branching object base class
    1130    Now just difference with OsiBranchingObject
     
    4968
    5069    /** Some branchingObjects may claim to be able to skip
    51         strong branching.  If so they ahve to fill in CbcStrongInfo.
     70        strong branching.  If so they have to fill in CbcStrongInfo.
    5271        The object mention in incoming CbcStrongInfo must match.
    5372        Returns nonzero if skip is wanted */
     
    155174    // Methods used in heuristics
    156175
    157     /** Return the type (an integer identifier) of \c this */
    158     virtual int type() const = 0;
     176    /** Return the type (an integer identifier) of \c this.
     177        See definition of CbcBranchObjType above for possibilities
     178    */
     179   
     180    virtual CbcBranchObjType type() const = 0;
    159181
    160182    /** Compare the original object of \c this with the original object of \c
     
    170192    }
    171193
    172     /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     194    /** Compare the \c this with \c brObj. \c this and \c brObj must be of the
    173195        same type and must have the same original object, but they may have
    174196        different feasible regions.
  • branches/sandbox/Cbc/src/CbcChooseVariable.hpp

    r1357 r1389  
    99*/
    1010
     11// FIXME: Do we want to define UP and DOWN constants (1 and -1) for clarity?
    1112class CbcChooseVariable {
    1213public:
  • branches/sandbox/Cbc/src/CbcClique.hpp

    r1362 r1389  
    186186    virtual double branch();
    187187
    188 #if 0
    189     // No need to override. Default works fine.
    190     /** Reset every information so that the branching object appears to point to
    191         the previous child. This method does not need to modify anything in any
    192         solver. */
    193     virtual void previousBranch();
    194 #endif
    195 
    196188    using CbcBranchingObject::print ;
    197189    /** \brief Print something about branch - only if log level high
     
    200192
    201193    /** Return the type (an integer identifier) of \c this */
    202     virtual int type() const {
    203         return 102;
     194    virtual CbcBranchObjType type() const {
     195        return CliqueBranchObj;
     196    }
     197
     198    /** Compare the original object of \c this with the original object of \c
     199        brObj. Assumes that there is an ordering of the original objects.
     200        This method should be invoked only if \c this and brObj are of the same
     201        type.
     202        Return negative/0/positive depending on whether \c this is
     203        smaller/same/larger than the argument.
     204    */
     205    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     206
     207    /** Compare the \c this with \c brObj. \c this and \c brObj must be of the
     208        same type and must have the same original object, but they may have
     209        different feasible regions.
     210        Return the appropriate CbcRangeCompare value (first argument being the
     211        sub/superset if that's the case). In case of overlap (and if \c
     212        replaceIfOverlap is true) replace the current branching object with one
     213        whose feasible region is the overlap.
     214     */
     215    virtual CbcRangeCompare compareBranchingObject
     216    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     217
     218private:
     219    /// data
     220    const CbcClique * clique_;
     221    /// downMask - bit set to fix to weak bounds, not set to leave unfixed
     222    unsigned int downMask_[2];
     223    /// upMask - bit set to fix to weak bounds, not set to leave unfixed
     224    unsigned int upMask_[2];
     225};
     226
     227/** Unordered Clique Branching Object class.
     228    These are for cliques which are > 64 members
     229    Variable is number of clique.
     230 */
     231class CbcLongCliqueBranchingObject : public CbcBranchingObject {
     232
     233public:
     234
     235    // Default Constructor
     236    CbcLongCliqueBranchingObject ();
     237
     238    // Useful constructor
     239    CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
     240                                  int way,
     241                                  int numberOnDownSide, const int * down,
     242                                  int numberOnUpSide, const int * up);
     243
     244    // Copy constructor
     245    CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
     246
     247    // Assignment operator
     248    CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
     249
     250    /// Clone
     251    virtual CbcBranchingObject * clone() const;
     252
     253    // Destructor
     254    virtual ~CbcLongCliqueBranchingObject ();
     255
     256    using CbcBranchingObject::branch ;
     257    /// Does next branch and updates state
     258    virtual double branch();
     259
     260    using CbcBranchingObject::print ;
     261    /** \brief Print something about branch - only if log level high
     262    */
     263    virtual void print();
     264
     265    /** Return the type (an integer identifier) of \c this */
     266    virtual CbcBranchObjType type() const {
     267        return LongCliqueBranchObj;
    204268    }
    205269
     
    228292    const CbcClique * clique_;
    229293    /// downMask - bit set to fix to weak bounds, not set to leave unfixed
    230     unsigned int downMask_[2];
    231     /// upMask - bit set to fix to weak bounds, not set to leave unfixed
    232     unsigned int upMask_[2];
    233 };
    234 
    235 /** Unordered Clique Branching Object class.
    236     These are for cliques which are > 64 members
    237     Variable is number of clique.
    238  */
    239 class CbcLongCliqueBranchingObject : public CbcBranchingObject {
    240 
    241 public:
    242 
    243     // Default Constructor
    244     CbcLongCliqueBranchingObject ();
    245 
    246     // Useful constructor
    247     CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
    248                                   int way,
    249                                   int numberOnDownSide, const int * down,
    250                                   int numberOnUpSide, const int * up);
    251 
    252     // Copy constructor
    253     CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
    254 
    255     // Assignment operator
    256     CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
    257 
    258     /// Clone
    259     virtual CbcBranchingObject * clone() const;
    260 
    261     // Destructor
    262     virtual ~CbcLongCliqueBranchingObject ();
    263 
    264     using CbcBranchingObject::branch ;
    265     /// Does next branch and updates state
    266     virtual double branch();
    267 
    268 #if 0
    269     // No need to override. Default works fine.
    270     /** Reset every information so that the branching object appears to point to
    271         the previous child. This method does not need to modify anything in any
    272         solver. */
    273     virtual void previousBranch();
    274 #endif
    275 
    276     using CbcBranchingObject::print ;
    277     /** \brief Print something about branch - only if log level high
    278     */
    279     virtual void print();
    280 
    281     /** Return the type (an integer identifier) of \c this */
    282     virtual int type() const {
    283         return 103;
    284     }
    285 
    286     /** Compare the original object of \c this with the original object of \c
    287         brObj. Assumes that there is an ordering of the original objects.
    288         This method should be invoked only if \c this and brObj are of the same
    289         type.
    290         Return negative/0/positive depending on whether \c this is
    291         smaller/same/larger than the argument.
    292     */
    293     virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
    294 
    295     /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
    296         same type and must have the same original object, but they may have
    297         different feasible regions.
    298         Return the appropriate CbcRangeCompare value (first argument being the
    299         sub/superset if that's the case). In case of overlap (and if \c
    300         replaceIfOverlap is true) replace the current branching object with one
    301         whose feasible region is the overlap.
    302      */
    303     virtual CbcRangeCompare compareBranchingObject
    304     (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
    305 
    306 private:
    307     /// data
    308     const CbcClique * clique_;
    309     /// downMask - bit set to fix to weak bounds, not set to leave unfixed
    310294    unsigned int * downMask_;
    311295    /// upMask - bit set to fix to weak bounds, not set to leave unfixed
  • branches/sandbox/Cbc/src/CbcDummyBranchingObject.hpp

    r1357 r1389  
    4848
    4949    /** Return the type (an integer identifier) of \c this */
    50     virtual int type() const {
    51         return 107;
     50    virtual CbcBranchObjType type() const {
     51        return DummyBranchObj;
    5252    }
    5353
  • branches/sandbox/Cbc/src/CbcFollowOn.hpp

    r1357 r1389  
    107107
    108108    /** Return the type (an integer identifier) of \c this */
    109     virtual int type() const {
    110         return 106;
     109    virtual CbcBranchObjType type() const {
     110        return FollowOnBranchObj;
    111111    }
    112112
  • branches/sandbox/Cbc/src/CbcGeneralDepth.hpp

    r1357 r1389  
    135135    }
    136136    /** Return the type (an integer identifier) of \c this */
    137     virtual int type() const {
    138         return 108;
     137    virtual CbcBranchObjType type() const {
     138        return GeneralDepthBranchObj;
    139139    }
    140140
     
    234234    virtual void print();
    235235    /** Return the type (an integer identifier) of \c this */
    236     virtual int type() const {
    237         return 110;
     236    virtual CbcBranchObjType type() const {
     237        return OneGeneralBranchingObj;
    238238    }
    239239
  • branches/sandbox/Cbc/src/CbcNWay.hpp

    r1357 r1389  
    126126
    127127    /** Return the type (an integer identifier) of \c this */
    128     virtual int type() const {
    129         return 105;
     128    virtual CbcBranchObjType type() const {
     129        return NWayBranchObj;
    130130    }
    131131
  • branches/sandbox/Cbc/src/CbcSOS.hpp

    r1362 r1389  
    228228
    229229    /** Return the type (an integer identifier) of \c this */
    230     virtual int type() const {
    231         return 104;
     230    virtual CbcBranchObjType type() const {
     231        return SoSBranchObj;
    232232    }
    233233
  • branches/sandbox/Cbc/src/CbcSimpleInteger.hpp

    r1357 r1389  
    121121
    122122    /** Return the type (an integer identifier) of \c this */
    123     virtual int type() const {
    124         return 100;
     123    virtual CbcBranchObjType type() const {
     124        return SimpleIntegerBranchObj;
    125125    }
    126126
  • branches/sandbox/Cbc/src/CbcSimpleIntegerDynamicPseudoCost.hpp

    r1357 r1389  
    437437
    438438    /** Return the type (an integer identifier) of \c this */
    439     virtual int type() const {
    440         return 101;
     439    virtual CbcBranchObjType type() const {
     440        return SimpleIntegerDynamicPseudoCostBranchObj;
    441441    }
    442442
Note: See TracChangeset for help on using the changeset viewer.