Changeset 1362


Ignore:
Timestamp:
Dec 4, 2009 5:15:52 PM (9 years ago)
Author:
EdwinStraver
Message:

added Lou's comments

Location:
branches/sandbox/Cbc/src
Files:
6 edited

Legend:

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

    r1351 r1362  
    193193/* Pass in information on branch just done.
    194194   assumes object can get information from solver */
     195/*
     196  The expectation is that this method will be called after the branch has been
     197  imposed on the constraint system and resolve() has executed.
     198
     199  Note that the CbcBranchDecision is a property of the CbcModel. Note also that
     200  this method is reaching right through the CbcBranchingObject to update
     201  information in the underlying CbcObject. That's why we delete the
     202  branchingObject at the end of the method --- the next time we're called,
     203  the CbcObject will be different.
     204*/
    195205void
    196206CbcBranchDynamicDecision::updateInformation(OsiSolverInterface * solver,
     
    208218    //const double * lower = solver->getColLower();
    209219    //const double * upper = solver->getColUpper();
     220        /*
     221         Gain access to the associated CbcBranchingObject and its underlying
     222         CbcObject.
     223
     224         Seems like we'd want to distinguish between no branching object and a
     225         branching object of the wrong type. Just deleting an object of the wrong
     226         type hides many sins.
     227
     228         Hmmm ... if we're using the OSI side of the hierarchy, is this indicated by a
     229         null object_? Nah, then we have an assert failure off the top.
     230        */
     231
    210232    CbcDynamicPseudoCostBranchingObject * branchingObject =
    211233        dynamic_cast<CbcDynamicPseudoCostBranchingObject *>(object_);
     
    216238    }
    217239    CbcSimpleIntegerDynamicPseudoCost *  object = branchingObject->object();
    218     double change = CoinMax(0.0, objectiveValue - originalValue);
     240    /*
     241        change is the change in objective due to the branch we've just imposed. It's
     242        possible we may have gone infeasible.
     243        */
     244        double change = CoinMax(0.0, objectiveValue - originalValue);
    219245    // probably should also ignore if stopped
    220246    int iStatus;
     
    226252    else
    227253        iStatus = 1; // infeasible
    228 
     254        /*
     255          If we're feasible according to the solver, evaluate integer feasibility.
     256        */
    229257    bool feasible = iStatus != 1;
    230258    if (feasible) {
     
    240268        }
    241269    }
     270        /*
     271          Finally, update the object. Defaults (080104) are TYPE2 = 0, INFEAS = 1.
     272
     273          Pseudocosts are at heart the average of actual costs for a branch. We just
     274          need to update the information used to calculate that average.
     275        */
    242276    int way = object_->way();
    243277    double value = object_->value();
  • branches/sandbox/Cbc/src/CbcClique.hpp

    r1357 r1362  
    33#define CbcClique_H
    44
     5/** \brief Branching object for cliques
     6
     7  A clique is defined to be a set of binary variables where fixing any one
     8  variable to its `strong' value fixes all other variables. An example is the
     9  most common SOS1 construction: a set of binary variables x<j> s.t.  SUM{j}
     10  x<j> = 1.  Setting any one variable to 1 forces all other variables to 0.
     11  (See comments for CbcSOS below.)
     12
     13  Other configurations are possible, however: Consider x1-x2+x3 <= 0.
     14  Setting x1 (x3) to 1 forces x2 to 1 and x3 (x1) to 0. Setting x2 to 0
     15  forces x1 and x3 to 0.
     16
     17  The proper point of view to take when interpreting CbcClique is
     18  `generalisation of SOS1 on binary variables.' To get into the proper frame
     19  of mind, here's an example.
     20 
     21  Consider the following sequence, where x<i> = (1-y<i>):
     22     x1 + x2 + x3 <=  1         all strong at 1
     23     x1 - y2 + x3 <=  0         y2 strong at 0; x1, x3 strong at 1
     24    -y1 - y2 + x3 <= -1         y1, y2 strong at 0, x3 strong at 1
     25    -y1 - y2 - y3 <= -2         all strong at 0
     26  The first line is a standard SOS1 on binary variables.
     27 
     28  Variables with +1 coefficients are `SOS-style' and variables with -1
     29  coefficients are `non-SOS-style'. So numberNonSOSMembers_ simply tells you
     30  how many variables have -1 coefficients. The implicit rhs for a clique is
     31  1-numberNonSOSMembers_.
     32*/
     33
    534/// Define a clique class
    635
     
    1241    CbcClique ();
    1342
    14     /** Useful constructor (which are integer indices)
    15         slack can denote a slack in set.
    16         If type == NULL then as if 1
    17     */
     43  /** Useful constructor (which are integer indices) slack can denote a slack
     44  // Useful constructor (which are integer indices)
     45      in set.  If type == NULL then as if 1
     46  */
    1847    CbcClique (CbcModel * model, int cliqueType, int numberMembers,
    1948               const int * which, const char * type,
     
    4675        return numberMembers_;
    4776    }
    48 
    49     /// Number of Non SOS members i.e. fixing to zero is strong
     77        /** \brief Number of variables with -1 coefficient
     78         
     79          Original comment: Number of Non SOS members i.e. fixing to zero is strong.
     80          See comments at head of class, and comments for type_.
     81        */
     82
    5083    inline int numberNonSOSMembers() const {
    5184        return numberNonSOSMembers_;
     
    5790    }
    5891
    59     /** Type of each member i.e. which way is strong 0=non SOS, 1 =SOS,
    60         index is 0 ... numberMembers_-1 */
    61     inline char type(int index) const {
     92    /** \brief Type of each member, i.e. which way is strong
     93 
     94    This also specifies whether a variable has a +1 or -1 coefficient.
     95      0 => -1 coefficient, 0 is strong value
     96      1 -> +1 coefficient, 1 is strong value
     97    If unspecified, all coefficients are assumed to be positive.
     98   
     99    Indexed as 0 .. numberMembers_-1
     100    */
     101        inline char type(int index) const {
    62102        if (type_) return type_[index];
    63103        else return 1;
     
    82122    int * members_;
    83123
    84     /// Type of each member 0=SOS, 1 =clique
     124    /** \brief Strong value for each member.
     125
     126      This also specifies whether a variable has a +1 or -1 coefficient.
     127        0 => -1 coefficient, 0 is strong value
     128        1 -> +1 coefficient, 1 is strong value
     129      If unspecified, all coefficients are assumed to be positive.
     130   
     131      Indexed as 0 .. numberMembers_-1
     132    */
    85133    char * type_;
    86134
    87     /// Clique type - 0 <=, 1 ==
     135    /** \brief Clique type
     136
     137      0 defines a <= relation, 1 an equality. The assumed value of the rhs is
     138      numberNonSOSMembers_+1. (See comments for the class.)
     139    */
    88140    int cliqueType_;
    89141
    90     /// Which one is slack (if any) sequence within this set
     142    /** \brief Slack variable for the clique
     143 
     144      Identifies the slack variable for the clique (typically added to convert
     145      a <= relation to an equality). Value is sequence number within clique
     146      menbers.
     147    */
    91148    int slack_;
    92149};
  • branches/sandbox/Cbc/src/CbcCutGenerator.cpp

    r1336 r1362  
    178178CbcCutGenerator::generateCuts( OsiCuts & cs , int fullScan, OsiSolverInterface * solver, CbcNode * node)
    179179{
    180     int depth;
     180    /*
     181          Make some decisions about whether we'll generate cuts. First convert
     182          whenCutGenerator_ to a set of canonical values for comparison to the node
     183          count.
     184
     185                 0 <    mod 1000000, with a result of 0 forced to 1
     186           -99 <= <= 0  convert to 1
     187          -100 =        Off, period
     188        */
     189        int depth;
    181190    if (node)
    182191        depth = node->depth();
     
    203212    if (!pass)
    204213        savedCuts_ = OsiCuts();
    205     bool doThis = (model_->getNodeCount() % howOften) == 0;
    206     if (depthCutGenerator_ > 0) {
     214    /*
     215          Determine if we should generate cuts based on node count.
     216        */
     217        bool doThis = (model_->getNodeCount() % howOften) == 0;
     218    /*
     219          If the user has provided a depth specification, it will override the node
     220          count specification.
     221        */
     222        if (depthCutGenerator_ > 0) {
    207223        doThis = (depth % depthCutGenerator_) == 0;
    208224        if (depth < depthCutGenerator_)
    209225            doThis = true; // and also at top of tree
    210226    }
     227        /*
     228          A few magic numbers ...
     229
     230          The distinction between -100 and 100 for howOften is that we can override 100
     231          with fullScan. -100 means no cuts, period. As does the magic number -200 for
     232          whenCutGeneratorInSub_.
     233        */
     234
    211235    // But turn off if 100
    212236    if (howOften == 100)
  • branches/sandbox/Cbc/src/CbcSOS.cpp

    r1357 r1362  
    228228        }
    229229    }
     230        /* ?? */
    230231    preferredWay = 1;
     232/*
     233  SOS1 allows one nonzero; SOS2 allows two consecutive nonzeros. Infeasibility
     234  is calculated as (.5)(range of nonzero values)/(number of members). So if
     235  the first and last elements of the set are nonzero, we have maximum
     236  infeasibility.
     237*/
    231238    if (lastNonZero - firstNonZero >= sosType_) {
    232239        // find where to branch
  • branches/sandbox/Cbc/src/CbcSOS.hpp

    r1357 r1362  
    33#define CbcSOS_H
    44
    5 /** Define Special Ordered Sets of type 1 and 2.  These do not have to be
    6     integer - so do not appear in lists of integers.
    7 
    8     which_ points directly to columns of matrix
     5/** \brief Branching object for Special Ordered Sets of type 1 and 2.
     6
     7  SOS1 are an ordered set of variables where at most one variable can be
     8  non-zero. SOS1 are commonly defined with binary variables (interpreted as
     9  selection between alternatives) but this is not necessary.  An SOS1 with
     10  all binary variables is a special case of a clique (setting any one
     11  variable to 1 forces all others to 0).
     12
     13  In theory, the implementation makes no assumptions about integrality in
     14  Type 1 sets. In practice, there are places where the code seems to have been
     15  written with a binary SOS mindset. Current development of SOS branching
     16  objects is proceeding in OsiSOS.
     17
     18  SOS2 are an ordered set of variables in which at most two consecutive
     19  variables can be non-zero and must sum to 1 (interpreted as interpolation
     20  between two discrete values). By definition the variables are non-integer.
    921*/
    10 
    1122
    1223class CbcSOS : public CbcObject {
     
    1728    CbcSOS ();
    1829
    19     /** Useful constructor - which are indices
    20         and  weights are also given.  If null then 0,1,2..
    21         type is SOS type
    22     */
     30        /** \brief Constructor with SOS type and member information
     31
     32    Type specifies SOS 1 or 2. Identifier is an arbitrary value.
     33
     34    Which should be an array of variable indices with numberMembers entries.
     35    Weights can be used to assign arbitrary weights to variables, in the order
     36    they are specified in which. If no weights are provided, a default array of
     37    0, 1, 2, ... is generated.
     38        */
     39
    2340    CbcSOS (CbcModel * model, int numberMembers,
    2441            const int * which, const double * weights, int identifier,
     
    126143    /// Members (indices in range 0 ... numberColumns-1)
    127144    int * members_;
    128     /// Weights
     145  /** \brief Weights for individual members
     146
     147    Arbitrary weights for members. Can be used to attach meaning to variable
     148    values independent of objective coefficients. For example, if the SOS set
     149    comprises binary variables used to choose a facility of a given size, the
     150    weight could be the corresponding facilty size. Fractional values of the
     151    SOS variables can then be used to estimate ideal facility size.
     152
     153    Weights cannot be completely arbitrary. From the code, they must be
     154    differ by at least 1.0e-7
     155  */
     156
    129157    double * weights_;
    130158    /// Current pseudo-shadow price estimate down
  • branches/sandbox/Cbc/src/CbcSimpleIntegerDynamicPseudoCost.cpp

    r1357 r1362  
    571571    }
    572572    assert (breakEven_ > 0.0 && breakEven_ < 1.0);
     573        /*
     574          Find nearest integer, and integers above and below current value.
     575
     576          Given that we've already forced value within bounds, if
     577          (current value)+(integer tolerance) > (upper bound)
     578          shouldn't we declare this variable integer?
     579        */
     580
    573581    double value = solution[columnNumber_];
    574582    value = CoinMax(value, lower[columnNumber_]);
     
    586594    }
    587595#if INFEAS==1
     596/*
     597  Why do we inflate the distance to the cutoff by a factor of 10 for
     598  values that could be considered reachable? Why do we add 100 for values
     599  larger than 1e20?
     600*/
    588601    double distanceToCutoff = 0.0;
    589602    double objectiveValue = model_->getCurrentMinimizationObjValue();
Note: See TracChangeset for help on using the changeset viewer.