Changeset 1265 for branches


Ignore:
Timestamp:
Oct 31, 2009 4:09:29 PM (10 years ago)
Author:
lou
Message:

BUILDABLE. Fold in additional comments (in varying amount) for about 20 cbc
source files.

Location:
branches/reengAnn/Cbc/src
Files:
23 edited

Legend:

Unmodified
Added
Removed
  • branches/reengAnn/Cbc/src/CbcBranchActual.cpp

    r1232 r1265  
    123123  delete [] type_;
    124124}
     125/*
     126  Unfortunately, that comment is untrue. And there are other issues. This
     127  routine is clearly an unfinished work.
     128*/
    125129double
    126130CbcClique::infeasibility(const OsiBranchingInformation * /*info*/,
     
    138142    model_->getDblParam(CbcModel::CbcIntegerTolerance);
    139143  double * sort = new double[numberMembers_];
    140 
     144/*
     145  Calculate integer infeasibility and fill an array. Pick off the infeasibility
     146  of the slack and the max infeasibility while we're at it. You can see here
     147  the conversion of `non-SOS' (strong value of 0, negative coefficient) to
     148  `SOS' (strong value of 1, positive coefficient). Also count the number of
     149  variables that have integral values but are not fixed.
     150*/
    141151  double slackValue=0.0;
    142152  for (j=0;j<numberMembers_;j++) {
     
    160170    }
    161171  }
     172/*
     173  preferredWay will not change. The calculation of otherWay is an expensive
     174  noop --- value is ultimately unused. Same for the sort of sort. It looks like
     175  there was some notion of branching by splitting the set using even and odd
     176  indices (as opposed to first and second half).
     177*/
    162178  preferredWay=1;
    163179  double otherWay = 0.0;
     
    170186    }
    171187    // Need to think more
     188/*
     189  Here we have the actual infeasibility calculation. Most previous work is
     190  discarded, and we calculate a value using various counts, adjusted by the
     191  max value and slack value. This is not scaled to [0, .5].
     192*/
    172193    double value = 0.2*numberUnsatis+0.01*(numberMembers_-numberFree);
    173194    if (fabs(largestValue-0.5)<0.1) {
     
    392413    // sort so weights increasing
    393414    CoinSort_2(weights_,weights_+numberMembers_,members_);
     415/*
     416  Force all weights to be distinct; note that the separation enforced here
     417  (1.0e-10) is not sufficien to pass the test in infeasibility().
     418*/
    394419    double last = -COIN_DBL_MAX;
    395420    int i;
     
    473498  delete [] weights_;
    474499}
     500
     501/*
     502  Routine to calculate standard infeasibility of an SOS set and return a
     503  preferred branching direction. This routine looks to have undergone
     504  incomplete revision. There is vestigial code. preferredWay is unconditionally
     505  set to 1. There used to be a comment `large is 0.5' but John removed it
     506  at some point. Have to check to see if it no longer applies or if John
     507  thought it provided too much information.
     508*/
    475509double
    476510CbcSOS::infeasibility(const OsiBranchingInformation * info,
     
    494528  for (j=0;j<numberMembers_;j++) {
    495529    int iColumn = members_[j];
     530/*
     531  The value used here (1.0e-7) is larger than the value enforced in the
     532  constructor.
     533*/
    496534    if (lastWeight>=weights_[j]-1.0e-7)
    497535      throw CoinError("Weights too close together in SOS","infeasibility","CbcSOS");
    498536    double value = CoinMax(0.0,solution[iColumn]);
    499537    sum += value;
     538/*
     539  If we're not making assumptions about integrality, why check integerTolerance
     540  here? Convenient tolerance? Why not just check against the upper bound?
     541
     542  The calculation of weight looks to be a relic --- in the end, the value isn't
     543  used to calculate either the return value or preferredWay.
     544*/
    500545    if (value>integerTolerance&&upper[iColumn]) {
    501546      // Possibly due to scaling a fixed variable might slip through
     
    515560    }
    516561  }
     562/* ?? */
    517563  preferredWay=1;
     564/*
     565  SOS1 allows one nonzero; SOS2 allows two consecutive nonzeros. Infeasibility
     566  is calculated as (.5)(range of nonzero values)/(number of members). So if
     567  the first and last elements of the set are nonzero, we have maximum
     568  infeasibility.
     569*/
    518570  if (lastNonZero-firstNonZero>=sosType_) {
    519571    // find where to branch
  • branches/reengAnn/Cbc/src/CbcBranchActual.hpp

    r1205 r1265  
    88#include "CoinPackedMatrix.hpp"
    99class CbcIntegerBranchingObject;
    10 /// Define a clique class
    11 
     10/** \brief Branching object for cliques
     11
     12  A clique is defined to be a set of binary variables where fixing any one
     13  variable to its `strong' value fixes all other variables. An example is the
     14  most common SOS1 construction: a set of binary variables x<j> s.t.  SUM{j}
     15  x<j> = 1.  Setting any one variable to 1 forces all other variables to 0.
     16  (See comments for CbcSOS below.)
     17
     18  Other configurations are possible, however: Consider x1-x2+x3 <= 0.
     19  Setting x1 (x3) to 1 forces x2 to 1 and x3 (x1) to 0. Setting x2 to 0
     20  forces x1 and x3 to 0.
     21
     22  The proper point of view to take when interpreting CbcClique is
     23  `generalisation of SOS1 on binary variables.' To get into the proper frame
     24  of mind, here's an example.
     25 
     26  Consider the following sequence, where x<i> = (1-y<i>):
     27     x1 + x2 + x3 <=  1         all strong at 1
     28     x1 - y2 + x3 <=  0         y2 strong at 0; x1, x3 strong at 1
     29    -y1 - y2 + x3 <= -1         y1, y2 strong at 0, x3 strong at 1
     30    -y1 - y2 - y3 <= -2         all strong at 0
     31  The first line is a standard SOS1 on binary variables.
     32 
     33  Variables with +1 coefficients are `SOS-style' and variables with -1
     34  coefficients are `non-SOS-style'. So numberNonSOSMembers_ simply tells you
     35  how many variables have -1 coefficients. The implicit rhs for a clique is
     36  1-numberNonSOSMembers_.
     37*/
    1238
    1339class CbcClique : public CbcObject {
     
    1541public:
    1642
    17   // Default Constructor 
     43  // Default Constructor
    1844  CbcClique ();
    1945
    20   /** Useful constructor (which are integer indices)
    21       slack can denote a slack in set.
    22       If type == NULL then as if 1
     46  /** Useful constructor (which are integer indices) slack can denote a slack
     47      in set.  If type == NULL then as if 1
    2348  */
    2449  CbcClique (CbcModel * model, int cliqueType, int numberMembers,
     
    5277  {return numberMembers_;}
    5378
    54   /// Number of Non SOS members i.e. fixing to zero is strong
     79  /** \brief Number of variables with -1 coefficient
     80 
     81    Original comment: Number of Non SOS members i.e. fixing to zero is strong.
     82    See comments at head of class, and comments for type_.
     83  */
    5584  inline int numberNonSOSMembers() const
    5685  {return numberNonSOSMembers_;}
     
    6089  {return members_;}
    6190
    62   /** Type of each member i.e. which way is strong 0=non SOS, 1 =SOS,
    63       index is 0 ... numberMembers_-1 */
     91  /** \brief Type of each member, i.e. which way is strong
     92 
     93    This also specifies whether a variable has a +1 or -1 coefficient.
     94      0 => -1 coefficient, 0 is strong value
     95      1 -> +1 coefficient, 1 is strong value
     96    If unspecified, all coefficients are assumed to be positive.
     97   
     98    Indexed as 0 .. numberMembers_-1
     99  */
    64100  inline char type(int index) const
    65101  {if (type_) return type_[index]; else return 1;}
     
    82118  int * members_;
    83119
    84   /// Type of each member 0=SOS, 1 =clique
     120  /** \brief Strong value for each member.
     121
     122    This also specifies whether a variable has a +1 or -1 coefficient.
     123      0 => -1 coefficient, 0 is strong value
     124      1 -> +1 coefficient, 1 is strong value
     125    If unspecified, all coefficients are assumed to be positive.
     126   
     127    Indexed as 0 .. numberMembers_-1
     128  */
    85129  char * type_;
    86130
    87   /// Clique type - 0 <=, 1 ==
     131  /** \brief Clique type
     132
     133    0 defines a <= relation, 1 an equality. The assumed value of the rhs is
     134    numberNonSOSMembers_+1. (See comments for the class.)
     135  */
    88136   int cliqueType_;
    89137
    90   /// Which one is slack (if any) sequence within this set
     138  /** \brief Slack variable for the clique
     139 
     140    Identifies the slack variable for the clique (typically added to convert
     141    a <= relation to an equality). Value is sequence number within clique
     142    menbers.
     143  */
    91144  int slack_;
    92145};
    93146
    94 /** Define Special Ordered Sets of type 1 and 2.  These do not have to be
    95     integer - so do not appear in lists of integers.
    96    
    97     which_ points directly to columns of matrix
     147/** \brief Branching object for Special Ordered Sets of type 1 and 2.
     148
     149  SOS1 are an ordered set of variables where at most one variable can be
     150  non-zero. SOS1 are commonly defined with binary variables (interpreted as
     151  selection between alternatives) but this is not necessary.  An SOS1 with
     152  all binary variables is a special case of a clique (setting any one
     153  variable to 1 forces all others to 0).
     154
     155  In theory, the implementation makes no assumptions about integrality in
     156  Type 1 sets. In practice, there are places where the code seems to have been
     157  written with a binary SOS mindset. Current development of SOS branching
     158  objects is proceeding in OsiSOS.
     159
     160  SOS2 are an ordered set of variables in which at most two consecutive
     161  variables can be non-zero and must sum to 1 (interpreted as interpolation
     162  between two discrete values). By definition the variables are non-integer.
    98163*/
    99164
     
    103168public:
    104169
    105   // Default Constructor
     170  /// Default Constructor
    106171  CbcSOS ();
    107172
    108   /** Useful constructor - which are indices
    109       and  weights are also given.  If null then 0,1,2..
    110       type is SOS type
     173  /** \brief Constructor with SOS type and member information
     174
     175    Type specifies SOS 1 or 2. Identifier is an arbitrary value.
     176
     177    Which should be an array of variable indices with numberMembers entries.
     178    Weights can be used to assign arbitrary weights to variables, in the order
     179    they are specified in which. If no weights are provided, a default array of
     180    0, 1, 2, ... is generated.
    111181  */
    112182  CbcSOS (CbcModel * model, int numberMembers,
     
    204274  /// Members (indices in range 0 ... numberColumns-1)
    205275  int * members_;
    206   /// Weights
     276  /** \brief Weights for individual members
     277
     278    Arbitrary weights for members. Can be used to attach meaning to variable
     279    values independent of objective coefficients. For example, if the SOS set
     280    comprises binary variables used to choose a facility of a given size, the
     281    weight could be the corresponding facilty size. Fractional values of the
     282    SOS variables can then be used to estimate ideal facility size.
     283
     284    Weights cannot be completely arbitrary. From the code, they must be
     285    differ by at least 1.0e-7.
     286  */
    207287  double * weights_;
    208288  /// Current pseudo-shadow price estimate down
  • branches/reengAnn/Cbc/src/CbcBranchBase.hpp

    r1209 r1265  
    514514  inline CbcModel * cbcModel() const
    515515  { return model_;}
    516   /* If chooseMethod_ id non-null then the rest is fairly pointless
     516  /* If chooseMethod_ is non-null then the rest is fairly pointless
    517517     as choosemethod_ will be doing all work
     518
     519     This comment makes more sense if you realise that there's a conversion in
     520     process from the Cbc branching classes to Osi branching classes. The test
     521     for use of the Osi branching classes is CbcModel::branchingMethod_
     522     non-null (i.e., it points to one of these CbcBranchDecision objects) and
     523     that branch decision object has an OsiChooseVariable method set. In which
     524     case, we'll use it, rather than the choose[*]Variable methods defined in
     525     CbcNode.
    518526  */
    519527  OsiChooseVariable * chooseMethod() const
  • branches/reengAnn/Cbc/src/CbcBranchDynamic.cpp

    r1240 r1265  
    1010#include <cmath>
    1111#include <cfloat>
     12
     13
     14// Debug trace  (-lh-)
     15#define CBCBRDYN_DEBUG 0
     16
     17
    1218//#define CBC_DEBUG
    1319//#define TRACE_ONE 19
     20
    1421#include "OsiSolverInterface.hpp"
    1522#include "OsiSolverBranch.hpp"
     
    572579  }
    573580  assert (breakEven_>0.0&&breakEven_<1.0);
     581/*
     582  Find nearest integer, and integers above and below current value.
     583
     584  Given that we've already forced value within bounds, if
     585  (current value)+(integer tolerance) > (upper bound)
     586  shouldn't we declare this variable integer?
     587*/
    574588  double value = solution[columnNumber_];
    575589  value = CoinMax(value, lower[columnNumber_]);
     
    587601  }
    588602#if INFEAS==1
     603/*
     604  Why do we inflate the distance to the cutoff by a factor of 10 for
     605  values that could be considered reachable? Why do we add 100 for values
     606  larger than 1e20?
     607*/
    589608  double distanceToCutoff=0.0;
    590609  double objectiveValue = model_->getCurrentMinimizationObjValue();
     
    14961515/* Pass in information on branch just done.
    14971516   assumes object can get information from solver */
     1517/*
     1518  The expectation is that this method will be called after the branch has been
     1519  imposed on the constraint system and resolve() has executed.
     1520
     1521  Note that the CbcBranchDecision is a property of the CbcModel. Note also that
     1522  this method is reaching right through the CbcBranchingObject to update
     1523  information in the underlying CbcObject. That's why we delete the
     1524  branchingObject at the end of the method --- the next time we're called,
     1525  the CbcObject will be different.
     1526*/
    14981527void
    14991528CbcBranchDynamicDecision::updateInformation(OsiSolverInterface * solver,
    15001529                                            const CbcNode * node)
    15011530{
     1531# if CBCBRDYN_DEBUG > 0
     1532  std::cout
     1533    << "CbcBrDynDec::updateInformation: entering."
     1534    << " chooseMethod " << std::hex << chooseMethod_ << std::dec
     1535    << "." << std::endl ;
     1536# endif
    15021537  assert (object_);
    15031538  const CbcModel * model = object_->model();
     
    15111546  //const double * lower = solver->getColLower();
    15121547  //const double * upper = solver->getColUpper();
     1548/*
     1549 Gain access to the associated CbcBranchingObject and its underlying
     1550 CbcObject.
     1551
     1552 Seems like we'd want to distinguish between no branching object and a
     1553 branching object of the wrong type. Just deleting an object of the wrong
     1554 type hides many sins.
     1555
     1556 Hmmm ... if we're using the OSI side of the hierarchy, is this indicated by a
     1557 null object_? Nah, then we have an assert failure off the top.
     1558*/
    15131559  CbcDynamicPseudoCostBranchingObject * branchingObject =
    15141560    dynamic_cast<CbcDynamicPseudoCostBranchingObject *>(object_);
     
    15191565  }
    15201566  CbcSimpleIntegerDynamicPseudoCost *  object = branchingObject->object();
     1567/*
     1568  change is the change in objective due to the branch we've just imposed. It's
     1569  possible we may have gone infeasible.
     1570*/
    15211571  double change = CoinMax(0.0,objectiveValue-originalValue);
    15221572  // probably should also ignore if stopped
     
    15291579  else
    15301580    iStatus=1; // infeasible
    1531 
     1581/*
     1582  If we're feasible according to the solver, evaluate integer feasibility.
     1583*/
    15321584  bool feasible = iStatus!=1;
    15331585  if (feasible) {
     
    15431595    }
    15441596  }
     1597/*
     1598  Finally, update the object. Defaults (080104) are TYPE2 = 0, INFEAS = 1.
     1599
     1600  Pseudocosts are at heart the average of actual costs for a branch. We just
     1601  need to update the information used to calculate that average.
     1602*/
    15451603  int way = object_->way();
    15461604  double value = object_->value();
  • branches/reengAnn/Cbc/src/CbcCutGenerator.cpp

    r1263 r1265  
    2323#include "CglProbing.hpp"
    2424#include "CoinTime.hpp"
     25
     26#define CBC_DEBUG 1
    2527
    2628// Default Constructor
     
    174176CbcCutGenerator::generateCuts( OsiCuts & cs , int fullScan, OsiSolverInterface * solver, CbcNode * node)
    175177{
     178
     179/*
     180  Make some decisions about whether we'll generate cuts. First convert
     181  whenCutGenerator_ to a set of canonical values for comparison to the node
     182  count.
     183
     184     0 <        mod 1000000, with a result of 0 forced to 1
     185   -99 <= <= 0  convert to 1
     186  -100 =        Off, period
     187*/
    176188  int depth;
    177189  if (node)
     
    196208  //OsiSolverInterface * solver = model_->solver();
    197209  int pass=model_->getCurrentPassNumber()-1;
     210
    198211  // Reset cuts on first pass
    199212  if (!pass)
    200213    savedCuts_ = OsiCuts();
     214/*
     215  Determine if we should generate cuts based on node count.
     216*/
    201217  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*/
    202222  if (depthCutGenerator_>0) {
    203223    doThis = (depth % depthCutGenerator_) ==0;
     
    205225      doThis=true; // and also at top of tree
    206226  }
     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*/
    207234  // But turn off if 100
    208235  if (howOften==100)
     
    9991026    }
    10001027#ifdef CBC_DEBUG
     1028/*
     1029  Check for bogus cuts --- cut lb > cut ub, or too large for comfort;
     1030  no coefficients, or too small for comfort. By convention, some cut generators
     1031  will return a cut with a lower bound of infinity and an upper bound of 0 to
     1032  indicate infeasibility.
     1033*/
    10011034    {
    10021035      int numberRowCutsAfter = cs.sizeRowCuts() ;
     
    10081041            thisCut.lb()>1.0e8||
    10091042            thisCut.ub()<-1.0e8)
    1010           printf("cut from %s has bounds %g and %g!\n",
    1011                  generatorName_,thisCut.lb(),thisCut.ub());
     1043        { if (!(thisCut.lb() == COIN_DBL_MAX && thisCut.ub() == 0.0))
     1044          { printf("cut from %s has bounds %g and %g!\n",
     1045                   generatorName_,thisCut.lb(),thisCut.ub()); } }
    10121046        if (thisCut.lb()<=thisCut.ub()) {
    10131047          /* check size of elements.
     
    10171051          const int * column = thisCut.row().getIndices();
    10181052          const double * element = thisCut.row().getElements();
    1019           assert (n);
     1053          if (n <= 0) {
     1054            printf("Cut generator %s produced a cut with no elements!\n",
     1055                   generatorName_) ;
     1056            nBad++ ;
     1057          }
     1058          // assert (n);
    10201059          for (int i=0;i<n;i++) {
    10211060            double value = element[i];
     
    10241063          }
    10251064        }
    1026         if (nBad)
    1027           printf("Cut generator %s produced %d cuts of which %d had tiny or large elements\n",
    1028                  generatorName_,numberRowCutsAfter-numberRowCutsBefore,nBad);
     1065      }
     1066      if (nBad) {
     1067        printf("Cut generator %s produced %d cuts",
     1068                 generatorName_,numberRowCutsAfter-numberRowCutsBefore) ;
     1069        printf(" of which %d had tiny or large elements\n",nBad) ;
    10291070      }
    10301071    }
  • branches/reengAnn/Cbc/src/CbcFathom.hpp

    r1173 r1265  
    66#include "CbcConfig.h"
    77
     8/*
     9  This file contains two classes, CbcFathom and CbcOsiSolver. It's unclear why
     10  they're in the same file. CbcOsiSolver is a base class for CbcLinked.
     11
     12  --lh, 071031 --
     13*/
     14
    815class CbcModel;
    916
    1017//#############################################################################
     18
    1119/** Fathom base class.
    1220
    13     The idea is that after some branching the problem will be effectively smaller than
    14     the original problem and maybe there will be a more specialized technique which can completely
    15     fathom this branch quickly.
     21    The idea is that after some branching the problem will be effectively
     22    smaller than the original problem and maybe there will be a more
     23    specialized technique which can completely fathom this branch quickly.
    1624
    17     One method is to presolve the problem to give a much smaller new problem and then do branch
    18     and cut on that.  Another might be dynamic programming.
     25    One method is to presolve the problem to give a much smaller new problem
     26    and then do branch and cut on that.  Another might be dynamic
     27    programming.
    1928
     29    Added capabilities are the resetModel() and fathom() methods.
    2030 */
    2131
     
    7181
    7282/**
    73    
    74 This is for codes where solver needs to know about CbcModel
     83  This is for codes where solver needs to know about CbcModel
     84
     85  Seems to provide only one value-added feature, a CbcModel object.
    7586*/
    7687
  • branches/reengAnn/Cbc/src/CbcGenBaB.cpp

    r1173 r1265  
    3434
    3535  char svnid[] = "$Id$" ;
     36
     37/*
     38  Just for kicks, define a branch decision class that makes it explicit we're
     39  working the OSI side of the hierarchy. The point here is that when we're
     40  working the OSI side, all the work is performed by the OsiChooseVariable
     41  method held in chooseMethod_ in the base class.
     42*/
     43
     44class CbcBranchOsiDecision : public CbcBranchDecision
     45{ public:
     46
     47  CbcBranchOsiDecision () : CbcBranchDecision() {}
     48  ~CbcBranchOsiDecision () {}
     49
     50  CbcBranchOsiDecision (const CbcBranchOsiDecision &rhs)
     51    : CbcBranchDecision(rhs)
     52  {}
     53
     54  CbcBranchOsiDecision *clone () const
     55  { return new CbcBranchOsiDecision(*this) ; }
     56
     57  void initialize (CbcModel *model) { assert(false) ; }
     58
     59  int betterBranch (CbcBranchingObject *thisOne,
     60                    CbcBranchingObject *bestSoFar,
     61                    double changeUp, int numInfUp,
     62                    double changeDn, int numInfDn)
     63  { assert(false) ;
     64    return (0) ; }
     65} ;
     66
    3667
    3768/*
     
    494525  the meat of the issue.
    495526
    496   preIppSolver will hold a clone of the unpreprocessed constraint system.
    497   We'll need it when we postprocess. ippSolver holds the preprocessed
    498   constraint system.  Again, we clone it and give the clone to babModel for
    499   B&C. Presumably we need an unmodified copy of the preprocessed system to
    500   do postprocessing, but the copy itself is hidden inside the preprocess
    501   object.
     527  preIppSolver points to the unpreprocessed constraint system.  ippSolver
     528  holds the preprocessed constraint system.  We clone it and give the clone
     529  to babModel for B&C. We'll need an unmodified copy of the preprocessed
     530  system to do postprocessing, but the copy itself is hidden inside (and
     531  managed by) the preprocess object.
    502532*/
    503533  OsiSolverInterface *preIppSolver = 0 ;
     
    512542        ippAction == CbcGenCtlBlk::IPPStrategy))
    513543  { double timeLeft = babModel.getMaximumSeconds() ;
    514     preIppSolver = babSolver->clone() ;
     544    preIppSolver = babSolver ;
    515545    OsiSolverInterface *ippSolver ;
    516546#   if CBC_TRACK_SOLVERS > 0
    517547    std::cout
    518       << "doBaCParam: clone made prior to IPP is "
     548      << "doBaCParam: solver prior to IPP is "
    519549      << std::hex << preIppSolver << std::dec
    520550      << ", log level " << preIppSolver->messageHandler()->logLevel()
     
    570600    { std::cout
    571601        << "Integer preprocess says infeasible or unbounded" << std::endl ;
    572       delete preIppSolver ;
    573602      ctlBlk->setBaBStatus(&babModel,CbcGenCtlBlk::BACwIPP) ;
    574603      return (0) ; }
     
    590619        << "Integer preprocessed model written to `presolved.mps' "
    591620        << "as minimisation problem." << std::endl ; }
    592    
     621/*
     622  Clone the preprocessed solver and give it to the model as the solver to
     623  use during branch and cut. The second parameter to assignSolver means that
     624  assignSolver will not delete the existing solver (held in preIppSolver).
     625*/
    593626    OsiSolverInterface *osiTmp = ippSolver->clone() ;
    594     babModel.assignSolver(osiTmp) ;
     627    babModel.assignSolver(osiTmp,false) ;
    595628    babSolver = babModel.solver() ;
    596629#   if CBC_TRACK_SOLVERS > 0
     
    602635#   endif
    603636    if (!solveRelaxation(&babModel))
    604     { delete preIppSolver ;
    605       ctlBlk->setBaBStatus(&babModel,CbcGenCtlBlk::BACwIPPRelax) ;
     637    { ctlBlk->setBaBStatus(&babModel,CbcGenCtlBlk::BACwIPPRelax) ;
    606638      return (0) ; }
    607639#   if COIN_CBC_VERBOSITY > 0
     
    682714  Set the branching method. We can't do this until we establish objects,
    683715  because the constructor will set up arrays based on the number of objects,
    684   and there's no provision to set this information after creation. Arguably not
    685   good --- it'd be nice to set this in the prototype model that's cloned for
    686   this routine. In CoinSolve, shadowPriceMode is handled with the TESTOSI
     716  and there's no provision to set this information after creation. Arguably
     717  not good --- it'd be nice to set this in the prototype model that's cloned
     718  for this routine. In CoinSolve, shadowPriceMode is handled with the TESTOSI
    687719  option.
     720
     721  CbcBranchOsiDecision (defined at the head of the file) is deliberately
     722  crafted to emphasise that when we're using the OSI side of the hierarchy
     723  there's no use of anything in the CbcBranchDecision classes except for
     724  chooseMethod_, which specifies an OsiChooseVariable method that does all
     725  the work. We indicate to CbcModel::branchAndBound that we want the Osi side
     726  by installing an Osi choose method (OsiChooseStrong in this case) in the
     727  CbcBranchDecision object with setChooseMethod, then installing the
     728  CbcBranchDecision object in the CbcModel with setBranchingMethod().
    688729*/
    689730  OsiChooseStrong strong(babSolver) ;
     
    691732  strong.setNumberStrong(babModel.numberStrong()) ;
    692733  strong.setShadowPriceMode(ctlBlk->chooseStrong_.shadowPriceMode_) ;
    693   CbcBranchDefaultDecision decision ;
     734  CbcBranchOsiDecision decision ;
    694735  decision.setChooseMethod(strong) ;
    695736  babModel.setBranchingMethod(decision) ;
     
    763804  ctlBlk->totalTime_ += time2-time1;
    764805/*
    765   If we performed integer preprocessing, time to back it out.
     806  If we performed integer preprocessing, time to back it out. babSolver will be
     807  deleted when preIPPsolver is again assigned to the model.
     808 
     809  As best I can see, it's not necessary to hold a pointer to the original
     810  model given to IPP. The assert is to boost my confidence in this conclusion.
     811  -- lh, 080122 --
    766812*/
    767813  if (ippAction != CbcGenCtlBlk::IPPOff)
     
    773819#   endif
    774820    ippObj.postProcess(*babSolver);
     821
     822    assert(ippObj.originalModel() == preIppSolver) ;
     823
     824    preIppSolver = ippObj.originalModel() ;
    775825    babModel.assignSolver(preIppSolver) ;
    776826    babSolver = babModel.solver() ;
  • branches/reengAnn/Cbc/src/CbcGenCtlBlk.cpp

    r1173 r1265  
    137137  fpump_.action_ = CbcGenCtlBlk::CGOn ;
    138138  fpump_.proto_ = 0 ;
     139  fpump_.iters_ = 20 ;
    139140
    140141  combine_.action_ = CbcGenCtlBlk::CGOn ;
  • branches/reengAnn/Cbc/src/CbcHeuristic.cpp

    r1263 r1265  
    66#  pragma warning(disable:4786)
    77#endif
     8
     9// Debug trace  (-lh-)
     10#define CBCHEUR_DEBUG 0
    811
    912#include "CbcConfig.h"
     
    641644                                  double cutoff, std::string name) const
    642645{
     646
     647# if CBCHEUR_DEBUG > 0
     648  std::cout
     649    << "CbcHeuristic::smallBAB: entering." << std::endl ;
     650# endif
     651
    643652  // size before
    644653  int shiftRows=0;
     
    665674    }
    666675  }
     676
    667677#ifdef COIN_HAS_CLP
    668678  OsiClpSolverInterface * osiclp = dynamic_cast< OsiClpSolverInterface*> (solver);
     
    711721    // presolveActions |= 4;
    712722    pinfo->setPresolveActions(presolveActions);
    713     OsiSolverInterface * presolvedModel = pinfo->presolvedModel(*solver,1.0e-8,true,2);
     723    OsiSolverInterface * presolvedModel = pinfo->presolvedModel(*solver,1.0e-8,true,2,0,false);
    714724    delete pinfo;
    715725    // see if too big
     
    773783          // presolveActions |= 4;
    774784          pinfo->setPresolveActions(presolveActions);
    775           presolvedModel = pinfo->presolvedModel(*solver,1.0e-8,true,2);
     785          presolvedModel = pinfo->presolvedModel(*solver,1.0e-8,true,2,0,false);
    776786          delete pinfo;
    777787          if(presolvedModel) {
     
    12131223    returnCode=2; // infeasible finished
    12141224  }
     1225
     1226# if CBCHEUR_DEBUG > 0
     1227  std::cout
     1228    << "CbcHeuristic::smallBAB: resetting bounds." << std::endl ;
     1229# endif
     1230
    12151231  model_->setSpecialOptions(saveModelOptions);
    12161232  model_->setLogLevel(logLevel);
     
    12791295#endif
    12801296  solver->setHintParam(OsiDoReducePrint,takeHint,strength);
     1297
     1298# if CBCHEUR_DEBUG > 0
     1299  std::cout
     1300    << "CbcHeuristic::smallBAB: finished." << std::endl ;
     1301# endif
     1302
    12811303  return returnCode;
    12821304}
  • branches/reengAnn/Cbc/src/CbcHeuristicFPump.cpp

    r1240 r1265  
    66#  pragma warning(disable:4786)
    77#endif
     8
     9#define CBCFPUMP_DEBUG 0
     10// #define COIN_DEVELOP
     11// #define COIN_DEVELOP_x
     12
    813#include <cassert>
    914#include <cstdlib>
     
    215220                         double * betterSolution)
    216221{
     222
     223# if CBCFPUMP_DEBUG > 0
     224  std::cout
     225    << "CbcFPump::solution: Entering, phase "
     226    << model_->phase() << ", z = " << solutionValue
     227    << ", " << maximumRetries_ << " retries, " << maximumPasses_
     228    << " passes." << std::endl ;
     229# endif
     230
    217231  startTime_=CoinCpuTime();
    218232  numCouldRun_++;
     
    221235  char pumpPrint[LEN_PRINT];
    222236  pumpPrint[0]='\0';
     237/*
     238  Decide if we want to run. Standard values for when are described in
     239  CbcHeuristic.hpp. If we're off, or running only at root and this isn't the
     240  root, bail out.
     241
     242  The double test (against phase, then atRoot and passNumber) has a fair bit
     243  of redundancy, but the results will differ depending on whether we're
     244  actually at the root of the main search tree or at the root of a small tree
     245  (recursive call to branchAndBound).
     246
     247  FPump also supports some exotic values (11 -- 15) for when, described in
     248  CbcHeuristicFPump.hpp.
     249*/
    223250  if (!when()||(when()==1&&model_->phase()!=1))
    224251    return 0; // switched off
     
    283310  int numberIterationsLastPass=0;
    284311  // 1. initially check 0-1
     312/*
     313  I'm skeptical of the above comment, but it's likely accurate as the default.
     314  Bit 4 or bit 8 needs to be set in order to consider working with general
     315  integers.
     316*/
    285317  int i,j;
    286318  int general=0;
     
    290322  bool doGeneral = (accumulate_&4)!=0;
    291323  j=0;
     324/*
     325  Scan the objects, recording the columns and counting general integers.
     326
     327  Seems like the NDEBUG tests could be made into an applicability test. If
     328  a scan of the objects reveals complex objects, just clean up and return
     329  failure.
     330*/
    292331  for (i=0;i<numberIntegers;i++) {
    293332    int iColumn = integerVariableOrig[i];
     
    308347    }
    309348  }
     349/*
     350  If 2/3 of integers are general integers, and we're not going to work with
     351  them, might as well go home.
     352
     353  The else case is unclear to me. We reach it if general integers are less than
     354  2/3 of the total, or if either of bit 4 or 8 is set. But only bit 8 is used
     355  in the decision. (Let manyGen = 1 if more than 2/3 of integers are general
     356  integers. Then a k-map on manyGen, bit4, and bit8 shows it clearly.)
     357
     358  So there's something odd here. In the case where bit4 = 1 and bit8 = 0,
     359  we've included general integers in integerVariable, but we're not going to
     360  process them.
     361*/
    310362  if (general*3>2*numberIntegers&&!doGeneral) {
    311363    delete [] integerVariable;
     
    326378    printf("DOing general with %d out of %d\n",general,numberIntegers);
    327379#endif
     380/*
     381  This `closest solution' will satisfy integrality, but violate some other
     382  constraints?
     383*/
    328384  // For solution closest to feasible if none found
    329385  int * closestSolution = general ? NULL : new int[numberIntegers];
     
    345401  }
    346402  double time1 = CoinCpuTime();
     403/*
     404  Obtain a relaxed lp solution.
     405*/
    347406  model_->solver()->resolve();
    348407  if (!model_->solver()->isProvenOptimal()) {
     
    363422    }
    364423  }
     424/*
     425  I have no idea why we're doing this, except perhaps that saveBasis will be
     426  automagically deleted on exit from the routine.
     427*/
    365428  CoinWarmStartBasis saveBasis;
    366429  CoinWarmStartBasis * basis =
     
    474537    double lastSumInfeas=COIN_DBL_MAX;
    475538    numberTries++;
     539#   if CBCFPUMP_DEBUG > 0
     540    std::cout
     541      << "    major pass " << numberTries
     542      << "." << std::endl ;
     543#   endif
    476544    // Clone solver - otherwise annoys root node computations
    477545    solver = cloneBut(2); // was model_->solver()->clone();
     
    630698#endif
    631699#endif
     700
    632701    // This is an array of sums of infeasibilities so can see if "bobbling"
    633702#define SIZE_BOBBLE 20
     
    636705    // 0 before doing anything
    637706    int bobbleMode = 0;
     707
     708#   if CBCFPUMP_DEBUG > 0
     709    std::cout << "CbcFPump::solution: entering main while loop." << std::endl ;
     710#   endif
     711
    638712    // 5. MAIN WHILE LOOP
    639713    //bool newLineNeeded=false;
     714/*
     715  finished occurs exactly twice in this routine: immediately above, where it's
     716  set to false, and here in the loop condition.
     717*/
    640718    while (!finished) {
    641719      double newTrueSolutionValue=0.0;
     
    645723      if (model_->maximumSecondsReached()) {
    646724        exitAll=true;
     725#           if CBCFPUMP_DEBUG > 0
     726            std::cout
     727              << "CbcFPump::solution: (1) breaking main while loop."
     728              << std::endl ;
     729#           endif
    647730        break;
    648731      }
     
    684767          &&numberPasses>15) {
    685768          // exiting on iteration count
     769
     770#           if CBCFPUMP_DEBUG > 0
     771            std::cout
     772              << "CbcFPump::solution: (2) breaking main while loop."
     773              << std::endl ;
     774#           endif
     775
    686776        exitAll=true;
    687777      } else if (maximumPasses<30&&numberPasses>100) {
     
    726816        newSolutionValue *= direction;
    727817        sprintf(pumpPrint,"Solution found of %g",newSolutionValue);
     818#       if CBCFPUMP_DEBUG > 1
     819        if (strlen(pumpPrint) >= LEN_PRINT)
     820        { std::cout
     821            << "ERROR(1)! string in pumpPrint is "
     822            << strlen(pumpPrint) << " chars." << std::endl ; }
     823#       endif
    728824        model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    729825          << pumpPrint
     
    788884              if (action==0||model_->maximumSecondsReached()) {
    789885                exitAll=true; // exit
     886#           if CBCFPUMP_DEBUG > 0
     887            std::cout
     888              << "CbcFPump::solution: (5) breaking main while loop."
     889              << std::endl ;
     890#           endif
    790891                break;
    791892              }
     
    799900            if (general&&saveValue!=newSolutionValue) {
    800901              sprintf(pumpPrint,"Cleaned solution of %g",solutionValue);
     902#             if CBCFPUMP_DEBUG > 1
     903              if (strlen(pumpPrint) >= LEN_PRINT)
     904              { std::cout
     905                  << "ERROR(2)! string in pumpPrint is "
     906                  << strlen(pumpPrint) << " chars." << std::endl ; }
     907#             endif
    801908              model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    802909                << pumpPrint
     
    807914          } else {
    808915            sprintf(pumpPrint,"Mini branch and bound could not fix general integers");
     916#           if CBCFPUMP_DEBUG > 1
     917            if (strlen(pumpPrint) >= LEN_PRINT)
     918            { std::cout
     919                << "ERROR(3)! string in pumpPrint is "
     920                << strlen(pumpPrint) << " chars." << std::endl ; }
     921#           endif
    809922            model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    810923              << pumpPrint
     
    813926        } else {
    814927          sprintf(pumpPrint,"After further testing solution no better than previous of %g",solutionValue);
     928#         if CBCFPUMP_DEBUG > 1
     929          if (strlen(pumpPrint) >= LEN_PRINT)
     930          { std::cout
     931              << "ERROR(4)! string in pumpPrint is "
     932              << strlen(pumpPrint) << " chars." << std::endl ; }
     933#         endif
    815934          model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    816935            << pumpPrint
     
    839958        if (matched || numberPasses%100 == 0) {
    840959          // perturbation
    841           //sprintf(pumpPrint+strlen(pumpPrint)," perturbation applied");
    842           //newLineNeeded=true;
    843960          double factorX[10]={0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0};
    844961          double factor=1.0;
     
    9801097            // presumably max time or some such
    9811098            exitAll=true;
     1099#           if CBCFPUMP_DEBUG > 0
     1100            std::cout
     1101              << "CbcFPump::solution: (6) breaking main while loop."
     1102              << std::endl ;
     1103#           endif
    9821104            break;
    9831105          }
     
    10081130              << pumpPrint
    10091131              <<CoinMessageEol;
     1132#           if CBCFPUMP_DEBUG > 1
     1133            if (strlen(pumpPrint) >= LEN_PRINT)
     1134            { std::cout
     1135                << "ERROR(6)! string in pumpPrint is "
     1136                << strlen(pumpPrint) << " chars." << std::endl ; }
     1137#           endif
    10101138            if (newSolutionValue<solutionValue) {
    10111139              memcpy(betterSolution,newSolution,numberColumns*sizeof(double));
     
    10291157                if (!action||model_->maximumSecondsReached()) {
    10301158                  exitAll=true; // exit
     1159#           if CBCFPUMP_DEBUG > 0
     1160            std::cout
     1161              << "CbcFPump::solution: (7) breaking main while loop."
     1162              << std::endl ;
     1163#           endif
    10311164                  break;
    10321165                }
     
    11431276            // presumably max time or some such
    11441277            exitAll=true;
     1278#           if CBCFPUMP_DEBUG > 0
     1279            std::cout
     1280              << "CbcFPump::solution: (8) breaking main while loop."
     1281              << std::endl ;
     1282#           endif
    11451283            break;
    11461284          }
     
    13331471            // presumably max time or some such
    13341472            exitAll=true;
     1473#           if CBCFPUMP_DEBUG > 0
     1474            std::cout
     1475              << "CbcFPump::solution: (9) breaking main while loop."
     1476              << std::endl ;
     1477#           endif
    13351478            break;
    13361479          }
     
    14091552            // presumably max time or some such
    14101553            exitAll=true;
     1554#           if CBCFPUMP_DEBUG > 0
     1555            std::cout
     1556              << "CbcFPump::solution: (10) breaking main while loop."
     1557              << std::endl ;
     1558#           endif
    14111559            break;
    14121560          }
     
    14611609          << pumpPrint
    14621610          <<CoinMessageEol;
     1611#       if CBCFPUMP_DEBUG > 1
     1612        if (strlen(pumpPrint) >= LEN_PRINT)
     1613        { std::cout
     1614            << "ERROR(7)! string in pumpPrint is "
     1615            << strlen(pumpPrint) << " chars." << std::endl ; }
     1616#       endif
    14631617        if (closestSolution&&solver->getObjValue()<closestObjectiveValue) {
    14641618          int i;
     
    15711725      // reduce scale factor
    15721726      scaleFactor *= weightFactor_;
    1573     } // END WHILE
     1727    } // END WHILE break
     1728#   if CBCFPUMP_DEBUG > 0
     1729    std::cout << "CbcFPump::solution: end main while loop." << std::endl ;
     1730#   endif
    15741731    // see if rounding worked!
    15751732    if (roundingObjective<solutionValue) {
     
    15901747    if (!solutionFound) {
    15911748      sprintf(pumpPrint,"No solution found this major pass");
     1749#     if CBCFPUMP_DEBUG > 1
     1750      if (strlen(pumpPrint) >= LEN_PRINT)
     1751      { std::cout
     1752          << "ERROR(8)! string in pumpPrint is "
     1753          << strlen(pumpPrint) << " chars." << std::endl ; }
     1754#     endif
    15921755      model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    15931756        << pumpPrint
    15941757        <<CoinMessageEol;
    15951758    }
    1596     //}
     1759
    15971760    delete solver;
    15981761    solver=NULL;
     
    16741837        }
    16751838        sprintf(pumpPrint,"Before mini branch and bound, %d integers at bound fixed and %d continuous",
    1676                 nFix,nFixC);
     1839               nFix,nFixC);
    16771840        if (nFixC2+nFixI!=0)
    16781841          sprintf(pumpPrint+strlen(pumpPrint)," of which %d were internal integer and %d internal continuous",
    16791842                  nFixI,nFixC2);
     1843#       if CBCFPUMP_DEBUG > 1
     1844        if (strlen(pumpPrint) >= LEN_PRINT)
     1845        { std::cout
     1846            << "ERROR(9)! string in pumpPrint is "
     1847            << strlen(pumpPrint) << " chars." << std::endl ; }
     1848#       endif
    16801849        model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    16811850          << pumpPrint
     
    16881857            fractionSmall_ *= 0.5;
    16891858          // Give branch and bound a bit more freedom
    1690           double cutoff2=newSolutionValue+
    1691             CoinMax(model_->getCutoffIncrement(),1.0e-3);
     1859          double cutoff2=newSolutionValue-model_->getCutoffIncrement();
    16921860          int returnCode2 = smallBranchAndBound(newSolver,numberNodes_,newSolution,newSolutionValue,
    16931861                                                cutoff2,"CbcHeuristicLocalAfterFPump");
     
    16981866              returnCode=0;
    16991867            } else {
    1700               returnCode2=0; // returned on size - try changing
     1868              returnCode2=0; // returned on size (or event) - could try changing
    17011869              //#define ROUND_AGAIN
    17021870#ifdef ROUND_AGAIN
     
    18532021#endif
    18542022                sprintf(pumpPrint,"Freeing continuous variables gives a solution of %g", value);
     2023#               if CBCFPUMP_DEBUG > 1
     2024                if (strlen(pumpPrint) >= LEN_PRINT)
     2025                { std::cout
     2026                    << "ERROR(11)! string in pumpPrint is "
     2027                    << strlen(pumpPrint) << " chars." << std::endl ; }
     2028#               endif
    18552029                model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    18562030                  << pumpPrint
     
    19532127        break;
    19542128      sprintf(pumpPrint,"Round again with cutoff of %g",cutoff);
     2129#     if CBCFPUMP_DEBUG > 1
     2130      if (strlen(pumpPrint) >= LEN_PRINT)
     2131      { std::cout
     2132          << "ERROR(12)! string in pumpPrint is "
     2133          << strlen(pumpPrint) << " chars." << std::endl ; }
     2134#     endif
    19552135      model_->messageHandler()->message(CBC_FPUMP1,model_->messages())
    19562136        << pumpPrint
     
    19652145    }
    19662146  }
     2147/*
     2148  End of the `exitAll' loop.
     2149*/
    19672150#ifdef RAND_RAND
    19682151  delete [] randomFactor;
     
    20142197    delete newSolver;
    20152198  }
     2199
     2200# if CBCFPUMP_DEBUG > 0
     2201  std::cout
     2202    << "CbcFPump::solution: Cleanup." << std::endl ;
     2203# endif
     2204
    20162205  delete clonedSolver;
    20172206  delete [] roundingSolution;
     
    20392228    model_->setNumberHeuristicSolutions(1);
    20402229  }
     2230
    20412231#ifdef COIN_DEVELOP
    20422232  {
     
    20502240  }
    20512241#endif
     2242
     2243# if CBCFPUMP_DEBUG > 0
     2244  std::cout
     2245    << "CbcFPump::solution: Finished, returning "
     2246    << finalReturnCode << "." << std::endl ;
     2247# endif
     2248
    20522249  return finalReturnCode;
    20532250}
     
    20712268                          /*bool roundExpensive,*/ double downValue, int *flip)
    20722269{
     2270# if CBCFPUMP_DEBUG > 0
     2271  std::cout << "CbcFPump::rounds entering." << std::endl ;
     2272# endif
    20732273  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
    20742274  double primalTolerance ;
     
    26672867#endif
    26682868  delete [] rowActivity;
     2869# if CBCFPUMP_DEBUG > 0
     2870  std::cout
     2871    << "CbcFPump::rounds exiting with "
     2872    << ((largestInfeasibility>primalTolerance)?"no solution":"solution")
     2873    << "." << std::endl ;
     2874# endif
    26692875  return (largestInfeasibility>primalTolerance) ? 0 : 1;
    26702876}
  • branches/reengAnn/Cbc/src/CbcHeuristicFPump.hpp

    r1221 r1265  
    5555        14 - also fix all continuous variables staying at same internal value throughout
    5656        15 - as 13 but no internal integers
     57
     58      And beyond that, it's apparently possible for the range to be between 21
     59      and 25, in which case it's reduced on entry to solution() to be between
     60      11 and 15 and allSlack is set to true. Then, if we're not processing
     61      general integers, we'll use an all-slack basis to solve ... what? Don't
     62      see that yet.
    5763  */
    5864  virtual int solution(double & objectiveValue,
     
    129135       2 - reuse solves, do not accumulate integer solutions for local search
    130136       3 - reuse solves, accumulate integer solutions for local search
    131        If we add 4 then use second form of problem (with extra rows and variables for general integers)
     137
     138       At some point (date?), I added
     139
     140       And then there are a few bit fields:
     141       4 - something about general integers
     142       8 - determines whether we process general integers
     143
     144       And on 090831, John added
     145
     146       If we add 4 then use second form of problem (with extra rows and
     147       variables for general integers)
    132148       If we add 8 then can run after initial cuts (if no solution)
     149
     150       So my (lh) guess for 4 was at least in the ballpark, but I'll have to
     151       rethink 8 entirely (and it may well not mean the same thing as it did
     152       when I added that comment.
    133153  */
    134154  inline void setAccumulate(int value)
  • branches/reengAnn/Cbc/src/CbcHeuristicLocal.cpp

    r1263 r1265  
    122122  }
    123123}
     124
     125/*
     126  Run a mini-BaB search after fixing all variables not marked as used by
     127  solution(). (See comments there for semantics.)
     128
     129  Return values are:
     130    1: smallBranchAndBound found a solution
     131    0: everything else
     132
     133  The degree of overload as return codes from smallBranchAndBound are folded
     134  into 0 is such that it's impossible to distinguish return codes that really
     135  require attention from a simple `nothing of interest'.
     136*/
    124137// This version fixes stuff and does IP
    125138int
     
    128141                               const int * /*keep*/)
    129142{
     143
     144/*
     145  If when is set to off (0), or set to root (1) and we're not at the root,
     146  return. If this heuristic discovered the current solution, don't continue.
     147*/
     148
    130149  numCouldRun_++;
    131150  // See if to do
     
    135154  if (this==model_->lastHeuristic())
    136155    return 0;
     156/*
     157  Load up a new solver with the solution.
     158
     159  Why continuousSolver(), as opposed to solver()?
     160*/
    137161  OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
    138162  const double * colLower = newSolver->getColLower();
     
    141165  int numberIntegers = model_->numberIntegers();
    142166  const int * integerVariable = model_->integerVariable();
    143  
     167/*
     168  The net effect here is that anything that hasn't moved from its lower bound
     169  will be fixed at lower bound.
     170
     171  See comments in solution() w.r.t. asymmetric treatment of upper and lower
     172  bounds.
     173*/
    144174  int i;
    145175  int nFix=0;
     
    157187    }
    158188  }
     189/*
     190  Try a `small' branch-and-bound search. The notion here is that we've fixed a
     191  lot of variables and reduced the amount of `free' problem to a point where a
     192  small BaB search will suffice to fully explore the remaining problem. This
     193  routine will execute integer presolve, then call branchAndBound to do the
     194  actual search.
     195*/
    159196  int returnCode = 0;
    160197  if (nFix*10>numberIntegers) {
    161198    returnCode = smallBranchAndBound(newSolver,numberNodes_,newSolution,objectiveValue,
    162199                                     objectiveValue,"CbcHeuristicLocal");
     200/*
     201  -2 is return due to user event, and -1 is overloaded with what look to be
     202  two contradictory meanings.
     203*/
    163204    if (returnCode<0) {
    164205      returnCode=0; // returned on size
     
    225266    }
    226267  }
     268/*
     269  If the result is complete exploration with a solution (3) or proven
     270  infeasibility (2), we could generate a cut (the AI folks would call it a
     271  nogood) to prevent us from going down this route in the future.
     272*/
    227273  if ((returnCode&2)!=0) {
    228274    // could add cut
     
    233279  return returnCode;
    234280}
    235 /*
    236   First tries setting a variable to better value.  If feasible then
    237   tries setting others.  If not feasible then tries swaps
    238   Returns 1 if solution, 0 if not */
     281
     282/*
     283  First tries setting a variable to better value.  If feasible then tries
     284  setting others.  If not feasible then tries swaps Returns 1 if solution, 0
     285  if not
     286
     287  The main body of this routine implements an O((q^2)/2) brute force search
     288  around the current solution, for q = number of integer variables. Call this
     289  the inc/dec heuristic.  For each integer variable x<i>, first decrement the
     290  value. Then, for integer variables x<i+1>, ..., x<q-1>, try increment and
     291  decrement. If one of these permutations produces a better solution,
     292  remember it.  Then repeat, with x<i> incremented. If we find a better
     293  solution, update our notion of current solution and continue.
     294
     295  The net effect is a greedy walk: As each improving pair is found, the
     296  current solution is updated and the search continues from this updated
     297  solution.
     298
     299  Way down at the end, we call solutionFix, which will create a drastically
     300  restricted problem based on variables marked as used, then do mini-BaC on
     301  the restricted problem. This can occur even if we don't try the inc/dec
     302  heuristic. This would be more obvious if the inc/dec heuristic were broken
     303  out as a separate routine and solutionFix had a name that reflected where
     304  it was headed.
     305
     306  The return code of 0 is grossly overloaded, because it maps to a return
     307  code of 0 from solutionFix, which is itself grossly overloaded. See
     308  comments in solutionFix and in CbcHeuristic::smallBranchAndBound.
     309*/
     310
    239311int
    240312CbcHeuristicLocal::solution(double & solutionValue,
    241313                         double * betterSolution)
    242314{
    243 
     315/*
     316  Execute only if a new solution has been discovered since the last time we
     317  were called.
     318*/
    244319  numCouldRun_++;
    245320  if (numberSolutions_==model_->getSolutionCount())
    246321    return 0;
    247322  numberSolutions_=model_->getSolutionCount();
     323/*
     324  Exclude long (column), thin (row) systems.
     325
     326  Given the n^2 nature of the search, more than 100,000 columns could get
     327  expensive. But I don't yet see the rationale for the second part of the
     328  condition (cols > 10*rows). And cost is proportional to number of integer
     329  variables --- shouldn't we use that?
     330
     331  Why wait until we have more than one solution?
     332*/
    248333  if ((model_->getNumCols()>100000&&model_->getNumCols()>
    249334       10*model_->getNumRows())||numberSolutions_<=1)
     
    255340  const double * rowUpper = solver->getRowUpper();
    256341  const double * solution = model_->bestSolution();
     342/*
     343  Shouldn't this test be redundant if we've already checked that
     344  numberSolutions_ > 1? Stronger: shouldn't this be an assertion?
     345*/
    257346  if (!solution)
    258347    return 0; // No solution found yet
     
    302391  double * save = new double[numberRows];
    303392
     393/*
     394  Force variables within their original bounds, then to the nearest integer.
     395  Overall, we seem to be prepared to cope with noninteger bounds. Is this
     396  necessary? Seems like we'd be better off to force the bounds to integrality
     397  as part of preprocessing.  More generally, why do we need to do this? This
     398  solution should have been cleaned and checked when it was accepted as a
     399  solution!
     400
     401  Once the value is set, decide whether we can move up or down.
     402
     403  The only place that used_ is used is in solutionFix; if a variable is not
     404  flagged as used, it will be fixed (at lower bound). Why the asymmetric
     405  treatment? This makes some sense for binary variables (for which there are
     406  only two options). But for general integer variables, why not make a similar
     407  test against the original upper bound?
     408*/
    304409  // clean solution
    305410  for (i=0;i<numberIntegers;i++) {
     
    327432    }
    328433    cost[i] = direction*objective[iColumn];
     434/*
     435  Given previous computation we're checking that value is at least 1 away
     436  from the original bounds.
     437*/
    329438    int iway=0;
    330    
    331439    if (value>originalLower+0.5)
    332440      iway = 1;
     
    335443    way[i]=static_cast<char>(iway);
    336444  }
     445/*
     446  Calculate lhs of each constraint for groomed solution.
     447*/
    337448  // get row activities
    338449  double * rowActivity = new double[numberRows];
     
    350461    }
    351462  }
     463/*
     464  Check that constraints are satisfied. For small infeasibility, force the
     465  activity within bound. Again, why is this necessary if the current solution
     466  was accepted as a valid solution?
     467
     468  Why are we scanning past the first unacceptable constraint?
     469*/
    352470  // check was feasible - if not adjust (cleaning may move)
    353471  // if very infeasible then give up
     
    364482    }
    365483  }
     484/*
     485  This bit of code is not quite totally redundant: it'll bail at 10,000
     486  instead of 100,000. Potentially we can do a lot of work to get here, only
     487  to abandon it.
     488*/
    366489  // Switch off if may take too long
    367490  if (model_->getNumCols()>10000&&model_->getNumCols()>
    368491      10*model_->getNumRows())
    369492    tryHeuristic=false;
     493/*
     494  Try the inc/dec heuristic?
     495*/
    370496  if (tryHeuristic) {
    371497   
    372498    // best change in objective
    373499    double bestChange=0.0;
    374    
     500/*
     501  Outer loop to walk integer variables. Call the current variable x<i>. At the
     502  end of this loop, bestChange will contain the best (negative) change in the
     503  objective for any single pair.
     504
     505  The trouble is, we're limited to monotonically increasing improvement.
     506  Suppose we discover an improvement of 10 for some pair. If, later in the
     507  search, we discover an improvement of 9 for some other pair, we will not use
     508  it. That seems wasteful.
     509*/
    375510    for (i=0;i<numberIntegers;i++) {
    376511      int iColumn = integerVariable[i];
     
    381516      int goodK=-1;
    382517      int wayK=-1,wayI=-1;
     518/*
     519  Try decrementing x<i>.
     520*/
    383521      if ((way[i]&1)!=0) {
    384522        int numberInfeasible=0;
     523/*
     524  Adjust row activities where x<i> has a nonzero coefficient. Save the old
     525  values for restoration. Mark any rows that become infeasible as a result
     526  of the decrement.
     527*/
    385528        // save row activities and adjust
    386529        for (j=columnStart[iColumn];
     
    396539          }
    397540        }
     541/*
     542  Run through the remaining integer variables. Try increment and decrement on
     543  each one. If the potential objective change is better than anything we've
     544  seen so far, do a full evaluation of x<k> in that direction.  If we can
     545  repair all infeasibilities introduced by pushing x<i> down, we have a
     546  winner. Remember the best variable, and the direction for x<i> and x<k>.
     547*/
    398548        // try down
    399549        for (k=i+1;k<numberIntegers;k++) {
     
    457607          }
    458608        }
     609/*
     610  Remove effect of decrementing x<i> by restoring original lhs values.
     611*/
    459612        // restore row activities
    460613        for (j=columnStart[iColumn];
     
    465618        }
    466619      }
     620/*
     621  Try to increment x<i>. Actions as for decrement.
     622*/
    467623      if ((way[i]&2)!=0) {
    468624        int numberInfeasible=0;
     
    549705        }
    550706      }
     707/*
     708  We've found a pair x<i> and x<k> which produce a better solution. Update our
     709  notion of current solution to match.
     710
     711  Why does this not update newSolutionValue?
     712*/
    551713      if (goodK>=0) {
    552714        // we found something - update solution
     
    564726        }
    565727        newSolution[kColumn] += wayK;
     728/*
     729  Adjust motion range for x<k>. We may have banged up against a bound with that
     730  last move.
     731*/
    566732        // See if k can go further ?
    567733        const OsiObject * object = model_->object(goodK);
     
    581747      }
    582748    }
     749/*
     750  End of loop to try increment/decrement of integer variables.
     751
     752  newSolutionValue does not necessarily match the current newSolution, and
     753  bestChange simply reflects the best single change. Still, that's sufficient
     754  to indicate that there's been at least one change. Check that we really do
     755  have a valid solution.
     756*/
    583757    if (bestChange+newSolutionValue<solutionValue) {
    584758      // paranoid check
     
    625799          }
    626800        }
     801/*
     802  Copy the solution to the array returned to the client. Grab a basis from
     803  the solver (which, if it exists, is almost certainly infeasible, but it
     804  should be ok for a dual start). The value returned as solutionValue is
     805  conservative because of handling of newSolutionValue and bestChange, as
     806  described above.
     807*/
    627808        // new solution
    628809        memcpy(betterSolution,newSolution,numberColumns*sizeof(double));
     
    642823    }
    643824  }
     825/*
     826  We're done. Clean up.
     827*/
    644828  delete [] newSolution;
    645829  delete [] rowActivity;
     
    648832  delete [] save;
    649833  delete [] mark;
     834/*
     835  Do we want to try swapping values between solutions?
     836  swap_ is set elsewhere; it's not adjusted during heuristic execution.
     837
     838  Again, redundant test. We shouldn't be here if numberSolutions_ = 1.
     839*/
    650840  if (numberSolutions_>1&&swap_==1) {
    651841    // try merge
  • branches/reengAnn/Cbc/src/CbcMain.cpp

    r1173 r1265  
    22// copyright (C) 2002, International Business Machines
    33// Corporation and others.  All Rights Reserved.
     4
     5/*! \file CbcMain.cpp
     6    \brief Obsolete main routine for stand-alone cbc.
     7
     8    Unused since at least 2006. JJF forked off a clp-specific version, which
     9    evolved into CoinSolve and CbcSolver. LH changed to a completely different
     10    structure for CbcGeneric.
     11*/
    412
    513#include "CbcConfig.h"
  • branches/reengAnn/Cbc/src/CbcModel.cpp

    r1263 r1265  
    99#include "CbcConfig.h"
    1010
     11// Debug trace  (-lh-)
     12#define CBCMODEL_DEBUG 0
     13
     14
    1115#include <string>
    12 //#define CBC_DEBUG 1
    13 //#define CHECK_CUT_COUNTS
    14 //#define CHECK_NODE_FULL
    15 //#define NODE_LOG
     16// #define CBC_DEBUG 1
     17// #define CHECK_CUT_COUNTS
     18// #define CHECK_NODE_FULL
     19// #define NODE_LOG
     20#define CBC_HEUR_TRACE 0
     21#define CBC_CUTGEN_TRACE 0
    1622//#define GLOBAL_CUTS_JUST_POINTERS
    1723#ifdef CGL_DEBUG_GOMORY
     
    11281134
    11291135{
     1136# if CBCMODEL_DEBUG > 0
     1137  std::cout
     1138    << "CbcModel:bAB: Entering." << std::endl ;
     1139  handler_->setLogLevel(3) ;
     1140# endif
    11301141/*
    11311142  Capture a time stamp before we start.
     
    11791190  bool noObjects = (numberObjects_==0);
    11801191  // Set up strategies
     1192/*
     1193  See if the user has supplied a strategy object and deal with it if present.
     1194  The call to setupOther will set numberStrong_ and numberBeforeTrust_, and
     1195  perform integer preprocessing, if requested.
     1196
     1197  We need to hang on to a pointer to solver_. setupOther will assign a
     1198  preprocessed solver to model, but will instruct assignSolver not to trash the
     1199  existing one.
     1200*/
    11811201  if (strategy_) {
    11821202    // May do preprocessing
     
    14101430  solver_->getStrParam(OsiProbName,problemName) ;
    14111431  printf("Problem name - %s\n",problemName.c_str()) ;
    1412   solver_->setHintParam(OsiDoReducePrint,false,OsiHintDo,0) ;
     1432  // CBCMODEL_DEBUG solver_->setHintParam(OsiDoReducePrint,false,OsiHintDo,0) ;
    14131433# endif
    14141434/*
     
    14501470  } 
    14511471/*
    1452   Ensure that objects on the lists of OsiObjects, heuristics, and cut
     1472  Ensure that objects on the lists of objects, heuristics, and cut
    14531473  generators attached to this model all refer to this model.
    14541474*/
     
    15471567    return ;
    15481568  }
     1569/*
     1570  See if we're using the Osi side of the branching hierarchy. If so, either
     1571  convert existing CbcObjects to OsiObjects, or generate them fresh. In the
     1572  first case, CbcModel owns the objects on the object_ list. In the second
     1573  case, the solver holds the objects and object_ simply points to the
     1574  solver's list.
     1575
     1576  080417 The conversion code here (the block protected by `if (obj)') cannot
     1577  possibly be correct. On the Osi side, descent is OsiObject -> OsiObject2 ->
     1578  all other Osi object classes. On the Cbc side, it's OsiObject -> CbcObject
     1579  -> all other Cbc object classes. It's structurally impossible for any Osi
     1580  object to descend from CbcObject. The only thing I can see is that this is
     1581  really dead code, and object detection is now handled from the Osi side.
     1582*/
    15491583  // Convert to Osi if wanted
    15501584  bool useOsiBranching=false;
    15511585  //OsiBranchingInformation * persistentInfo = NULL;
    15521586  if (branchingMethod_&&branchingMethod_->chooseMethod()) {
     1587#   if CBCMODEL_DEBUG > 1
     1588    std::cout << "    Using Osi objects." << std::endl ;
     1589#   endif
    15531590    useOsiBranching=true;
    15541591    //persistentInfo = new OsiBranchingInformation(solver_);
    15551592    if (numberOriginalObjects) {
     1593#     if CBCMODEL_DEBUG > 1
     1594      std::cout
     1595        << "    Scanning " << numberOriginalObjects
     1596        << " objects for CbcObjects to convert to OsiObjects."
     1597        << std::endl
     1598        << "    This code is clearly bogus, so I'm going to die now."
     1599        << std::endl ;
     1600      std::cout.flush() ;
     1601      assert(false) ;
     1602#     endif
    15561603      for (int iObject = 0 ; iObject < numberObjects_ ; iObject++) {
    15571604        CbcObject * obj =
     
    15951642        //}
    15961643    } else {
     1644/*
     1645  As of 080104, findIntegersAndSOS is misleading --- the default OSI
     1646  implementation finds only integers.
     1647*/
    15971648      // do from solver
     1649#     if CBCMODEL_DEBUG > 1
     1650      std::cout
     1651        << "    Calling Osi routines to identify objects."
     1652        << std::endl ;
     1653#     endif
    15981654      deleteObjects(false);
    15991655      solver_->findIntegersAndSOS(false);
     
    16041660    branchingMethod_->chooseMethod()->setSolver(solver_);
    16051661  }
     1662# if CBCMODEL_DEBUG > 1
     1663  else
     1664  { std::cout << "    Using Cbc objects." << std::endl ; }
     1665# endif
    16061666  // take off heuristics if have to
    16071667  {
     
    17011761  constraint system (aka the continuous system).
    17021762*/
     1763# if CBCMODEL_DEBUG > 1
     1764  std::cout << "    Cloning continuous solver." << std::endl ;
     1765# endif
    17031766  continuousSolver_ = solver_->clone() ;
    17041767
     
    17881851  double * upperBefore = new double [numberColumns] ;
    17891852/*
    1790  
    1791   Generate cuts at the root node and reoptimise. solveWithCuts does the heavy
    1792   lifting. It will iterate a generate/reoptimise loop (including reduced cost
    1793   fixing) until no cuts are generated, the change in objective falls off,  or
    1794   the limit on the number of rounds of cut generation is exceeded.
    1795 
    1796   At the end of all this, any cuts will be recorded in cuts and also
    1797   installed in the solver's constraint system. We'll have reoptimised, and
    1798   removed any slack cuts (numberOldActiveCuts_ and numberNewCuts_ have been
    1799   adjusted accordingly).
    1800 
    1801   Tell cut generators they can be a bit more aggressive at root node
    1802 
    1803   TODO: Why don't we make a copy of the solution after solveWithCuts?
    1804   TODO: If numberUnsatisfied == 0, don't we have a solution?
     1853  Set up to run heuristics and generate cuts at the root node. The heavy
     1854  lifting is hidden inside the calls to doHeuristicsAtRoot and solveWithCuts.
     1855
     1856  To start, tell cut generators they can be a bit more aggressive at the
     1857  root node.
     1858
     1859  QUESTION: phase_ = 0 is documented as `initial solve', phase = 1 as `solve
     1860            with cuts at root'. Is phase_ = 1 the correct indication when
     1861            doHeurisiticsAtRoot is called to run heuristics outside of the main
     1862            cut / heurisitc / reoptimise loop in solveWithCuts?
    18051863*/
    18061864  phase_=1;
     
    18281886  maximumDepthActual_=0;
    18291887  numberDJFixed_=0.0;
     1888/*
     1889  Run heuristics at the root. This is the only opportunity to run FPump; it
     1890  will be removed from the heuristics list by doHeuristicsAtRoot.
     1891*/
     1892# if CBCMODEL_DEBUG > 1
     1893  std::cout
     1894    << "bAB: trying heuristics at root." << std::endl ;
     1895# endif
    18301896  // Do heuristics
    18311897  doHeuristicsAtRoot();
     1898# if CBCMODEL_DEBUG > 1
     1899  std::cout
     1900    << "bAB: finished heuristics at root." << std::endl ;
     1901# endif
     1902/*
     1903  Grepping through the code, it would appear that this is a command line
     1904  debugging hook.  There's no obvious place in the code where this is set to
     1905  a negative value.
     1906*/
    18321907  if ( intParam_[CbcMaxNumNode] < 0)
    18331908    eventHappened_=true; // stop as fast as possible
     
    18441919    //eventHappened_=true; // stop as fast as possible
    18451920  }
     1921/*
     1922  Set up for statistics collection, if requested. Standard values are
     1923  documented in CbcModel.hpp. The magic number 100 will trigger a dump of
     1924  CbcSimpleIntegerDynamicPseudoCost objects (no others). Looks like another
     1925  command line debugging hook.
     1926*/
    18461927  statistics_ = NULL;
    18471928  // Do on switch
     
    21582239    analyzeObjective();
    21592240  }
     2241/*
     2242  Do an initial round of cut generation for the root node. Depending on the
     2243  type of underlying solver, we may want to do this even if the initial query
     2244  to the objects indicates they're satisfied.
     2245
     2246  solveWithCuts does the heavy lifting. It will iterate a generate/reoptimise
     2247  loop (including reduced cost fixing) until no cuts are generated, the
     2248  change in objective falls off,  or the limit on the number of rounds of cut
     2249  generation is exceeded.
     2250
     2251  At the end of all this, any cuts will be recorded in cuts and also
     2252  installed in the solver's constraint system. We'll have reoptimised, and
     2253  removed any slack cuts (numberOldActiveCuts_ and numberNewCuts_ have been
     2254  adjusted accordingly).
     2255*/
    21602256  { int iObject ;
    21612257    int preferredWay ;
     
    30033099  }
    30043100  /*
    3005     It is possible that strong branching fixes one variable and then the code goes round
    3006     again and again.  This can take too long.  So we need to warn user - just once.
     3101    It is possible that strong branching fixes one variable and then the code
     3102    goes round again and again.  This can take too long.  So we need to warn
     3103    user - just once.
    30073104  */
    30083105  numberLongStrong_=0;
     
    34973594    }
    34983595#ifdef BONMIN
    3499     assert(!solverCharacteristics_->solutionAddsCuts() || solverCharacteristics_->mipFeasible());
     3596    assert(!solverCharacteristics_->solutionAddsCuts() ||
     3597           solverCharacteristics_->mipFeasible());
    35003598#endif
    35013599    if (cutoff > getCutoff()) {
     
    44124510#endif
    44134511  moreSpecialOptions_ = saveMoreSpecialOptions;
     4512# if CBCMODEL_DEBUG > 0
     4513  std::cout
     4514    << "CbcModel:bAB: Finished." << std::endl ;
     4515# endif
    44144516  return ;
    44154517 }
     
    59806082                        normal,atSolution,whenInfeasible,howOftenInSub,
    59816083                        whatDepth, whatDepthInSub);
     6084
     6085# if CBC_CUTGEN_TRACE > 0
     6086  std::cout << "Adding generator " << numberCutGenerators_
     6087            << " (" << generator_[numberCutGenerators_]->cutGeneratorName()
     6088            << ")." << std::endl ;
     6089# endif
    59826090  // and before any changes
    59836091  temp = virginGenerator_;
     
    62966404        } else {
    62976405#         ifdef CHECK_CUT_COUNTS
    6298           printf("Dropping cut %d %x\n",i,addedCuts_[i]);
     6406          printf("Dropping %s cut %d %x\n",
     6407                 ((status != CoinWarmStartBasis::basic)?"active":"inactive"),
     6408                 i,addedCuts_[i]);
    62996409#         endif
    63006410          addedCuts_[i]=NULL;
     
    66016711  relaxation and calling solveWithCuts?
    66026712
    6603   If numberTries == 0 then user did not want any cuts.
     6713  If numberTries == 0 then user did not want any cuts. (But see below; loop is
     6714  structured to always execute at least once. -- lh, 080103 --)
    66046715*/
    66056716
     
    66186729
    66196730{
     6731
     6732# if CBCMODEL_DEBUG > 0
     6733  if (handler_->logLevel() < 3)
     6734  { handler_->setLogLevel(3) ; }
     6735  std::cout
     6736    << "CbcModel::sWC: entering." << std::endl ;
     6737  std::cout
     6738    << "  Cbc log level " << handler_->logLevel()
     6739    << ",  solver log level " << solver_->messageHandler()->logLevel()
     6740    << "." << std::endl ;
     6741  std::cout
     6742    << "  Thread mode " << std::hex << threadMode_ << std::dec
     6743    << "." << std::endl ;
     6744# endif
     6745# ifdef NODE_LOG
     6746  int startIters = getIterationCount() ;
     6747# endif
     6748
    66206749#if 0
    66216750  if (node&&numberTries>1) {
     
    66306759  for (int j=0;j<CUT_HISTORY;j++)
    66316760         cut_obj[j]=-COIN_DBL_MAX;
     6761
    66326762# ifdef COIN_HAS_CLP
    66336763  OsiClpSolverInterface * clpSolver
     
    66376767    saveClpOptions = clpSolver->specialOptions();
    66386768# endif
     6769
    66396770  //solver_->writeMps("saved");
     6771
    66406772#ifdef CBC_THREAD
     6773/*
     6774  Thread mode makes a difference here only when it specifies using separate
     6775  threads to generate cuts at the root (bit 2^1 set in threadMode_). In which
     6776  case we'll create an array of empty CbcModels (!). Solvers will be cloned
     6777  later.
     6778*/
    66416779  CbcModel ** threadModel = NULL;
    66426780  Coin_pthread_t * threadId = NULL;
     
    66826820  }
    66836821#endif
     6822
    66846823  bool feasible = true ;
    66856824  int lastNumberCuts = 0 ;
     
    67056844      onOptimalPath = (debugger->onOptimalPath(*solver_)) ;
    67066845  }
     6846
     6847/*
     6848  As the final action in each round of cut generation (the numberTries loop),
     6849  we'll call takeOffCuts to remove slack cuts. These are saved into slackCuts
     6850  and rechecked immediately after the cut generation phase of the loop.
     6851*/
    67076852  OsiCuts slackCuts;
    6708 /*
    6709   Resolve the problem. If we've lost feasibility, might as well bail out right
    6710   after the debug stuff. The resolve will also refresh cached copies of the
    6711   solver solution (cbcColLower_, ...) held by CbcModel.
     6853
     6854/*
     6855  Resolve the problem
     6856
     6857  The resolve will also refresh cached copies of the solver solution
     6858  (cbcColLower_, ...) held by CbcModel.
     6859
     6860  This resolve looks like the best point to capture a warm start for use in
     6861  the case where cut generation proves ineffective and we need to back out
     6862  a few tight cuts.
     6863
     6864  I've always maintained that this resolve is unnecessary. Let's put in a hook
     6865  to report if it's every nontrivial.
    67126866*/
    67136867  double objectiveValue = solver_->getObjValue()*solver_->getObjSense();
     
    67166870  }
    67176871  int returnCode = resolve(node ? node->nodeInfo() : NULL,1);
     6872
    67186873#if COIN_DEVELOP>1
    67196874  //if (!solver_->getIterationCount()&&solver_->isProvenOptimal())
    67206875  //printf("zero iterations on first solve of branch\n");
    67216876#endif
     6877
    67226878  double lastObjective = solver_->getObjValue()*solver_->getObjSense();
    67236879  cut_obj[CUT_HISTORY-1]=lastObjective;
    67246880  //double firstObjective = lastObjective+1.0e-8+1.0e-12*fabs(lastObjective);
     6881
     6882# if CBCMODEL_DEBUG > 1
     6883  if (solver_->isProvenOptimal() && solver_->getIterationCount() > 0)
     6884  { std::cout
     6885      << "CbcModel::sWC: initial resolve required "
     6886      << solver_->getIterationCount() << " iterations." << std::endl ; }
     6887# endif
     6888
     6889/*
     6890  Contemplate the result of the resolve.
     6891    - CbcModel::resolve() has a hook that calls CbcStrategy::status to look
     6892      over the solution. The net result is that resolve can return
     6893      0 (infeasible), 1 (feasible), or -1 (feasible, but do no further work).
     6894    - CbcFeasbililityBase::feasible() can return 0 (no comment),
     6895      1 (pretend this is an integer solution), or -1 (pretend this is
     6896      infeasible). As of 080104, this seems to be a stub to allow overrides,
     6897      with a default implementation that always returns 0.
     6898
     6899  Setting numberTries = 0 for `do no more work' is problematic. The main cut
     6900  generation loop will still execute once, so we do not observe the `no
     6901  further work' semantics.
     6902
     6903  As best I can see, allBranchesGone is a null function as of 071220.
     6904*/
    67256905  if (node&&node->nodeInfo()&&!node->nodeInfo()->numberBranchesLeft())
    67266906    node->nodeInfo()->allBranchesGone(); // can clean up
     
    67316911    feasible=false; // pretend infeasible
    67326912  }
    6733  
     6913/*
     6914  NEW_UPDATE_OBJECT is defined to 0 when unthreaded (CBC_THREAD undefined), 2
     6915  when threaded. No sign of 1 as of 071220.
     6916
     6917  At present, there are two sets of hierarchies for branching classes. Call
     6918  them CbcHier and OsiHier. For example, we have OsiBranchingObject, with
     6919  children CbcBranchingObject and OsiTwoWayBranchingObject. All
     6920  specialisations descend from one of these two children. Similarly, there is
     6921  OsiObject, with children CbcObject and OsiObject2.
     6922
     6923  In the original setup, there's a single CbcBranchDecision object attached
     6924  to CbcModel (branchingMethod_). It has a field to hold the current CbcHier
     6925  branching object, and the updateInformation routine reaches through the
     6926  branching object to update the underlying CbcHier object.
     6927
     6928  NEW_UPDATE_OBJECT = 0 would seem to assume the original setup. But,
     6929  if we're using the OSI hierarchy for objects and branching, a call to a
     6930  nontrivial branchingMethod_->updateInformation would have no effect (it
     6931  would expect a CbcObject to work on) or perhaps crash.  For the
     6932  default CbcBranchDefaultDecision, updateInformation is a noop (actually
     6933  defined in the base CbcBranchDecision class).
     6934
     6935  NEW_UPDATE_OBJECT = 2 looks like it's prepared to cope with either CbcHier or
     6936  OsiHier, but it'll be executed only when threads are activated. See the
     6937  comments below. The setup is scary.
     6938
     6939  But ... if the OsiHier update actually reaches right through to the object
     6940  list in the solver, it should work just fine in unthreaded mode. It would
     6941  seem that the appropriate thing to do in unthreaded mode would be to choose
     6942  between the existing code for NEW_UPDATE_OBJECT = 0 and the OsiHier code for
     6943  NEW_UPDATE_OBJECT = 2. But I'm going to let John hash that out. The worst
     6944  that can happen is inefficiency because I'm not properly updating an object.
     6945*/
     6946# if CBCMODEL_DEBUG > 2
     6947  std::cout
     6948    << "CbcModel::sWC: object update type " << NEW_UPDATE_OBJECT
     6949    << ", node " << std::hex << node
     6950    << ", branchingMethod_ " << branchingMethod_
     6951    << std::dec << "." << std::endl ;
     6952# endif
    67346953  // Update branching information if wanted
    67356954  if(node &&branchingMethod_) {
     
    68427061 
    68437062  else
    6844   { printf("Infeasible %d rows\n",solver_->getNumRows()) ; }
     7063  { printf("Infeasible %d rows, return code %d\n",
     7064           solver_->getNumRows(),returnCode) ; }
    68457065#endif
    68467066  if ((specialOptions_&1)!=0) {
     
    69547174  bool increaseDrop = (moreSpecialOptions_&8192)!=0;
    69557175/*
    6956   Begin cut generation loop. Cuts generated during each iteration are
    6957   collected in theseCuts. The loop can be divided into four phases:
     7176  Begin main cut generation loop (the `numberTries loop').
     7177 
     7178  Cuts generated during each iteration are collected in theseCuts. The loop
     7179  can be divided into four phases:
    69587180   1) Prep: Fix variables using reduced cost. In the first iteration only,
    69597181      consider scanning globalCuts_ and activating any applicable cuts.
     
    69687190  do
    69697191  { currentPassNumber_++ ;
     7192#   if CBCMODEL_DEBUG > 1
     7193    std::cout
     7194      << "CbcModel::sWC: pass " << currentPassNumber_
     7195      << " of cut generation loop." << std::endl ;
     7196#   endif
    69707197    numberTries-- ;
    69717198    if (numberTries<0&&keepGoing) {
     
    69887215      int numberCuts = globalCuts_.sizeColCuts() ;
    69897216      int i;
     7217#     if CBCMODEL_DEBUG > 1
     7218      std::cout
     7219        << "CbcModel::sWC: scanning global cuts; "
     7220        << globalCuts_.sizeRowCuts() << " row, "
     7221        << globalCuts_.sizeColCuts() << " col." << std::endl ;
     7222#     endif
    69907223      // possibly extend whichGenerator
    69917224      resizeWhichGenerator(numberViolated, numberViolated+numberCuts);
     
    70377270
    70387271  The need to resolve here should only happen after a heuristic solution.
    7039   (Note default OSI implementation of optimalBasisIsAvailable always returns
    7040   false.)
     7272
     7273  optimalBasisIsAvailable resolves to basisIsAvailable, which seems to be part
     7274  of the old OsiSimplex API. Doc'n says `Returns true if a basis is available
     7275  and the problem is optimal. Should be used to see if the BinvARow type
     7276  operations are possible and meaningful.' Which means any solver other the clp
     7277  is probably doing a lot of unnecessary resolves right here.
    70417278*/
    70427279    if (solverCharacteristics_->warmStart()&&
    70437280        !solver_->optimalBasisIsAvailable()) {
    7044       //printf("XXXXYY no opt basis\n");
    70457281#if 0//def COIN_HAS_CLP
    70467282      //OsiClpSolverInterface * clpSolver
     
    70537289#endif
    70547290      resolve(node ? node->nodeInfo() : NULL,3);
     7291
     7292#     if CBC_DEBUG
     7293      std::cout
     7294        << "CbcModel::sWC: XXXXYY resolve iters = "
     7295        << solver_->getIterationCount() << "." << std::endl ;
     7296#     endif
     7297
    70557298#if 0//def COIN_HAS_CLP
    70567299      if (clpSolver)
     
    70637306#endif
    70647307#endif
     7308
    70657309    }
    70667310    if (nextRowCut_) {
     
    70977341    //probingInfo_->initializeFixing();
    70987342    int i;
     7343/*
     7344  threadMode with bit 2^1 set indicates we should use threads for root cut
     7345  generation.
     7346*/
    70997347    if ((threadMode_&2)==0||numberNodes_) {
     7348#     if CBCMODEL_DEBUG > 1
     7349      std::cout
     7350        << "CbcModel::sWC: unthreaded cut loop, "
     7351        << numberNodes_ << " nodes." << std::endl ;
     7352#     endif
    71007353# ifdef COIN_HAS_CLP
    71017354      if (!node&&!parentModel_&& intParam_[CbcMaxNumNode] == -123456) {
     
    71407393          generator_[i]->setIneffectualCuts(false);
    71417394          numberRowCutsAfter = theseCuts.sizeRowCuts() ;
     7395
     7396#         if CBCMODEL_DEBUG > 2
     7397          std::cout
     7398            << "CbcModel::sWC: ran generator " << i
     7399            << " (" << generator_[i]->cutGeneratorName()
     7400            << "), " << numberRowCutsAfter-numberRowCutsBefore << " cuts, "
     7401            << "mustResolve = " << mustResolve << "." << std::endl ;
     7402#         endif
     7403
    71427404          if (fullScan&&generator_[i]->howOften()==1000000+SCANCUTS_PROBING) {
    71437405            CglProbing * probing =
     
    71607422            if (thisCut->lb()>thisCut->ub()) {
    71617423              feasible = false; // sub-problem is infeasible
     7424#             if CBCMODEL_DEBUG > 2
     7425              std::cout
     7426                << "CbcModel::sWC: generator reports infeasible."
     7427                << std::endl ;
     7428#             endif
    71627429              break;
    71637430            }
    71647431          }
    71657432#ifdef CBC_DEBUG
    7166           {
    7167             int k ;
    7168             for (k = numberRowCutsBefore;k<numberRowCutsAfter;k++) {
    7169               OsiRowCut thisCut = theseCuts.rowCut(k) ;
    7170               /* check size of elements.
    7171                  We can allow smaller but this helps debug generators as it
    7172                  is unsafe to have small elements */
    7173               int n=thisCut.row().getNumElements();
    7174               const int * column = thisCut.row().getIndices();
    7175               const double * element = thisCut.row().getElements();
    7176               //assert (n);
    7177               for (int i=0;i<n;i++) {
    7178                 double value = element[i];
    7179                 assert(fabs(value)>1.0e-12&&fabs(value)<1.0e20);
    7180               }
    7181             }
    7182           }
     7433          {
     7434            int k ;
     7435            bool badCut = false ;
     7436            for (k = numberRowCutsBefore;k<numberRowCutsAfter;k++) {
     7437              OsiRowCut thisCut = theseCuts.rowCut(k) ;
     7438              /* check size of elements.
     7439                 We can allow smaller but this helps debug generators as it
     7440                 is unsafe to have small elements */
     7441              int n=thisCut.row().getNumElements();
     7442              const int * column = thisCut.row().getIndices();
     7443              const double * element = thisCut.row().getElements();
     7444              //assert (n);
     7445              for (int i=0;i<n;i++) {
     7446                double value = element[i];
     7447                if (fabs(value)<1.0e-12||fabs(value)>1.0e20) {
     7448                  std::cout
     7449                    << "Bad coefficient " << value << " in cut "
     7450                    << k << "." << std::endl ;
     7451                  thisCut.print() ;
     7452                  badCut = true ;
     7453                }
     7454              }
     7455            }
     7456            assert(badCut == false);
     7457          }
    71837458#endif
    71847459          if (mustResolve) {
     
    72307505        }
    72317506/*
    7232   The cut generator has done its thing, and maybe it generated some
    7233   cuts.  Do a bit of bookkeeping: load
    7234   whichGenerator[i] with the index of the generator responsible for a cut,
    7235   and place cuts flagged as global in the global cut pool for the model.
     7507  The cut generator has done its thing, and maybe it generated some cuts.  Do
     7508  a bit of bookkeeping: load whichGenerator[i] with the index of the
     7509  generator responsible for a cut, and place cuts flagged as global in the
     7510  global cut pool for the model.
    72367511
    72377512  lastNumberCuts is the sum of cuts added in previous iterations; it's the
     
    72967571        }
    72977572      }
     7573
     7574#     if CBCMODEL_DEBUG > 1
     7575      std::cout
     7576        << "CbcModel::sWC: unthreaded cut loop end." << std::endl ;
     7577#     endif
     7578/*
     7579  End of loop to run each cut generator.
     7580*/
     7581
    72987582      if (!node) {
    72997583        handler_->message(CBC_ROOT_DETAIL,messages_)
     
    74537737    } else {
    74547738      // do cuts independently
     7739#     if CBCMODEL_DEBUG > 1
     7740      std::cout
     7741        << "CbcModel::sWC: threaded cut loop, "
     7742        << numberNodes_ << " nodes." << std::endl ;
     7743#     endif
    74557744      OsiCuts * eachCuts = new OsiCuts [numberCutGenerators_];;
    74567745#ifdef CBC_THREAD
     
    76297918        }
    76307919/*
    7631   The cut generator has done its thing, and maybe it generated some
    7632   cuts.  Do a bit of bookkeeping: load
    7633   whichGenerator[i] with the index of the generator responsible for a cut,
    7634   and place cuts flagged as global in the global cut pool for the model.
     7920  The cut generator has done its thing, and maybe it generated some cuts.  Do
     7921  a bit of bookkeeping: load whichGenerator[i] with the index of the
     7922  generator responsible for a cut, and place cuts flagged as global in the
     7923  global cut pool for the model.
    76357924
    76367925  lastNumberCuts is the sum of cuts added in previous iterations; it's the
     
    77097998                                  newSolution);
    77107999                                  //theseCuts) ;
     8000#       if CBCMODEL_DEBUG > 2
     8001        std::cout
     8002          << "CbcModel::sWC: ran heuristic "
     8003          << i << " (" << heuristic_[i]->heuristicName()
     8004          << "). " << std::endl ;
     8005#       endif
    77118006        if (ifSol>0) {
    77128007          // better solution found
     
    80938388    }
    80948389  } while (numberTries>0||keepGoing) ;
     8390#   if CBCMODEL_DEBUG > 1
     8391    std::cout
     8392      << "CbcModel::sWC: end cut generation loop."
     8393      << std::endl ;
     8394#   endif
     8395/*
     8396  End cut generation loop.
     8397*/
    80958398  {
    80968399    // switch on
     
    81068409  if(feasible&&solverCharacteristics_->solutionAddsCuts())  //check integer feasibility
    81078410  {
     8411#   if CBCMODEL_DEBUG > 1
     8412    std::cout
     8413      << "CbcModel::sWC: solution adds cuts; verifying."
     8414      << std::endl ;
     8415#   endif
    81088416    bool integerFeasible = true;
    81098417    const double * save = testSolution_;
     
    81738481  }
    81748482/*
    8175   Reduced cost fix at end. Must also check feasible, in case we've popped out
    8176   because a generator indicated we're infeasible.
     8483  End of code block to check for a solution, when cuts may be added as a result
     8484  of a feasible solution.
     8485
     8486  Reduced cost fix at end. Must also check feasible, in case we've popped
     8487  out because a generator indicated we're infeasible.
    81778488*/
    81788489  if (feasible && solver_->isProvenOptimal())
    81798490    reducedCostFix() ;
    8180   // If at root node do heuristics
     8491/*
     8492  If we're at the root, try heuristics.
     8493*/
    81818494  if (!numberNodes_&&!maximumSecondsReached()) {
     8495#   if CBCMODEL_DEBUG > 1
     8496    std::cout
     8497      << "CbcModel::sWC: trying heuristics at root." << std::endl ;
     8498#   endif
    81828499    // First see if any cuts are slack
    81838500    int numberRows = solver_->getNumRows();
     
    82458562  //if ((numberNodes_%100)==0)
    82468563  //printf("XXb sum obj changed by %g\n",sumChangeObjective2_);
    8247 /*
    8248   End of cut generation loop.
    8249 
    8250   Now, consider if we want to disable or adjust the frequency of use for any
    8251   of the cut generators. If the client specified a positive number for
    8252   howOften, it will never change. If the original value was negative, it'll
    8253   be converted to 1000000+|howOften|, and this value will be adjusted each
    8254   time fullScan is true. Actual cut generation is performed every
    8255   howOften%1000000 nodes; the 1000000 offset is just a convenient way to
    8256   specify that the frequency is adjustable.
     8564
     8565# ifdef NODE_LOG
     8566/*
     8567  I've beefed this up a bit so that it once again compiles.  -- lh, 080422 --
     8568*/
     8569  { int fatherNum = -1 ;
     8570    double value = -1 ;
     8571    std::string wayStr = "" ;
     8572    const OsiTwoWayBranchingObject *osi2bo = NULL ;
     8573
     8574    if (node != NULL)
     8575    { fatherNum = node->nodeNumber() ;
     8576      value = node->branchingObject()->value() ;
     8577      osi2bo = dynamic_cast<const OsiTwoWayBranchingObject *>(node->branchingObject()) ;
     8578      if (osi2bo != NULL && osi2bo->way() == 1)
     8579        wayStr = "Up" ;
     8580      else
     8581        wayStr = "Down" ; }
     8582
     8583    if (solver_->getIterationCount() > 30)
     8584      std::cout << "*******" << std::endl ;
     8585
     8586    std::cout
     8587      << "Node " << numberNodes_ << ", father " << fatherNum
     8588      << ", " << wayStr << " branch from x = " << value
     8589      << ", #iterations " << getIterationCount()-startIters
     8590      << ", z = " << solver_->getObjValue()
     8591      << std::endl ;
     8592  }
     8593# endif
     8594
     8595/*
     8596  Is this a full scan interval? If so, consider if we want to disable or
     8597  adjust the frequency of use for any of the cut generators. If the client
     8598  specified a positive number for howOften, it will never change. If the
     8599  original value was negative, it'll be converted to 1000000+|howOften|, and
     8600  this value will be adjusted each time fullScan is true. Actual cut
     8601  generation is performed every howOften%1000000 nodes; the 1000000 offset is
     8602  just a convenient way to specify that the frequency is adjustable.
    82578603
    82588604  During cut generation, we recorded the number of cuts produced by each
     
    82618607
    82628608  TODO: All this should probably be hidden in a method of the CbcCutGenerator
    8263   class.
    8264 
    8265 */
    8266 #ifdef NODE_LOG
    8267   int fatherNum = (node == NULL) ? -1 : node->nodeNumber();
    8268   double value =  (node == NULL) ? -1 : node->branchingObject()->value();
    8269   string bigOne = (solver_->getIterationCount() > 30) ? "*******" : "";
    8270   string way = (node == NULL) ? "" : (node->branchingObject()->way())==1 ? "Down" : "Up";
    8271   std::cout<<"Node "<<numberNodes_<<", father "<<fatherNum<<", #iterations "<<solver_->getIterationCount()<<", sol value : "<<solver_->getObjValue()<<std::endl;
    8272 #endif
     8609        class.
     8610
     8611  TODO: Can the loop that scans over whichGenerator to accumulate per
     8612        generator counts be replaced by values in countRowCuts and
     8613        countColumnCuts?
     8614
     8615        << I think the answer is yes, but not the other way 'round. Row and
     8616           column cuts are block interleaved in whichGenerator. >>
     8617
     8618  The root is automatically a full scan interval. At the root, decide if
     8619  we're going to do cuts in the tree, and whether we should keep the cuts we
     8620  have.
     8621
     8622  Codes for willBeCutsInTree:
     8623    -1: no cuts in tree and currently active cuts seem ineffective; delete
     8624        them
     8625     0: no cuts in tree but currently active cuts seem effective; make them
     8626        into architecturals (faster than treating them as cuts)
     8627     1: cuts will be generated in the tree; currently active cuts remain as
     8628        cuts
     8629*/
    82738630  if (fullScan&&numberCutGenerators_) {
     8631#   if CBCMODEL_DEBUG > 1
     8632    std::cout
     8633      << "CbcModel::sWC: adjusting cut generator frequencies."
     8634      << std::endl ;
     8635#   endif
    82748636    /* If cuts just at root node then it will probably be faster to
    82758637       update matrix and leave all in */
     
    82828644    double densityNew = numberRowsAdded ? (static_cast<double> (numberElementsAdded))/static_cast<double> (numberRowsAdded)
    82838645      : 0.0;
     8646/*
     8647  If we're at the root, and we added cuts, and the cuts haven't changed the
     8648  objective, and the cuts resulted in a significant increase (> 20%) in nonzero
     8649  coefficients, do no cuts in the tree and ditch the current cuts. They're not
     8650  cost-effective.
     8651*/
    82848652    if (!numberNodes_) {
    82858653      if (numberRowsAdded)
     
    83988766      }
    83998767    }
     8768/*
     8769  Noop block 071219.
     8770*/
    84008771    if ((numberRowsAdded>100+0.5*numberRowsAtStart
    84018772         ||numberElementsAdded>0.5*numberElementsAtStart)
     
    84078778      //     numberRowsAdded,densityNew);
    84088779    }
     8780/*
     8781  Noop block 071219.
     8782*/
    84098783    if (densityNew>100.0&&numberRowsAdded>2&&densityNew>2.0*densityOld) {
    84108784      //if (thisObjective-startObjective<0.1*fabs(startObjective)+1.0e-5)
     
    84148788    }
    84158789    // Root node or every so often - see what to turn off
     8790/*
     8791  Hmmm ... > -90 for any generator will overrule previous decision to do no
     8792  cuts in tree and delete existing cuts.
     8793*/
    84168794    int i ;
    84178795    for (i = 0;i<numberCutGenerators_;i++) {
     
    84268804        <<currentPassNumber_
    84278805        <<CoinMessageEol ;
     8806/*
     8807  Count the number of cuts produced by each cut generator on this call. Not
     8808  clear to me that the accounting is equivalent here. whichGenerator_ records
     8809  the generator for column and row cuts. So unless numberNewCuts is row cuts
     8810  only, we're double counting for JUST_ACTIVE. Note too the multiplier applied
     8811  to column cuts.
     8812*/
    84288813    if (!numberNodes_) {
    84298814      double value = CoinMax(minimumDrop_,0.005*(thisObjective-startObjective)/
     
    84568841      totalCuts += value;
    84578842    }
     8843/*
     8844  Open up a loop to step through the cut generators and decide what (if any)
     8845  adjustment should be made for calling frequency.
     8846*/
    84588847    int iProbing=-1;
    84598848    double smallProblem = (0.2* totalCuts) /
     
    84618850    for (i = 0;i<numberCutGenerators_;i++) {
    84628851      int howOften = generator_[i]->howOften() ;
    8463       /*  Probing can be set to just do column cuts in treee.
    8464           But if doing good then leave as on */
     8852/*
     8853  Probing can be set to just do column cuts in tree.  But if doing good then
     8854  leave as on.
     8855
     8856  Ok, let me try to explain this. rowCuts = 3 says do disaggregation (1<<0) and
     8857  coefficient (1<<1) cuts. But if the value is negative, there's code at the
     8858  entry to generateCuts, and generateCutsAndModify, that temporarily changes
     8859  the value to 4 (1<<2) if we're in a search tree.
     8860
     8861  Which does nothing to explain this next bit. We set a boolean, convert
     8862  howOften to the code for `generate while objective is improving', and change
     8863  over to `do everywhere'. Hmmm ... now I write it out, this makes sense in the
     8864  context of the original comment. If we're doing well (objective improving)
     8865  we'll keep probing fully active.
     8866*/
    84658867      bool probingWasOnBut=false;
    84668868      CglProbing * probing = dynamic_cast<CglProbing*>(generator_[i]->generator());
     
    84788880        }
    84798881      }
     8882/*
     8883  Convert `as long as objective is improving' into `only at root' if we've
     8884  decided cuts just aren't worth it.
     8885*/
    84808886      if (willBeCutsInTree<0&&howOften==-98)
    84818887        howOften =-99;
     8888
     8889/*
     8890  And check to see if the objective is improving. But don't do the check if
     8891  the user has specified some minimum number of cuts.
     8892
     8893  This exclusion seems bogus, or at least counterintuitive. Why would a user
     8894  suspect that setting a minimum cut limit would invalidate the objective
     8895  check? Nor do I see the point in comparing the number of rows and columns
     8896  in the second test.
     8897*/
     8898
    84828899      if (!probing&&howOften==-98&&!generator_[i]->numberShortCutsAtRoot()&&
    84838900          generator_[i]->numberCutsInTotal()) {
     
    84938910          howOften=-99; // switch off
    84948911      }
     8912/*
     8913  Below -99, this generator is switched off. There's no need to consider
     8914  further. Then again, there was no point in persisting this far!
     8915*/
    84958916      if (howOften<-99)
    84968917        continue ;
     8918/*
     8919  Adjust, if howOften is adjustable.
     8920*/
    84978921      if (howOften<0||howOften >= 1000000) {
    84988922        if( !numberNodes_) {
     8923/*
     8924  If root only, or objective improvement but no cuts generated, switch off. If
     8925  it's just that the generator found no cuts at the root, give it one more
     8926  chance.
     8927*/
    84998928          // If small number switch mostly off
    85008929#ifdef JUST_ACTIVE
     
    85228951              }
    85238952            }
     8953/*
     8954  Not productive, but not zero either.
     8955*/
    85248956          } else if ((thisCuts+generator_[i]->numberColumnCuts()<smallProblem)
    8525                      &&!generator_[i] ->whetherToUse()) {
     8957                     &&!generator_[i]->whetherToUse()) {
     8958/*
     8959  Not unadjustable every node, and not strong probing.
     8960*/
    85268961            if (howOften!=1&&!probingWasOnBut) {
     8962/*
     8963  No depth spec, or not adjustable every node.
     8964*/
    85278965              if (generator_[i]->whatDepth()<0||howOften!=-1) {
    85288966                int k = static_cast<int> (sqrt(smallProblem/thisCuts)) ;
     8967/*
     8968  Not objective improvement, set to new frequency, otherwise turn off.
     8969*/
    85298970                if (howOften!=-98)
    85308971                  howOften = k+1000000 ;
    85318972                else
    85328973                  howOften=-100;
     8974/*
     8975  Depth spec, or adjustable every node. Force to unadjustable every node.
     8976*/
    85338977              } else {
    85348978                howOften=1;
    85358979              }
     8980/*
     8981  Unadjustable every node, or strong probing. Force unadjustable every node and
     8982  force not strong probing? I don't understand.
     8983*/
    85368984            } else {
    85378985              howOften=1;
     
    85398987              probingWasOnBut=false;
    85408988            }
    8541           } else {
     8989/*
     8990  Productive cut generator. Say we'll do it every node, adjustable. But if the
     8991  objective isn't improving, restrict that to every fifth depth level
     8992  (whatDepth overrides howOften in generateCuts).
     8993*/
     8994          } else {
    85428995            if (thisObjective-startObjective<0.1*fabs(startObjective)+1.0e-5&&generator_[i]->whatDepth()<0)
    85438996              generator_[i]->setWhatDepth(5);
     
    85458998          }
    85468999        }
     9000/*
     9001  End root actions.
     9002
     9003  sumChangeObjective2_ is the objective change due to cuts. If we're getting
     9004  much better results from branching over a large number of nodes, switch off
     9005  cuts.
     9006
     9007  Except it doesn't, really --- it just puts off the decision 'til the
     9008  next full scan, when it'll put it off again unless cuts look better.
     9009*/
    85479010        // If cuts useless switch off
    85489011        if (numberNodes_>=100000&&sumChangeObjective1_>2.0e2*(sumChangeObjective2_+1.0e-12)) {
     
    85519014        }
    85529015      }
     9016/*
     9017  Ok, that's the frequency adjustment bit.
     9018
     9019  Now, if we're at the root, force probing back on at every node, for column
     9020  cuts at least, even if it looks useless for row cuts. Notice that if it
     9021  looked useful, the values set above mean we'll be doing strong probing in
     9022  the tree subject to objective improvement.
     9023*/
    85539024      if (!numberNodes_) {
    85549025        if (probingWasOnBut&&howOften==-100) {
     
    85629033          willBeCutsInTree=1;
    85639034      }
     9035/*
     9036  Set the new frequency in the generator. If this is an adjustable frequency,
     9037  use the value to set whatDepth.
     9038
     9039  Hey! Seems like this could override the user's depth setting.
     9040*/
    85649041      generator_[i]->setHowOften(howOften) ;
    85659042      if (howOften>=1000000&&howOften<2000000&&0) {
     
    86029079      }
    86039080    }
     9081/*
     9082  End loop to adjust cut generator frequency of use.
     9083*/
    86049084    delete [] count ;
    86059085    if( !numberNodes_) {
     
    86099089        generator_[i]->setNumberActiveCutsAtRoot(generator_[i]->numberCutsActive());
    86109090      }
     9091/*
     9092  Garbage code 071219
     9093*/
    86119094      // decide on pseudo cost strategy
    86129095      int howOften = iProbing>=0 ? generator_[iProbing]->howOften() : 0;
     
    86339116      if (willBeCutsInTree==-2)
    86349117        willBeCutsInTree=0;
     9118/*
     9119  End garbage code.
     9120
     9121  Now I've reached the problem area. This is a problem only at the root node,
     9122  so that should simplify the issue of finding a workable basis? Or maybe not.
     9123*/
    86359124      if( willBeCutsInTree<=0) {
    86369125        // Take off cuts
     
    87199208#ifdef CBC_THREAD
    87209209  if (threadModel) {
     9210#   if CBCMODEL_DEBUG > 1
     9211    std::cout
     9212      << "CbcModel::sWC: stopping " << numberThreads << " threads."
     9213      << std::endl ;
     9214#   endif
    87219215    // stop threads
    87229216    int i;
     
    87679261  setPointers(solver_);
    87689262
     9263# if CBCMODEL_DEBUG > 0
     9264  std::cout
     9265    << "CbcModel::sWC: leaving, feasible = "
     9266    << feasible << std::endl ;
     9267# endif
     9268
    87699269  return feasible ; }
     9270
    87709271
    87719272
     
    89439444      numberOldActiveCuts_ -= numberOldToDelete ;
    89449445#     ifdef CBC_DEBUG
    8945       printf("takeOffCuts: purged %d+%d cuts\n", numberOldToDelete,
    8946              numberNewToDelete );
     9446      printf("takeOffCuts: purged %d+%d cuts; resolve %s.\n",
     9447             numberOldToDelete,numberNewToDelete,
     9448             ((allowResolve)?"allowed":"forbidden"));
    89479449#     endif
    89489450      if (allowResolve)
     
    89759477}
    89769478
     9479/*
     9480  Return values:
     9481    1:  feasible
     9482    0:  infeasible
     9483   -1:  feasible and finished (do no more work on this subproblem)
     9484*/
     9485
    89779486int
    89789487CbcModel::resolve(CbcNodeInfo * parent, int whereFrom,
     
    89819490                  double * saveUpper)
    89829491{
     9492
     9493# if CBCMODEL_DEBUG > 2
     9494  std::cout << "CbcModel::resolve: entering." << std::endl ;
     9495# endif
     9496
    89839497#ifdef CBC_STATISTICS
    89849498  void cbc_resolve_check(const OsiSolverInterface * solver);
    89859499  cbc_resolve_check(solver_);
    89869500#endif
     9501
    89879502  // We may have deliberately added in violated cuts - check to avoid message
    89889503  int iRow;
     
    89959510      feasible=false;
    89969511  }
     9512# if CBCMODEL_DEBUG > 2
     9513  std::cout
     9514    << "CbcModel::resolve: after row cuts check feas = "
     9515    << feasible << std::endl ;
     9516# endif
    89979517  // Can't happen if strong branching as would have been found before
    89989518  if (!numberStrong_&&numberObjects_>numberIntegers_) {
     
    91649684        feasible=false;
    91659685      }
     9686#     if CBCMODEL_DEBUG > 2
     9687      std::cout
     9688        << "CbcModel::resolve: solver says "
     9689        << "proven optimal " << solver_->isProvenOptimal()
     9690        << ", dual obj limit " << solver_->isDualObjectiveLimitReached()
     9691        << ", feasible " << feasible << "." << std::endl ;
     9692#     endif
    91669693    }
    91679694  if (0&&feasible) {
     
    92909817  int returnStatus = feasible ? 1 : 0;
    92919818  if (strategy_) {
     9819/*
     9820  Possible returns from status:
     9821    -1: no recommendation
     9822     0: treat as optimal
     9823     1: treat as optimal and finished (no more resolves, cuts, etc.)
     9824     2: treat as infeasible.
     9825*/
    92929826    // user can play clever tricks here
    92939827    int status = strategy_->status(this,parent,whereFrom);
     
    93019835    }
    93029836  }
     9837# if CBCMODEL_DEBUG > 2
     9838  std::cout
     9839    << "CbcModel::resolve: finished, status " << returnStatus
     9840    << "." << std::endl ;
     9841# endif
    93039842  return returnStatus ;
    93049843}
     
    93629901  const double * rowUpper = getRowUpper();
    93639902
     9903/*
     9904  Scan the rows, looking for individual rows that are clique constraints.
     9905*/
    93649906  for (iRow=0;iRow<numberRows;iRow++) {
    93659907    int numberP1=0, numberM1=0;
     
    93699911    bool good=true;
    93709912    int slack = -1;
     9913/*
     9914  Does this row qualify? All variables must be binary and all coefficients
     9915  +/- 1.0. Variables with positive coefficients are recorded at the low end of
     9916  which, variables with negative coefficients the high end.
     9917*/
    93719918    for (j=rowStart[iRow];j<rowStart[iRow]+rowLength[iRow];j++) {
    93729919      int iColumn = column[j];
     
    93999946    int iUpper = static_cast<int> (floor(upperValue+1.0e-5));
    94009947    int iLower = static_cast<int> (ceil(lowerValue-1.0e-5));
     9948/*
     9949  What do we have? If the row upper bound is greater than 1-numberM1, this
     9950  isn't a clique. If the row upper bound is 1-numberM1, we have the classic
     9951  clique (an SOS1 on binary variables, if numberM1 = 0). If the upper bound
     9952  equals numberM1, we can fix all variables. If the upper bound is less than
     9953  numberM1, we're infeasible.
     9954 
     9955  A similar analysis applies using numberP1 against the lower bound.
     9956*/
    94019957    int state=0;
    94029958    if (upperValue<1.0e6) {
     
    94169972        state=-3;
    94179973    }
     9974/*
     9975  What to do? If we learned nothing, move on to the next iteration. If we're
     9976  infeasible, we're outta here. If we decided we can fix variables, do it.
     9977*/
    94189978    if (good&&state) {
    94199979      if (abs(state)==3) {
     
    944010000        }
    944110001      } else {
     10002/*
     10003  And the final case: we have a clique constraint. If it's within the allowed
     10004  size range, make a clique object.
     10005*/
    944210006        int length = numberP1+numberM1;
    944310007        if (length >= atLeastThisMany&&length<lessThanThis) {
     
    944510009          bool addOne=false;
    944610010          int objectType;
     10011/*
     10012  Choose equality (type 1) or inequality (type 0). If we're forcing equalities,
     10013  add a slack.
     10014*/
    944710015          if (iLower==iUpper) {
    944810016            objectType=1;
     
    945710025            }
    945810026          }
     10027/*
     10028  Record the strong values for the variables. Variables with positive
     10029  coefficients force all others when set to 1; variables with negative
     10030  coefficients force when set to 0. If the clique is formed against the row
     10031  lower bound, convert to the canonical form of a clique against the row
     10032  upper bound.
     10033*/
    945910034          if (state>0) {
    946010035            totalP1 += numberP1;
     
    952110096  }
    952210097#endif
     10098/*
     10099  If required, augment the constraint matrix with clique slacks. Seems like we
     10100  should be able to add the necessary integer objects without a complete
     10101  rebuild of existing integer objects, but I'd need to look further to confirm
     10102  that (lh, 071219). Finally, add the clique objects.
     10103*/
    952310104  if (numberCliques>0&&numberSlacks&&makeEquality) {
    952410105    printf("adding %d integer slacks\n",numberSlacks);
     
    997710558
    997810559/*!
    9979   Ensure all attached objects (OsiObjects, heuristics, and cut
     10560  Ensure all attached objects (CbcObjects, heuristics, and cut
    998010561  generators) point to this model.
    998110562*/
     
    1223812819  solver->resolve();
    1223912820#endif
     12821# if CBCMODEL_DEBUG > 0
     12822  std::cout
     12823    << "CbcModel::resolve(2): solver says "
     12824    << solver->isProvenOptimal() << "." << std::endl ;
     12825# endif
    1224012826  return solver->isProvenOptimal() ? 1 : 0;
    1224112827}
    1224212828
    1224312829// Set log level
     12830/*!
     12831    \todo It'd be really nice if there were an overload for this method that
     12832          allowed a separate value for the underlying solver's log level. The
     12833          overload could be coded to allow an increase in the log level of the
     12834          underlying solver.
     12835
     12836          It's worth contemplating whether OSI should have a setLogLevel method
     12837          that's more specific than the hint mechanism.
     12838*/
    1224412839void
    1224512840CbcModel::setLogLevel(int value)
     
    1225112846    if (value<oldLevel)
    1225212847      solver_->messageHandler()->setLogLevel(value);
     12848#   if CBCMODEL_DEBUG > 0
     12849    std::cout
     12850      << "CbcModel::setLogLevel: solver log level was "
     12851      << oldLevel << ", attempting " << value
     12852      << ", result " << solver_->messageHandler()->logLevel()
     12853      << "." << std::endl ;
     12854#   endif
    1225312855#ifdef COIN_HAS_CLP
    1225412856    OsiClpSolverInterface * clpSolver
     
    1233312935  return CoinCpuTime()-getDblParam(CbcStartSeconds);
    1233412936}
    12335 /* Encapsulates choosing a variable -
    12336    anyAction -2, infeasible (-1 round again), 0 done
     12937/* Encapsulates choosing a variable - returns
     12938   anyAction: -2 infeasible
     12939              -1 round again
     12940               0 done
     12941
     12942   At the point where chooseBranch is called, we've decided that this problem
     12943   will need to be placed in the live set and we need to choose a branching
     12944   variable.
     12945
     12946   Parameters:
     12947     newNode:   the node just created for the active subproblem.
     12948     oldNode:   newNode's parent.
     12949     lastws:    oldNode's basis
     12950     lowerBefore, upperBefore: column bound arrays for oldNode
     12951     cuts:      list of cuts added to newNode.
     12952
     12953     resolved:  (o)  set to true if newNode is resolved during processing
     12954     branches:  (o) will be filled in with ... ? Null on entry
    1233712955*/
    1233812956int
     
    1235112969    4 - no solution but many nodes
    1235212970       add 10 if depth >= K
     12971
     12972    K is currently hardcoded to 8, a few lines below.
     12973
     12974    CBCMODEL_DEBUG: Seems like stateOfSearch_ should be 2 if
     12975               numberHeuristicSolutions_ == numberSolutions_.
    1235312976  */
    1235412977  stateOfSearch_=1;
     
    1239913022#endif
    1240013023  currentNode_=newNode; // so can be used elsewhere
     13024/*
     13025  Enough preparation. Get down to the business of choosing a branching
     13026  variable.
     13027*/
    1240113028  while (anyAction == -1) {
    1240213029    // Set objective value (not so obvious if NLP etc)
     
    1240413031    //if (numberPassesLeft<=0)
    1240513032    //branchingState=1;
     13033/*
     13034  Is there a CbcBranchDecision object installed? Does it specify a
     13035  chooseVariable method? If not, we're using the old (Cbc) side of the branch
     13036  decision hierarchy.  In quick summary, CbcNode::chooseBranch uses strong
     13037  branching on any objects, while CbcNode::chooseDynamicBranch uses dynamic
     13038  branching, but only on simple integers (-3 is the code for punt due to
     13039  complex objects). Serious bugs remain on the Cbc side, particularly in
     13040  chooseDynamicBranch.
     13041*/
    1240613042    if (!branchingMethod_||!branchingMethod_->chooseMethod()) {
    1240713043#ifdef COIN_HAS_CLP
     
    1243913075        anyAction = newNode->chooseBranch(this,oldNode,numberPassesLeft) ; // dynamic did nothing
    1244013076      }
     13077/*
     13078  We're on the new (Osi) side of the branching hierarchy.
     13079*/
    1244113080    } else {
    1244213081      OsiBranchingInformation usefulInfo=usefulInformation();
     
    1253313172    }
    1253413173  }
     13174/*
     13175  End main loop to choose a branching variable.
     13176*/
    1253513177  if (anyAction >= 0) {
    1253613178    if (resolved) {
     
    1253813180  Used to be that when the node was not fathomed (branching object present)
    1253913181  the solution was not needed. But that's no longer the case --- heuristics
    12540   are applied, and they may want the solution.
     13182  are applied, and they want the solution.
    1254113183*/
    1254213184      // bool needValidSolution = (newNode->branchingObject() == NULL) ;
    1254313185      bool needValidSolution = true ;
     13186#     if CBC_DEBUG > 0
     13187      std::cout
     13188        << "CbcModel::chooseBranch: branching object is " << std::hex
     13189        << newNode->branchingObject() << std::dec
     13190        << " and needValidSolution is " << needValidSolution
     13191        << "." << std::endl ;
     13192#     endif
    1254413193      takeOffCuts(cuts,needValidSolution ,NULL) ;
    1254513194#             ifdef CHECK_CUT_COUNTS
     
    1281113460  memcpy(bestSolution_,solution,numberColumns*sizeof(double));
    1281213461}
    12813 /* Do heuristics at root.
     13462
     13463/*
     13464  Do heuristics at root.
    1281413465   0 - don't delete
    1281513466   1 - delete
    12816       2 - just delete - don't even use
     13467   2 - just delete - don't even use
     13468
     13469  Parameter of 2 means what it says --- the routine will do nothing except
     13470  delete the existing heuristics. A feasibility pump is always deleted,
     13471  independent of the parameter value, as it's only useful at the root.
     13472
     13473  The routine is called from branchAndBound to process the root node. But it
     13474  will also be called when we've recursed into branchAndBound via smallBaB.
    1281713475*/
    1281813476void
     
    1282313481  double * newSolution = new double [numberColumns] ;
    1282413482  int i;
     13483
    1282513484  if (deleteHeuristicsAfterwards!=2) {
     13485/*
     13486  If mode == 1, we delete and recreate here, then delete at the bottom. The
     13487  create/delete part makes sense, but why delete the existing array? Seems like
     13488  it should be preserved and restored.
     13489*/
    1282613490    if (deleteHeuristicsAfterwards) {
    1282713491      delete [] usedInSolution_;
     
    1283413498    if (eventHandler)
    1283513499      eventHandler->setModel(this);
    12836    
     13500/*
     13501  currentPassNumber_ is described as `cut pass number'. Again, seems a bit
     13502  cavalier to just change it.
     13503
     13504  Whether this has any effect is determined by individual heuristics. Typically
     13505  there will be a check at the front of the solution() routine that determines
     13506  whether it will run or simply return. Root heuristics are characterised by
     13507  node count of 0. In addition, currentPassNumber_ can be checked to to limit
     13508  execution in terms of passes through cut generation / heuristic execution in
     13509  solveWithCuts.
     13510*/
    1283713511    currentPassNumber_ = 1; // so root heuristics will run
     13512/*
     13513  A loop to run the heuristics. incrementUsed will mark entries in
     13514  usedInSolution corresponding to variables that are nonzero in the solution.
     13515  CBC_ROUNDING just identifies a message template, not the heuristic.
     13516*/
    1283813517    // Modify based on size etc
    1283913518    adjustHeuristics();
     
    1294013619          // see if heuristic will do anything
    1294113620          double saveValue = heuristicValue ;
     13621#         if CBCMODEL_DEBUG > 1
     13622          // 090504 This print needs to be ported into the above threaded code.
     13623          std::cout
     13624            << "doHeuristic: heuristic " << heuristic_[i]->heuristicName()
     13625            << std::endl ;
     13626#         endif
    1294213627          int ifSol = heuristic_[i]->solution(heuristicValue,
    1294313628                                              newSolution);
     
    1298013665    }
    1298113666    currentPassNumber_ = 0;
    12982     /*
    12983       Did any of the heuristics turn up a new solution? Record it before we free
    12984       the vector.
    12985     */
     13667/*
     13668  Did any of the heuristics turn up a new solution? Record it before we free
     13669  the vector. tree_ will not necessarily be a CbcTreeLocal; the main model gets
     13670  a CbcTree by default. CbcTreeLocal actually implements a k-neighbourhood
     13671  search heuristic. This initialises it with a solution and creates the
     13672  k-neighbourhood cut.
     13673*/
    1298613674    if (found >= 0) {
    1298713675      CbcTreeLocal * tree
     
    1299613684    }
    1299713685  }
     13686/*
     13687  Cleanup. The feasibility pump heuristic is a root heuristic to look for an
     13688  initial feasible solution. It's had its chance; remove it.
     13689
     13690  For modes 1 and 2, all the heuristics are deleted.
     13691*/
    1299813692  if (!deleteHeuristicsAfterwards) {
    1299913693    for (i = 0;i<numberHeuristics_;i++) {
  • branches/reengAnn/Cbc/src/CbcNode.cpp

    r1240 r1265  
    99#include "CbcConfig.h"
    1010
     11// Debug trace  (-lh-)
     12#define CBCNODE_DEBUG 0
     13
     14
    1115#include <string>
    12 //#define CBC_DEBUG 1
     16// #define CBC_DEBUG 1
     17//#define CBC_CHECK_BASIS 1
    1318//#define CHECK_CUT_COUNTS
    1419//#define CHECK_NODE
    15 //#define CBC_CHECK_BASIS
    1620#include <cassert>
    1721#include <cfloat>
     
    941945}
    942946
    943 #define CBC_NEW_CREATEINFO
    944 #ifdef CBC_NEW_CREATEINFO
    945947
    946948/*
     
    948950  solvers to override and carry over all information from one basis to
    949951  another.
     952
     953  (Old version of createInfo is deleted from this file. It occasionally shows
     954  up as a conflict. Arguably, I should put it back to track changes.)
    950955*/
    951956
     
    10531058        expanded->setArtifStatus(iFull,CoinWarmStartBasis::basic);
    10541059    }
    1055     /*
    1056       Finally, call mergeBasis to copy over entries from the current basis to
    1057       the expanded basis. Since we cloned the expanded basis from the active basis
    1058       and haven't changed the number of variables, only row status entries need
    1059       to be copied.
    1060     */
     1060/*
     1061  Finally, call mergeBasis to copy over entries from the current basis to
     1062  the expanded basis. Since we cloned the expanded basis from the active basis
     1063  and havn't changed the number of variables, only row status entries need
     1064  to be copied.
     1065*/
    10611066    expanded->mergeBasis(ws,&xferRows,0) ;
    10621067   
     
    11571162}
    11581163
    1159 #else   // CBC_NEW_CREATEINFO
    1160 
    1161 /*
    1162   Original createInfo, with bare manipulation of basis vectors. Fails if solver
    1163   maintains additional information in basis.
    1164 */
    1165 
    1166 void
    1167 CbcNode::createInfo (CbcModel *model,
    1168                      CbcNode *lastNode,
    1169                      const CoinWarmStartBasis *lastws,
    1170                      const double *lastLower, const double *lastUpper,
    1171                      int numberOldActiveCuts,int numberNewCuts)
    1172 { OsiSolverInterface * solver = model->solver();
    1173   CbcStrategy * strategy = model->strategy();
    1174   /*
    1175     The root --- no parent. Create full basis and bounds information.
    1176   */
    1177   if (!lastNode)
    1178     {
    1179       if (!strategy)
    1180         nodeInfo_=new CbcFullNodeInfo(model,solver->getNumRows());
    1181       else
    1182         nodeInfo_ = strategy->fullNodeInfo(model,solver->getNumRows());
    1183     }
    1184   /*
    1185     Not the root. Create an edit from the parent's basis & bound information.
    1186     This is not quite as straightforward as it seems. We need to reintroduce
    1187     cuts we may have dropped out of the basis, in the correct position, because
    1188     this whole process is strictly positional. Start by grabbing the current
    1189     basis.
    1190   */
    1191   else
    1192     {
    1193       bool mustDeleteBasis;
    1194       const CoinWarmStartBasis* ws =
    1195         dynamic_cast<const CoinWarmStartBasis*>(solver->getPointerToWarmStart(mustDeleteBasis));
    1196       assert(ws!=NULL); // make sure not volume
    1197       //int numberArtificials = lastws->getNumArtificial();
    1198       int numberColumns = solver->getNumCols();
    1199      
    1200       const double * lower = solver->getColLower();
    1201       const double * upper = solver->getColUpper();
    1202      
    1203       int i;
    1204       /*
    1205         Create a clone and resize it to hold all the structural constraints, plus
    1206         all the cuts: old cuts, both active and inactive (currentNumberCuts), and
    1207         new cuts (numberNewCuts).
    1208        
    1209         TODO: You'd think that the set of constraints (logicals) in the expanded
    1210         basis should match the set represented in lastws. At least, that's
    1211         what I thought. But at the point I first looked hard at this bit of
    1212         code, it turned out that lastws was the stripped basis produced at
    1213         the end of addCuts(), rather than the raw basis handed back by
    1214         addCuts1(). The expanded basis here is equivalent to the raw basis of
    1215         addCuts1(). I said ``whoa, that's not good, I must have introduced a
    1216         bug'' and went back to John's code to see where I'd gone wrong.
    1217         And discovered the same `error' in his code.
    1218        
    1219         After a bit of thought, my conclusion is that correctness is not
    1220         affected by whether lastws is the stripped or raw basis. The diffs
    1221         have no semantics --- just a set of changes that need to be made
    1222         to convert lastws into expanded. I think the only effect is that we
    1223         store a lot more diffs (everything in expanded that's not covered by
    1224         the stripped basis). But I need to give this more thought. There
    1225         may well be some subtle error cases.
    1226        
    1227         In the mean time, I've twiddled addCuts() to set lastws to the raw
    1228         basis. Makes me (Lou) less nervous to compare apples to apples.
    1229       */
    1230       CoinWarmStartBasis *expanded =
    1231         dynamic_cast<CoinWarmStartBasis *>(ws->clone()) ;
    1232       int numberRowsAtContinuous = model->numberRowsAtContinuous();
    1233       int iFull = numberRowsAtContinuous+model->currentNumberCuts()+
    1234         numberNewCuts;
    1235       //int numberArtificialsNow = iFull;
    1236       //int maxBasisLength = ((iFull+15)>>4)+((numberColumns+15)>>4);
    1237       //printf("l %d full %d\n",maxBasisLength,iFull);
    1238       if (expanded)
    1239         expanded->resize(iFull,numberColumns);
    1240 #ifdef CBC_CHECK_BASIS
    1241       printf("Before expansion: orig %d, old %d, new %d, current %d\n",
    1242              numberRowsAtContinuous,numberOldActiveCuts,numberNewCuts,
    1243              model->currentNumberCuts()) ;
    1244       ws->print();
    1245 #endif
    1246       /*
    1247         Now fill in the expanded basis. Any indices beyond nPartial must
    1248         be cuts created while processing this node --- they can be copied directly
    1249         into the expanded basis. From nPartial down, pull the status of active cuts
    1250         from ws, interleaving with a B entry for the deactivated (loose) cuts.
    1251       */
    1252       int numberDropped = model->currentNumberCuts()-numberOldActiveCuts;
    1253       int iCompact=iFull-numberDropped;
    1254       CbcCountRowCut ** cut = model->addedCuts();
    1255       int nPartial = model->currentNumberCuts()+numberRowsAtContinuous;
    1256       iFull--;
    1257       for (;iFull>=nPartial;iFull--) {
    1258         CoinWarmStartBasis::Status status = ws->getArtifStatus(--iCompact);
    1259         //assert (status != CoinWarmStartBasis::basic); // may be permanent cut
    1260         expanded->setArtifStatus(iFull,status);
    1261       }
    1262       for (;iFull>=numberRowsAtContinuous;iFull--) {
    1263         if (cut[iFull-numberRowsAtContinuous]) {
    1264           CoinWarmStartBasis::Status status = ws->getArtifStatus(--iCompact);
    1265           // If no cut generator being used then we may have basic variables
    1266           //if (model->getMaximumCutPasses()&&
    1267           //  status == CoinWarmStartBasis::basic)
    1268           //printf("cut basic\n");
    1269           expanded->setArtifStatus(iFull,status);
    1270         } else {
    1271           expanded->setArtifStatus(iFull,CoinWarmStartBasis::basic);
    1272         }
    1273       }
    1274 #ifdef CBC_CHECK_BASIS
    1275       printf("Expanded basis\n");
    1276       expanded->print() ;
    1277       printf("Diffing against\n") ;
    1278       lastws->print() ;
    1279 #endif   
    1280       /*
    1281         Now that we have two bases in proper positional correspondence, creating
    1282         the actual diff is dead easy.
    1283       */
    1284      
    1285       CoinWarmStartDiff *basisDiff = expanded->generateDiff(lastws) ;
    1286       /*
    1287         Diff the bound vectors. It's assumed the number of structural variables is
    1288         not changing. Assuming that branching objects all involve integer variables,
    1289         we should see at least one bound change as a consequence of processing this
    1290         subproblem. Different types of branching objects could break this assertion.
    1291         Not true at all - we have not applied current branch - JJF.
    1292       */
    1293       double *boundChanges = new double [2*numberColumns] ;
    1294       int *variables = new int [2*numberColumns] ;
    1295       int numberChangedBounds=0;
    1296       for (i=0;i<numberColumns;i++) {
    1297         if (lower[i]!=lastLower[i]) {
    1298           variables[numberChangedBounds]=i;
    1299           boundChanges[numberChangedBounds++]=lower[i];
    1300         }
    1301         if (upper[i]!=lastUpper[i]) {
    1302           variables[numberChangedBounds]=i|0x80000000;
    1303           boundChanges[numberChangedBounds++]=upper[i];
    1304         }
    1305 #ifdef CBC_DEBUG
    1306         if (lower[i]!=lastLower[i])
    1307           printf("lower on %d changed from %g to %g\n",
    1308                  i,lastLower[i],lower[i]);
    1309         if (upper[i]!=lastUpper[i])
    1310           printf("upper on %d changed from %g to %g\n",
    1311                  i,lastUpper[i],upper[i]);
    1312 #endif
    1313       }
    1314 #ifdef CBC_DEBUG
    1315       printf("%d changed bounds\n",numberChangedBounds) ;
    1316 #endif
    1317       //if (lastNode->branchingObject()->boundBranch())
    1318       //assert (numberChangedBounds);
    1319       /*
    1320         Hand the lot over to the CbcPartialNodeInfo constructor, then clean up and
    1321         return.
    1322       */
    1323       if (!strategy)
    1324         nodeInfo_ =
    1325           new CbcPartialNodeInfo(lastNode->nodeInfo_,this,numberChangedBounds,
    1326                                  variables,boundChanges,basisDiff) ;
    1327       else
    1328         nodeInfo_ = strategy->partialNodeInfo(model, lastNode->nodeInfo_,this,numberChangedBounds,
    1329                                               variables,boundChanges,basisDiff) ;
    1330       delete basisDiff ;
    1331       delete [] boundChanges;
    1332       delete [] variables;
    1333       delete expanded ;
    1334       if  (mustDeleteBasis)
    1335         delete ws;
    1336     }
    1337   // Set node number
    1338   nodeInfo_->setNodeNumber(model->getNodeCount2());
    1339   state_ |= 2; // say active
    1340 }
    1341 
    1342 #endif  // CBC_NEW_CREATEINFO
    13431164/*
    13441165  The routine scans through the object list of the model looking for objects
     
    23702191        osiclp->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
    23712192      }
    2372 #     endif 
     2193#     endif
    23732194    }
    23742195    /*
     
    31843005    // Save basis
    31853006    CoinWarmStart * ws = NULL;
     3007#   if CBC_DEBUG > 0
     3008    std::cout << "chDyBr: declaring null warm start." << std::endl ;
     3009#   endif
    31863010    // save limit
    31873011    int saveLimit=0;
     
    31913015    if (!skipAll) {
    31923016      ws = solver->getWarmStart();
     3017#     if CBC_DEBUG > 0
     3018      std::cout
     3019        << "chDyBr: Acquired real warm start "
     3020        << std::hex << ws << std::dec << "." << std::endl ;
     3021#     endif
    31933022      int limit=100;
    31943023      if (!saveStateOfSearch&&saveLimit<limit&&saveLimit==100)
     
    32233052      }
    32243053      delete ws;
     3054#     if CBC_DEBUG > 0
     3055      std::cout
     3056        << "chDyBr(1): deleting warm start "
     3057        << std::hex << ws << std::dec << "." << std::endl ;
     3058#     endif
    32253059      ws=NULL;
    32263060      break;
     
    39363770              if (numberStrong<=1) {
    39373771                delete ws;
     3772#     if CBC_DEBUG > 0
     3773      std::cout
     3774        << "chDyBr(2): deleting warm start "
     3775        << std::hex << ws << std::dec << "." << std::endl ;
     3776#     endif
    39383777                ws=NULL;
    39393778                break;
     
    39463785              if (iDo>=2*numberStrong) {
    39473786                delete ws;
     3787#     if CBC_DEBUG > 0
     3788      std::cout
     3789        << "chDyBr(3): deleting warm start "
     3790        << std::hex << ws << std::dec << "." << std::endl ;
     3791#     endif
    39483792                ws=NULL;
    39493793                break;
     
    39603804                if (iDo-whichChoice>=2*numberStrong) {
    39613805                  delete ws;
     3806#     if CBC_DEBUG > 0
     3807      std::cout
     3808        << "chDyBr(4): deleting warm start "
     3809        << std::hex << ws << std::dec << "." << std::endl ;
     3810#     endif
    39623811                  ws=NULL;
    39633812                  if (!choiceObject) {
     
    40573906            }
    40583907            delete ws;
     3908#     if CBC_DEBUG > 0
     3909      std::cout
     3910        << "chDyBr(9): deleting warm start "
     3911        << std::hex << ws << std::dec << "." << std::endl ;
     3912#     endif
    40593913            ws=NULL;
    40603914            break;
     
    41053959        solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
    41063960        // restore basis
     3961#     if CBC_DEBUG > 0
     3962      std::cout
     3963        << "chDyBr: trying to use warm start "
     3964        << std::hex << ws << std::dec << "." << std::endl ;
     3965#     endif
    41073966        solver->setWarmStart(ws);
    41083967      }
     
    41504009        finished=false;
    41514010      }
     4011#     if CBC_DEBUG > 0
     4012      std::cout
     4013        << "chDyBr(10): deleting warm start "
     4014        << std::hex << ws << std::dec << "." << std::endl ;
     4015#     endif
    41524016      delete ws;
    41534017    }
    41544018  }
     4019# if CBC_DEBUG > 0
     4020  std::cout << "Finished dynamic branching main loop." << std::endl ;
     4021# endif
     4022
     4023#ifdef CBC_NODE7
     4024  delete [] weightModifier;
     4025#endif
     4026
     4027# ifdef RANGING
     4028  if (model->messageHandler()->logLevel()>2)
     4029    printf("%d strong, %d iters, %d pen, %d mark, %d fixed, action %d nnott %d nt %d, %d dq %s ns %d\n",
     4030         numberStrongDone,numberStrongIterations,xPen,xMark,
     4031           numberToFix,anyAction,numberNotTrusted,px[0],px[1],px[2]>0 ? "y" : "n",px[3]);
     4032# endif
    41554033  // update number of strong iterations etc
    41564034  model->incrementStrongInfo(numberStrongDone,numberStrongIterations,
     
    43254203  bool fastIterations = false ;
    43264204# endif
    4327   /*
    4328     Scan for branching objects that indicate infeasibility. Choose candidates
    4329     using priority as the first criteria, then integer infeasibility.
    4330    
    4331     The algorithm is to fill the array with a set of good candidates (by
    4332     infeasibility) with priority bestPriority.  Finding a candidate with
    4333     priority better (less) than bestPriority flushes the choice array. (This
    4334     serves as initialization when the first candidate is found.)
    4335    
    4336   */
     4205/*
     4206  Scan the objects. We're only interested in simple integers.
     4207*/
    43374208  numberToDo=0;
    43384209  for (i=0;i<numberObjects;i++) {
     
    43684239  double objMax = -1.0e50;
    43694240  bool needResolve=false;
     4241/*
     4242  Now calculate the cost forcing the variable up and down.
     4243*/
    43704244  int iDo;
    43714245  for (iDo=0;iDo<numberToDo;iDo++) {
     
    43794253    int iColumn = dynamicObject->columnNumber();
    43804254    int preferredWay;
     4255/*
     4256  Update the information held in the object.
     4257*/
    43814258    object->infeasibility(&usefulInfo,preferredWay);
    43824259    double value = currentSolution[iColumn];
     
    47024579  return *this;
    47034580}
     4581
     4582
    47044583CbcNode::~CbcNode ()
    47054584{
     
    47254604      delete nodeInfo_;
    47264605    } else {
    4727       //printf("node %x nodeinfo %x parent %x\n",this,nodeInfo_,nodeInfo_->parent());
     4606      //printf("node %x nodeinfo %x parent %x\n",this,nodeInfo_,parent);
    47284607      // anyway decrement parent
    47294608      //if (parent)
     
    48204699   the up arm. But see OsiBranchingObject::way()
    48214700   Use nodeInfo--.numberBranchesLeft_ to see how active
     4701
     4702   Except that there is no OsiBranchingObject::way(), and this'll fail in any
     4703   event because we have various OsiXXXBranchingObjects which aren't descended
     4704   from CbcBranchingObjects. I think branchIndex() is the appropriate
     4705   equivalent, but could be wrong. (lh, 061220)
     4706
     4707   071212: I'm finally getting back to cbc-generic and rescuing a lot of my
     4708   annotation from branches/devel (which was killed in summer). I'm going to
     4709   put back an assert(obj) just to see what happens. It's still present as of
     4710   the most recent change to CbcNode (r833).
     4711
     4712   080104: Yep, we can arrive here with an OsiBranchingObject. Removed the
     4713   assert, it's served its purpose.
     4714
     4715   080226: John finally noticed this problem and added a way() method to the
     4716   OsiBranchingObject hierarchy. Removing my workaround.
     4717
    48224718*/
    48234719int
     
    48714767                          int branchState)
    48724768{
     4769# if CBCNODE_DEBUG > 0
     4770  std::cout
     4771    << "CbcNode::chOsiBr: entering, node " << nodeNumber_
     4772    << ", parent " << ((lastNode==0)?-1:lastNode->nodeNumber_)
     4773    << ", branchState " << branchState << "." << std::endl ;
     4774# endif
    48734775  int returnStatus=0;
    48744776  if (lastNode)
     
    49204822      // carry on with strong branching or whatever
    49214823      int returnCode = choose->chooseVariable(solver, usefulInfo,true);
     4824#     if CBCNODE_DEBUG > 0
     4825      std::cout
     4826        << "CbcNode::chooseOsiBranch: chooseVariable returns "
     4827        << returnCode << "." << std::endl ;
     4828#     endif
    49224829      // update number of strong iterations etc
    49234830      model->incrementStrongInfo(choose->numberStrongDone(),choose->numberStrongIterations(),
     
    49694876    choose->clearGoodSolution();
    49704877  }
     4878# if CBCNODE_DEBUG > 0
     4879  std::cout
     4880    << "CbcNode::chOsiBr: returning " << returnStatus << "." << std::endl ;
     4881# endif
     4882
    49714883  return returnStatus;
    49724884}
  • branches/reengAnn/Cbc/src/CbcSolver.cpp

    r1263 r1265  
    22// Copyright (C) 2007, International Business Machines
    33// Corporation and others.  All Rights Reserved.
    4    
     4
     5/*! \file CbcSolver.cpp
     6    \brief Second level routines for the cbc stand-alone solver.
     7*/
     8
     9// Debug trace  (-lh-)
     10#define CBCSLV_DEBUG 0
     11
    512#include "CbcConfig.h"
    613#include "CoinPragma.hpp"
     
    535542    delete clpSolver;
    536543}
     544
     545/*
     546  Initialise a subset of the parameters prior to processing any input from
     547  the user.
     548
     549  Why this choice of subset?
     550*/
     551/*!
     552  \todo Guard/replace clp-specific code
     553*/
    537554void CbcSolver::fillValuesInSolver()
    538555{
     556  int j,intVal ;
     557  double dblVal ;
     558
    539559  OsiSolverInterface * solver = model_.solver();
    540   OsiClpSolverInterface * clpSolver = dynamic_cast< OsiClpSolverInterface*> (solver);
     560
     561  OsiClpSolverInterface * clpSolver =
     562        dynamic_cast< OsiClpSolverInterface*> (solver);
    541563  assert (clpSolver);
    542   noPrinting_ = (clpSolver->getModelPtr()->logLevel()==0);
     564  ClpSimplex * lpSolver = clpSolver->getModelPtr();
     565
     566/*
     567  Why are we reaching into the underlying solver(s) for these settings?
     568  Shouldn't CbcSolver have its own defaults, which are then imposed on the
     569  underlying solver?
     570
     571  Coming at if from the other side, if CbcSolver had the capability to use
     572  multiple solvers then it definitely makes sense to acquire the defaults from
     573  the solver (on the assumption that we haven't processed command line
     574  parameters yet, which can then override the defaults). But then it's more of
     575  a challenge to avoid solver-specific coding here.
     576*/
     577  noPrinting_ = (lpSolver->logLevel()==0);
    543578  CoinMessageHandler * generalMessageHandler = clpSolver->messageHandler();
    544579  generalMessageHandler->setPrefix(true);
    545   ClpSimplex * lpSolver = clpSolver->getModelPtr();
     580
    546581  lpSolver->setPerturbation(50);
    547582  lpSolver->messageHandler()->setPrefix(false);
    548   parameters_[whichParam(DUALBOUND,numberParameters_,parameters_)].setDoubleValue(lpSolver->dualBound());
    549   parameters_[whichParam(DUALTOLERANCE,numberParameters_,parameters_)].setDoubleValue(lpSolver->dualTolerance());
    550   int iParam = whichParam(SOLVERLOGLEVEL,numberParameters_,parameters_);
    551   int value=parameters_[iParam].intValue();
    552   clpSolver->messageHandler()->setLogLevel(value) ;
    553   lpSolver->setLogLevel(value);
    554   iParam = whichParam(LOGLEVEL,numberParameters_,parameters_);
    555   value=parameters_[iParam].intValue();
    556   model_.messageHandler()->setLogLevel(value);
    557   parameters_[whichParam(LOGLEVEL,numberParameters_,parameters_)].setIntValue(model_.logLevel());
    558   parameters_[whichParam(SOLVERLOGLEVEL,numberParameters_,parameters_)].setIntValue(lpSolver->logLevel());
    559   parameters_[whichParam(MAXFACTOR,numberParameters_,parameters_)].setIntValue(lpSolver->factorizationFrequency());
    560   parameters_[whichParam(MAXITERATION,numberParameters_,parameters_)].setIntValue(lpSolver->maximumIterations());
    561   parameters_[whichParam(PERTVALUE,numberParameters_,parameters_)].setIntValue(lpSolver->perturbation());
    562   parameters_[whichParam(PRIMALTOLERANCE,numberParameters_,parameters_)].setDoubleValue(lpSolver->primalTolerance());
    563   parameters_[whichParam(PRIMALWEIGHT,numberParameters_,parameters_)].setDoubleValue(lpSolver->infeasibilityCost());
    564   parameters_[whichParam(NUMBERBEFORE,numberParameters_,parameters_)].setIntValue(model_.numberBeforeTrust());
    565   parameters_[whichParam(MAXNODES,numberParameters_,parameters_)].setIntValue(model_.getMaximumNodes());
    566   parameters_[whichParam(STRONGBRANCHING,numberParameters_,parameters_)].setIntValue(model_.numberStrong());
    567   parameters_[whichParam(INFEASIBILITYWEIGHT,numberParameters_,parameters_)].setDoubleValue(model_.getDblParam(CbcModel::CbcInfeasibilityWeight));
    568   parameters_[whichParam(INTEGERTOLERANCE,numberParameters_,parameters_)].setDoubleValue(model_.getDblParam(CbcModel::CbcIntegerTolerance));
    569   parameters_[whichParam(INCREMENT,numberParameters_,parameters_)].setDoubleValue(model_.getDblParam(CbcModel::CbcCutoffIncrement));
     583
     584  j = whichParam(DUALBOUND,numberParameters_,parameters_) ;
     585  parameters_[j].setDoubleValue(lpSolver->dualBound());
     586  j = whichParam(DUALTOLERANCE,numberParameters_,parameters_) ;
     587  parameters_[j].setDoubleValue(lpSolver->dualTolerance());
     588/*
     589  Why are we doing this? We read the log level from parameters_, set it into
     590  the message handlers for cbc and the underlying solver. Then we read the
     591  log level back from the handlers and use it to set the values in
     592  parameters_!
     593*/
     594  j = whichParam(SOLVERLOGLEVEL,numberParameters_,parameters_);
     595  intVal = parameters_[j].intValue();
     596  clpSolver->messageHandler()->setLogLevel(intVal) ;
     597  lpSolver->setLogLevel(intVal);       
     598  j = whichParam(LOGLEVEL,numberParameters_,parameters_);
     599  intVal=parameters_[j].intValue();
     600  model_.messageHandler()->setLogLevel(intVal);
     601
     602  j = whichParam(LOGLEVEL,numberParameters_,parameters_) ;
     603  parameters_[j].setIntValue(model_.logLevel());
     604  j = whichParam(SOLVERLOGLEVEL,numberParameters_,parameters_) ;
     605  parameters_[j].setIntValue(lpSolver->logLevel());
     606
     607  j = whichParam(MAXFACTOR,numberParameters_,parameters_) ;
     608  parameters_[j].setIntValue(lpSolver->factorizationFrequency());
     609  j = whichParam(MAXITERATION,numberParameters_,parameters_) ;
     610  parameters_[j].setIntValue(lpSolver->maximumIterations());
     611  j = whichParam(PERTVALUE,numberParameters_,parameters_) ;
     612  parameters_[j].setIntValue(lpSolver->perturbation());
     613  j = whichParam(PRIMALTOLERANCE,numberParameters_,parameters_) ;
     614  parameters_[j].setDoubleValue(lpSolver->primalTolerance());
     615  j = whichParam(PRIMALWEIGHT,numberParameters_,parameters_) ;
     616  parameters_[j].setDoubleValue(lpSolver->infeasibilityCost());
     617  j = whichParam(NUMBERBEFORE,numberParameters_,parameters_) ;
     618  parameters_[j].setIntValue(model_.numberBeforeTrust());
     619  j = whichParam(MAXNODES,numberParameters_,parameters_) ;
     620  parameters_[j].setIntValue(model_.getMaximumNodes());
     621  j = whichParam(STRONGBRANCHING,numberParameters_,parameters_) ;
     622  parameters_[j].setIntValue(model_.numberStrong());
     623  j = whichParam(INFEASIBILITYWEIGHT,numberParameters_,parameters_) ;
     624  dblVal = model_.getDblParam(CbcModel::CbcInfeasibilityWeight);
     625  parameters_[j].setDoubleValue(dblVal) ;
     626  j = whichParam(INTEGERTOLERANCE,numberParameters_,parameters_) ;
     627  dblVal = model_.getDblParam(CbcModel::CbcIntegerTolerance);
     628  parameters_[j].setDoubleValue(dblVal) ;
     629  j = whichParam(INCREMENT,numberParameters_,parameters_) ;
     630  dblVal = model_.getDblParam(CbcModel::CbcCutoffIncrement);
     631  parameters_[j].setDoubleValue(dblVal) ;
     632
    570633}
     634
     635
    571636// Add user function
    572637void
     
    57485813            // obsolete case STRENGTHEN:
    57495814            if (goodModel) {
     5815
     5816#             if CBCSLV_DEBUG > 0
     5817              std::cout
     5818                << "CbcSolver:BAB: entering." << std::endl ;
     5819#             endif
     5820
    57505821              bool miplib = type==MIPLIB;
    57515822              int logLevel = parameters_[slog].intValue();
     
    60006071                  model_.solver()->setHintParam(OsiDoPresolveInResolve,false,OsiHintTry);
    60016072                }
     6073
    60026074                double time1a = CoinCpuTime();
     6075
     6076#               if CBCSLV_DEBUG > 0
     6077                std::cout
     6078                  << "CbcSolver:BAB: initial solve complete." << std::endl ;
     6079#               endif
     6080
    60036081                OsiSolverInterface * solver = model_.solver();
     6082
    60046083#ifndef CBC_OTHER_SOLVER
    60056084                OsiClpSolverInterface * si =
     
    62306309              }
    62316310              // See if we want preprocessing
     6311
     6312#             if CBCSLV_DEBUG > 0
     6313              std::cout
     6314                << "CbcSolver:BAB: at preprocessing prep." << std::endl ;
     6315#             endif
     6316
    62326317              OsiSolverInterface * saveSolver=NULL;
    62336318              CglPreProcess process;
     
    65776662                babModel_->setMaximumSeconds(timeLeft-(CoinCpuTime()-time1));
    65786663              }
     6664
     6665#             if CBCSLV_DEBUG > 0
     6666              std::cout
     6667                << "CbcSolver:BAB: finished preprocessing." << std::endl ;
     6668#             endif
     6669
    65796670              // now tighten bounds
    65806671              if (!miplib) {
     
    67176808                delete [] dsort;
    67186809              }
     6810
     6811#             if CBCSLV_DEBUG > 0
     6812              std::cout
     6813                << "CbcSolver:BAB: preparing for heuristics." << std::endl ;
     6814#             endif
     6815
    67196816              // Set up heuristics
    67206817              doHeuristics(babModel_,(!miplib) ? 1 : 10);
     6818
    67216819              if (!miplib) {
    67226820                if(parameters_[whichParam(LOCALTREE,numberParameters_,parameters_)].currentOptionAsInteger()) {
     
    81508248                  babModel_->addHeuristic(&partial);
    81518249                }
     8250
     8251#               if CBCSLV_DEBUG > 0
     8252                std::cout
     8253                  << "CbcSolver:BAB: call branchAndBound." << std::endl ;
     8254#               endif
     8255
    81528256                if (logLevel<=1)
    81538257                  babModel_->solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
     
    82498353                  return returnCode;
    82508354                }
     8355
    82518356#ifdef CLP_MALLOC_STATISTICS
    82528357                malloc_stats();
  • branches/reengAnn/Cbc/src/CbcSolver.hpp

    r1212 r1265  
    22// Copyright (C) 2007, International Business Machines
    33// Corporation and others.  All Rights Reserved.
     4
     5/*! \file CbcSolver.hpp
     6    \brief Defines CbcSolver, the top-level class for the new-style cbc solver.
     7*/
     8 
    49#ifndef CbcSolver_H
    510#define CbcSolver_H
     
    2126//#############################################################################
    2227
    23 /** This allows the use of the standalone solver in a flexible manner
    24     It has an original OsiClpSolverInterface and CbcModel which
    25     it can use repeatedly e.g. get a heuristic solution and then start again
    26 
    27     So I will need a primitive scripting language which can then call solve
    28     and manipulate solution value and solution arrays.
     28/*! \brief This allows the use of the standalone solver in a flexible manner.
     29
     30    It has an original OsiClpSolverInterface and CbcModel which it can use
     31    repeatedly, e.g., to get a heuristic solution and then start again.
     32
     33    So I [jjf] will need a primitive scripting language which can then call
     34    solve and manipulate solution value and solution arrays.
     35
     36    Also provides for user callback functions. Currently two ideas in
     37    gestation, CbcUser and CbcStopNow. The latter seems limited to deciding
     38    whether or not to stop. The former seems completely general, with a notion
     39    of importing and exporting, and a `solve', which should be interpreted as
     40    `do whatever this user function does'.
    2941   
     42    Parameter initialisation is at last centralised in fillParameters().
    3043*/
    3144
    32 class CbcSolver  {
     45class CbcSolver
     46{
    3347 
    3448public:
     
    7286  /// Fill with standard parameters
    7387  void fillParameters();
    74   /// Set default values in solvers from parameters
     88  /*! \brief Set default values in solvers from parameters
     89
     90    Misleading. The current code actually reads default values from
     91    the underlying solvers and installs them as default values for a subset of
     92    parameters in #parameters_.
     93  */
    7594  void fillValuesInSolver();
    7695  /// Add user function
     
    196215};
    197216//#############################################################################
     217
    198218/// Structure to hold useful arrays
    199 typedef struct {
     219typedef struct
     220{
    200221  // Priorities
    201222  int * priorities_;
     
    211232  double * pseudoUp_;
    212233} CbcSolverUsefulData;
    213 /** This allows the use of an unknown user stuff including modeling languages
    214  */
    215 
    216 class CbcUser  {
     234
     235
     236/*! \brief A class to allow the use of unknown user functionality
     237
     238    For example, access to a modelling language (CbcAmpl).
     239*/
     240class CbcUser
     241{
    217242 
    218243public:
    219244  ///@name import/export methods
    220245  //@{
    221   /** Import - gets full command arguments
    222       Returns -1 - no action
    223                0 - data read in without error
    224                1 - errors
    225   */
    226   virtual int importData(CbcSolver * /*model*/, int & /*argc*/, char ** /*argv[]*/) {return -1;}
    227   /// Export 1 OsiClpSolver, 2 CbcModel - add 10 if infeasible from odd situation
    228   virtual void exportSolution(CbcSolver * /*model*/,
    229                               int /*mode*/,const char * /*message*/=NULL) {}
     246  /*! \brief Import - gets full command arguments
     247
     248    \return
     249    - -1 - no action
     250    -  0 - data read in without error
     251    -  1 - errors
     252  */
     253  virtual int importData(CbcSolver *model, int &argc, char **argv) {return -1;}
     254
     255  /*! \brief Export
     256 
     257    \param mode
     258    - 1 OsiClpSolver
     259    - 2 CbcModel
     260    - add 10 if infeasible from odd situation
     261  */
     262  virtual void exportSolution(CbcSolver *model,
     263                              int mode, const char *message = NULL) {}
     264
    230265  /// Export Data (i.e. at very end)
    231   virtual void exportData(CbcSolver * /*model*/) {}
     266  virtual void exportData(CbcSolver *model) {}
     267
    232268  /// Get useful stuff
    233   virtual void fillInformation(CbcSolver * /*model*/,
    234                                CbcSolverUsefulData & /*info*/) {}
    235 
    236   //@}
     269  virtual void fillInformation(CbcSolver *model,
     270                               CbcSolverUsefulData &info) {}
     271  //@}
     272
    237273  ///@name usage methods
    238274  //@{
    239275  /// CoinModel if valid
    240   inline CoinModel * coinModel() const
     276  inline CoinModel *coinModel() const
    241277  { return coinModel_;}
    242278  /// Other info - needs expanding
     
    250286  virtual bool canDo(const char * options) = 0;
    251287  //@}
     288
    252289  ///@name Constructors and destructors etc
    253290  //@{
     
    255292  CbcUser();
    256293 
    257   /** Copy constructor .
    258    */ 
     294  /// Copy constructor
    259295  CbcUser(const CbcUser & rhs);
    260296 
     
    283319//#############################################################################
    284320
    285 /** This allows the use of a call back class to decide whether to stop
    286  */
    287 
    288 class CbcStopNow  {
     321/*! \brief Support the use of a call back class to decide whether to stop
     322
     323  Definitely under construction.
     324*/
     325
     326class CbcStopNow
     327{
    289328 
    290329public:
    291330  ///@name Decision methods
    292331  //@{
    293   /// Import - 0 if good
    294   /** Meaning of whereFrom:
    295      1 after initial solve by dualsimplex etc
    296      2 after preprocessing
    297      3 just before branchAndBound (so user can override)
    298      4 just after branchAndBound (before postprocessing)
    299      5 after postprocessing
    300      6 after a user called heuristic phase
     332  /*! \brief Import
     333
     334    \param whereFrom
     335     - 1 after initial solve by dualsimplex etc
     336     - 2 after preprocessing
     337     - 3 just before branchAndBound (so user can override)
     338     - 4 just after branchAndBound (before postprocessing)
     339     - 5 after postprocessing
     340     - 6 after a user called heuristic phase
     341 
     342    \return 0 if good
    301343     nonzero return code to stop
    302344  */
    303   virtual int callBack(CbcModel * /*currentSolver*/,
    304                        int /*whereFrom*/) {return 0;}
    305   //@}
     345  virtual int callBack(CbcModel *currentSolver, int whereFrom) {return 0;}
     346  //@}
     347
    306348  ///@name Constructors and destructors etc
    307349  //@{
  • branches/reengAnn/Cbc/src/CbcStrategy.cpp

    r1263 r1265  
    331331  }
    332332}
     333
     334/*
     335 Aside from setting CbcModel::numberStrong_ and numberBeforeTrust, the big
     336 activity is integer preprocessing. Surely this code to do preprocessing
     337 duplicates code to do preprocessing up in the solver main routine. Most of the
     338 effort goes into manipulating SOS sets.
     339*/
    333340// Other stuff e.g. strong branching
    334341void
     
    338345  if (desiredPreProcess_) {
    339346    delete process_;
     347/*
     348  Inaccurate as of 080122 --- assignSolver (below) can now be instructed not to
     349  delete the existing solver when the preprocessed solver is assigned to the
     350  model. 'Course, we do need to hold on to a pointer somewhere, and that must
     351  be captured before this call.
     352*/
    340353    // solver_ should have been cloned outside
    341354    CglPreProcess * process = new CglPreProcess();
     
    413426      memset(prohibited,0,numberColumns);
    414427      int numberProhibited=0;
     428/*
     429  Create CbcSimpleInteger objects would be more accurate in the general
     430  case.  The `false' parameter says we won't delete existing objects.
     431
     432  Only Clp will produce SOS objects in findIntegers (080122), and that's
     433  where a possible conversion can occur. If clp is holding OsiSOS objects,
     434  they'll be converted to CbcSOS objects.
     435*/
    415436      // convert to Cbc integers
    416437      model.findIntegers(false);
     
    465486    generator1.setRowCuts(3);
    466487    //generator1.messageHandler()->setLogLevel(logLevel);
    467     // Not needed with pass in process->messageHandler()->setLogLevel(logLevel);
     488    // Not needed with pass k1in process->messageHandler()->setLogLevel(logLevel);
    468489    // Add in generators
    469490    process->addCutGenerator(&generator1);
  • branches/reengAnn/Cbc/src/CbcTreeLocal.cpp

    r1240 r1265  
    744744      int iColumn = integerVariable[i];
    745745      double value = floor(solution[iColumn]+0.5);
     746/*
     747  typeCuts_ == 0 restricts to binary, 1 allows general integer. But we're
     748  still restricted to being up against a bound. Consider: the notion is that
     749  the cut restricts us to a k-neighbourhood. For binary variables, this
     750  amounts to k variables which change value. For general integer, we could
     751  end up with a single variable sucking up all of k (hence mu --- the
     752  variable must swing to its other bound to look like a movement of 1).  For
     753  variables in the middle of a range, we're talking about fabs(sol<j> - x<j>).
     754*/
    746755      if (!typeCuts_&&originalUpper_[i]-originalLower_[i]>1.0)
    747756        continue; // skip as not 0-1
  • branches/reengAnn/Cbc/src/Cbc_ampl.cpp

    r1200 r1265  
    2424THIS SOFTWARE.
    2525****************************************************************/
     26
     27/*! \file Cbc_ampl.cpp
     28
     29  Interface routines for AMPL.
     30*/
     31
    2632#ifdef COIN_HAS_ASL
    2733
     
    344350  }
    345351}
     352
    346353int
    347354readAmpl(ampl_info * info, int argc, char **argv, void ** coinModel)
  • branches/reengAnn/Cbc/src/ClpAmplStuff.cpp

    r1200 r1265  
    22// Corporation and others.  All Rights Reserved.
    33/* $Id$ */
     4
     5/*! \file ClpAmplStuff.cpp
     6    \brief Hooks to Ampl (for the new-style solver?)
     7*/
    48
    59#include "ClpConfig.h"
     
    2428#include "CoinModel.hpp"
    2529#include "CbcLinked.hpp"
     30
     31/*! \brief Extension of CbcUser for Ampl.
     32
     33  Beyond that, can't say yet what this does. A CbcAmpl object can be installed
     34  in a CbcSolver object using CbcSolver::addUserFunction.
     35*/
     36 
    2637class CbcAmpl  : public CbcUser {
    2738 
     
    2940  ///@name usage methods
    3041  //@{
     42
    3143  /// Solve (whatever that means)
    3244  virtual void solve(CbcSolver * model, const char * options);
    33   /// Returns true if function knows about option
    34   virtual bool canDo(const char * options) ;
    35   /** Import - gets full command arguments
    36       Returns -1 - no action
    37                0 - data read in without error
    38                1 - errors
     45
     46  /*! \brief Returns true if function knows about option
     47
     48    Currently knows about
     49      - cbc_load
     50      - cbc_quit
     51  */
     52  virtual bool canDo(const char * option) ;
     53
     54  /*! \brief Import - gets full command arguments
     55
     56    \return
     57    - -1 - no action
     58    -  0 - data read in without error
     59    -  1 - errors
    3960  */
    4061  virtual int importData(CbcSolver * model, int & argc, char ** & argv);
    41   /// Export 1 OsiClpSolver, 2 CbcModel - add 10 if infeasible from odd situation
     62
     63  /*! \brief Export
     64 
     65    \param mode
     66    - 1 OsiClpSolver
     67    - 2 CbcModel
     68    - add 10 if infeasible from odd situation
     69  */
    4270  virtual void exportSolution(CbcSolver * model, int mode,const char * message=NULL) ;
    4371  /// Export Data (i.e. at very end)
     
    120148// Returns true if function knows about option
    121149bool
    122 CbcAmpl::canDo(const char * options)
    123 {
    124   return (!strcmp(options,"cbc_load")||!strcmp(options,"cbc_quit"));
     150CbcAmpl::canDo(const char * option)
     151{
     152  return (!strcmp(option,"cbc_load")||!strcmp(option,"cbc_quit"));
    125153}
    126154/* Import - gets full command arguments
     
    135163  assert (babModel);
    136164  CoinMessageHandler * generalMessageHandler = babModel->messageHandler();
    137   OsiClpSolverInterface * solver = dynamic_cast< OsiClpSolverInterface*> (control->model()->solver());
     165  OsiClpSolverInterface * solver =
     166      dynamic_cast< OsiClpSolverInterface*> (control->model()->solver());
    138167  assert (solver);
    139168  CoinMessages generalMessages = solver->getModelPtr()->messages();
    140169  char generalPrint[10000];
    141170  OsiSolverLink * si = NULL;
     171/*
     172  Poke through the arguments looking for a log level. If we find it, write it
     173  into the info block we'll use to load from AMPL, and set a magic number to
     174  indicate the log level is valid.
     175
     176  This looks brittle, in several different directions.
     177*/
    142178  ClpSimplex * lpSolver = solver->getModelPtr();
    143179  if (argc>2&&!strcmp(argv[2],"-AMPL")) {
  • branches/reengAnn/Cbc/src/CoinSolve.cpp

    r1224 r1265  
    22// Copyright (C) 2007, International Business Machines
    33// Corporation and others.  All Rights Reserved.
     4
     5/*! \file CbcSolver.cpp
     6    \brief Main routine for the cbc stand-alone solver.
     7*/
    48   
    59#include "CbcConfig.h"
     
    812#include "CbcOrClpParam.hpp"
    913#include "OsiClpSolverInterface.hpp"
     14
     15/*
     16  We have the following compile-time symbols.
     17
     18  NEW_STYLE_SOLVER      CoinSolve.cpp, CbcSolver.cpp
     19
     20    Unclear what this does just yet. A value of 0 seems to be `old style
     21    solver'.
     22
     23
     24  CBC_OTHER_SOLVER      CoinSolve.cpp, CbcSolver.[cpp,hpp], CbcModel.cpp
     25
     26    Usage in CbcSolver.hpp says `other solver' is Cplex (only).
     27
     28    Here in CoinSolver, CBC_OTHER_SOLVER dominates NEW_STYLE_SOLVER.
     29
     30    Usage in CbcModel is a fake; a small bit of code that's now `#if 0'.
     31                       
     32
     33  CPX_KEEP_RESULTS      CoinSolve.cpp, CbcSolver.cpp
     34
     35    Unclear what this does just yet. The name seems clear, but how / what is
     36    affected is not. Defining this symbol forces CBC_OTHER_SOLVER.
     37
     38
     39  CLP_DEBUG_MALLOC
     40
     41    This ties in with the functions clp_malloc, clp_free, and clp_memory,
     42    which are defined in CoinOslFactorization.cpp. (Right where you'd expect
     43    to find them, eh?).  Looks to be a relatively nice debugging wrapper for
     44    standard C malloc.  Calls standard C malloc/free directly if
     45    CLP_DEBUG_MALLOC is not defined.  Worth consideration for breaking out as
     46    a separate utility.  The hooks for new and delete defined here should be
     47    incorporated.
     48
     49    Absolutely not thread safe --- lots of static variables.
     50
     51    Hmmm ... is it still the case that standard C malloc and C++ new/delete
     52    do not play well together? 'Cause the hooks here for new and delete will
     53    not escape from this file.
     54
     55*/
     56
     57
     58/*
     59  Allow (force?) use of cplex for something.
     60*/
     61
    1062#ifdef CPX_KEEP_RESULTS
    1163#define CBC_OTHER_SOLVER 1
     
    1466#include "OsiCpxSolverInterface.hpp"
    1567#endif
     68
     69/*
     70  Hooks for a debugging wrapper for malloc/free. This bit of definition hooks
     71  C++ new / delete and diverts them into the debugging wrapper.
     72*/
    1673//#define CLP_DEBUG_MALLOC
    1774#ifdef CLP_DEBUG_MALLOC
     
    3188  clp_free(p);
    3289}
    33 #endif
     90#endif          // CLP_DEBUG_MALLOC
    3491
    3592#include <cassert>
     
    3996#include <cstring>
    4097#include <iostream>
     98
     99/*
     100  The subtleties are unclear, but the gross action is that CBC_OTHER_SOLVER
     101  will overrule NEW_STYLE_SOLVER. NEW_STYLE_SOLVER undefined or 0 seems to
     102  mean `old style solver'.
     103*/
    41104#ifndef NEW_STYLE_SOLVER
    42 #define NEW_STYLE_SOLVER 0
     105# define NEW_STYLE_SOLVER 0
    43106#endif
    44107#ifdef CBC_OTHER_SOLVER
    45 #undef NEW_STYLE_SOLVER
    46 #define NEW_STYLE_SOLVER 0
    47 #endif
    48 #if NEW_STYLE_SOLVER==0
    49   // define TEST_MESSAGE_HANDLER to check works on all messages
    50 //#define TEST_MESSAGE_HANDLER
     108# undef NEW_STYLE_SOLVER
     109# define NEW_STYLE_SOLVER 0
     110#endif
     111
     112
     113
     114#if NEW_STYLE_SOLVER == 0
     115// define TEST_MESSAGE_HANDLER to check works on all messages
     116// #define TEST_MESSAGE_HANDLER
    51117#ifdef TEST_MESSAGE_HANDLER
    52118// This driver shows how to trap messages - this is just as in unitTest.cpp
     
    59125
    60126    The file pointer is just there as an example of user stuff.
     127
     128  -- lh 071026 -- An accurate summary. Nothing is actually happening here
     129  except that messages will be prefixed with "==", which serves the purpose
     130  of demonstrating that this message handler is active. The extra parameters
     131  (CbcModel, FILE) are unused.
    61132
    62133*/
     
    191262  model_ = model;
    192263}
    193 #endif
     264#endif /* TEST_MESSAGE_HANDLER */
     265
    194266//#############################################################################
     267
    195268// To use USERCBC or USERCLP change 0 to 1 in defines and add in your fake main program(s) and any other code
    196269//#define USER_HAS_FAKE_CBC
    197 //#define USER_HAS_FAKE_CLP
     270//#define USER_HAS_FAKE_CLP
     271
    198272#ifdef USER_HAS_FAKE_CBC
    199273#endif
     
    210284#endif
    211285}
     286
    212287// Clp stuff
    213288#ifdef USER_HAS_FAKE_CLP
     
    225300}
    226301//  End any fake main program
     302
    227303//#############################################################################
     304
    228305// void CbcClpUnitTest (const CbcModel & saveModel);
     306
    229307#ifdef CBC_STATISTICS
    230308int osi_crunch=0;
     
    244322}
    245323#endif
     324
    246325int main (int argc, const char *argv[])
    247326{
     
    256335    OsiCpxSolverInterface solver1;
    257336#endif
    258     CbcModel model(solver1);
    259     // define TEST_MESSAGE_HANDLER at top of file to check works on all messages
     337  CbcModel model(solver1);
     338
     339  // define TEST_MESSAGE_HANDLER at top of file to check works on all messages
    260340#ifdef TEST_MESSAGE_HANDLER
    261341    MyMessageHandler2 messageHandler(&model);
     
    267347    //clpSolver->getModelPtr()->passInMessageHandler(&messageHandler);
    268348#endif
    269     // initialize
    270     CbcMain0(model);
     349
     350  // initialize
     351  CbcMain0(model);
     352
    271353#ifdef TEST_MESSAGE_HANDLER
    272354    // Set log levels same so can use one message handler
     
    277359    setCbcOrClpPrinting(false);
    278360#endif
     361
    279362    returnCode = CbcMain1 (argc, argv,model);
    280363  }
     364
    281365#ifdef CLP_DEBUG_MALLOC
    282366  clp_memory(1);
    283367#endif
     368
    284369#ifdef CBC_STATISTICS
    285370#endif
     371
    286372  if (returnCode!=777) {
    287373    return returnCode;
     
    290376  }
    291377}
    292 #else
     378
     379
     380
     381#else   /* NEW_STYLE_SOLVER */
     382
     383/*
     384  As best I can see, this is not yet fully functional. NEW_STYLE_SOLVER is
     385  normally undefined or forced to 0. See CbcSolver.hpp for jjf's thoughts on
     386  where this is going (a good direction, in my opinion [lh]).
     387*/
     388
    293389#include "CbcSolver.hpp"
     390
     391/*
     392  ClpAmplStuff.cpp
     393*/
    294394void addAmplToCbc(CbcSolver *);
     395
    295396int main (int argc, const char *argv[])
    296397{
    297398  int returnCode;
     399
     400/*
    298401  // Only active if malloc switched on in CbcSolver.cpp
    299 #ifdef CLP_DEBUG_MALLOC
     402
     403  Magic value 0 initialises the package. Anything else dumps statistics.
     404*/
     405# ifdef CLP_DEBUG_MALLOC
    300406  clp_memory(0);
    301 #endif
     407# endif
     408
     409  // Open a block to ease memory leak checks.
    302410  {
    303411    OsiClpSolverInterface solver1;
     
    305413    // initialize
    306414    control.fillValuesInSolver();
    307 #ifdef COIN_HAS_ASL
     415
     416#   ifdef COIN_HAS_ASL
    308417    addAmplToCbc(&control);
    309 #endif
     418#   endif
     419
    310420    returnCode= control.solve (argc, argv, 1);
    311421  }
     
    315425  return returnCode;
    316426}
    317 #endif
     427
     428#endif  /* NEW_STYLE_SOLVER */
     429
     430
     431
    318432/*
    319433  Version 1.00.00 November 16 2005.
  • branches/reengAnn/Cbc/src/unitTestClp.cpp

    r1263 r1265  
    22// Copyright (C) 2002, International Business Machines
    33// Corporation and others.  All Rights Reserved.
     4
     5// Debug trace  (-lh-)
     6#define CBCCLPUT_DEBUG 0
     7
    48
    59#include <cstdio>
     
    256260                << " (" << numberAttempts << " out of "
    257261                << numberPossibleAttempts << ")\n";
    258       /*
    259         Stage 1: Read the MPS
    260         and make sure the size of the constraint matrix is correct.
    261       */
     262/*
     263  Stage 1: Read the MPS and make sure the size of the constraint matrix is
     264          correct.
     265*/
    262266      CbcModel * model = new CbcModel(saveModel);
    263      
     267
     268#     if CBCCLPUT_DEBUG > 0
     269      std::cout
     270        << "CbcClpUnitTest: model is " << std::hex << model ;
     271      if (model)
     272      { std::cout << ", tree is " << model->tree() ; }
     273      std::cout << std::dec << "." << std::endl ;
     274#     endif
     275
    264276      std::string fn = dirMiplib+mpsName[m] ;
     277
     278#     if CBCCLPUT_DEBUG > 0
     279      std::cout << "CbcClpUnitTest: processing " << fn << "." << std::endl ;
     280#     endif
     281
    265282      if (!CbcTestMpsFile(fn)) {
    266283        std::cout << "ERROR: Cannot find MPS file " << fn << "\n";
    267284        continue;
    268285      }
     286
    269287      CoinDrand48(true,1234567);
    270288      //printf("RAND1 %g %g\n",CoinDrand48(true,1234567),model->randomNumberGenerator()->randomDouble());
    271289      //printf("RAND1 %g\n",CoinDrand48(true,1234567));
     290
    272291      model->solver()->readMps(fn.c_str(),"") ;
    273292      assert(model->getNumRows() == nRows[m]) ;
    274293      assert(model->getNumCols() == nCols[m]) ;
    275      
    276       /*
    277         Stage 2: Call solver to solve the problem.
    278         then check the return code and objective.
    279       */
    280      
     294
     295/*
     296  Stage 2: Call solver to solve the problem.  then check the return code and
     297          objective.
     298*/
     299
    281300#ifdef CLP_FACTORIZATION_INSTRUMENT
    282301      extern double factorization_instrument(int type);
     
    676695      delete model;
    677696    }
    678   }
     697  }     // end main loop on MPS problem
     698
    679699  int returnCode=0;
    680700  std::cout
Note: See TracChangeset for help on using the changeset viewer.