Changeset 886 for branches


Ignore:
Timestamp:
Mar 3, 2008 11:15:00 PM (11 years ago)
Author:
ladanyi
Message:

Added a new way of determinig when to run a heuristic

Location:
branches/heur/Cbc/src
Files:
9 edited

Legend:

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

    r854 r886  
    1010//#define CBC_DEBUG
    1111
     12#include "CoinTypes.hpp"
    1213#include "OsiSolverInterface.hpp"
    1314#include "OsiSolverBranch.hpp"
     
    1718#include "CoinSort.hpp"
    1819#include "CoinError.hpp"
     20
     21//##############################################################################
     22
     23/** Compare two ranges. The two bounds arrays are both of size two and
     24    describe closed intervals. Return the appropriate CbcRangeCompare value
     25    (first argument being the sub/superset if that's the case). In case of
     26    overlap (and if \c replaceIfOverlap is true) replace the content of thisBd
     27    with the intersection of the ranges.
     28*/
     29static inline CbcRangeCompare
     30CbcCompareRanges(double* thisBd, const double* otherBd,
     31                 const bool replaceIfOverlap)
     32{
     33  const double lbDiff = thisBd[0] - otherBd[0];
     34  if (lbDiff < 0) { // lb of this < lb of other
     35    if (thisBd[1] >= otherBd[1]) { // ub of this >= ub of other
     36      return CbcRangeSuperset;
     37    } else if (thisBd[1] < otherBd[0]) {
     38      return CbcRangeDisjoint;
     39    } else {
     40      // overlap
     41      if (replaceIfOverlap) {
     42        thisBd[0] = otherBd[0];
     43      }
     44      return CbcRangeOverlap;
     45    }
     46  } else if (lbDiff > 0) { // lb of this > lb of other
     47    if (thisBd[1] <= otherBd[1]) { // ub of this <= ub of other
     48      return CbcRangeSubset;
     49    } else if (thisBd[0] > otherBd[1]) {
     50      return CbcRangeDisjoint;
     51    } else {
     52      // overlap
     53      if (replaceIfOverlap) {
     54        thisBd[1] = otherBd[1];
     55      }
     56      return CbcRangeOverlap;
     57    }
     58  } else { // lb of this == lb of other
     59    if (thisBd[1] == otherBd[1]) {
     60      return CbcRangeSame;
     61    }
     62    return thisBd[1] < otherBd[1] ? CbcRangeSubset : CbcRangeSuperset;
     63  }
     64
     65  return CbcRangeSame; // fake return
     66
     67}
     68
     69//##############################################################################
    1970
    2071// Default Constructor
     
    331382  return branch;
    332383}
     384
     385//##############################################################################
    333386
    334387// Default Constructor
     
    708761}
    709762
     763//##############################################################################
     764
    710765/** Default Constructor
    711766
     
    938993  return NULL;
    939994}
     995
     996//##############################################################################
     997
    940998// Default Constructor
    941999CbcIntegerBranchingObject::CbcIntegerBranchingObject()
     
    13311389}
    13321390
     1391/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     1392    same type and must have the same original object, but they may have
     1393    different feasible regions.
     1394    Return the appropriate CbcRangeCompare value (first argument being the
     1395    sub/superset if that's the case). In case of overlap (and if \c
     1396    replaceIfOverlap is true) replace the current branching object with one
     1397    whose feasible region is the overlap.
     1398   */
     1399CbcRangeCompare
     1400CbcIntegerBranchingObject::compareBranchingObject
     1401(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     1402{
     1403  const CbcIntegerBranchingObject* br =
     1404    dynamic_cast<const CbcIntegerBranchingObject*>(brObj);
     1405  assert(br);
     1406  double* thisBd = way_ < 0 ? down_ : up_;
     1407  const double* otherBd = br->way_ < 0 ? br->down_ : br->up_;
     1408  return CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
     1409}
     1410
     1411//##############################################################################
    13331412
    13341413/** Default Constructor
     
    15681647}
    15691648
     1649//##############################################################################
     1650
    15701651// Default Constructor
    15711652CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject()
     
    16391720}
    16401721
     1722/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     1723    same type and must have the same original object, but they may have
     1724    different feasible regions.
     1725    Return the appropriate CbcRangeCompare value (first argument being the
     1726    sub/superset if that's the case). In case of overlap (and if \c
     1727    replaceIfOverlap is true) replace the current branching object with one
     1728    whose feasible region is the overlap.
     1729*/
     1730CbcRangeCompare
     1731CbcIntegerPseudoCostBranchingObject::compareBranchingObject
     1732(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     1733{
     1734  const CbcIntegerPseudoCostBranchingObject* br =
     1735    dynamic_cast<const CbcIntegerPseudoCostBranchingObject*>(brObj);
     1736  assert(br);
     1737  double* thisBd = way_ < 0 ? down_ : up_;
     1738  const double* otherBd = br->way_ < 0 ? br->down_ : br->up_;
     1739  return CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
     1740}
     1741
     1742
     1743//##############################################################################
    16411744
    16421745// Default Constructor
     
    18131916  printf("\n");
    18141917}
    1815  
     1918
     1919static inline int
     1920CbcCompareCliques(const CbcClique* cl0, const CbcClique* cl1)
     1921{
     1922  if (cl0->cliqueType() < cl1->cliqueType()) {
     1923    return -1;
     1924  }
     1925  if (cl0->cliqueType() > cl1->cliqueType()) {
     1926    return 1;
     1927  }
     1928  if (cl0->numberMembers() != cl1->numberMembers()) {
     1929    return cl0->numberMembers() - cl1->numberMembers();
     1930  }
     1931  if (cl0->numberNonSOSMembers() != cl1->numberNonSOSMembers()) {
     1932    return cl0->numberNonSOSMembers() - cl1->numberNonSOSMembers();
     1933  }
     1934  return memcmp(cl0->members(), cl1->members(),
     1935                cl0->numberMembers() * sizeof(int));
     1936}
     1937
     1938/** Compare the original object of \c this with the original object of \c
     1939    brObj. Assumes that there is an ordering of the original objects.
     1940    This method should be invoked only if \c this and brObj are of the same
     1941    type.
     1942    Return negative/0/positive depending on whether \c this is
     1943    smaller/same/larger than the argument.
     1944*/
     1945int
     1946CbcCliqueBranchingObject::compareOriginalObject
     1947(const CbcBranchingObject* brObj) const
     1948{
     1949  const CbcCliqueBranchingObject* br =
     1950    dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
     1951  assert(br);
     1952  return CbcCompareCliques(clique_, br->clique_);
     1953}
     1954
     1955/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     1956    same type and must have the same original object, but they may have
     1957    different feasible regions.
     1958    Return the appropriate CbcRangeCompare value (first argument being the
     1959    sub/superset if that's the case). In case of overlap (and if \c
     1960    replaceIfOverlap is true) replace the current branching object with one
     1961    whose feasible region is the overlap.
     1962*/
     1963CbcRangeCompare
     1964CbcCliqueBranchingObject::compareBranchingObject
     1965(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     1966{
     1967  const CbcCliqueBranchingObject* br =
     1968    dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
     1969  assert(br);
     1970  unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
     1971  const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
     1972  const CoinUInt64 cl0 =
     1973    (static_cast<CoinUInt64>(thisMask[0]) << 32) | thisMask[1];
     1974  const CoinUInt64 cl1 =
     1975    (static_cast<CoinUInt64>(otherMask[0]) << 32) | otherMask[1];
     1976  if (cl0 == cl1) {
     1977    return CbcRangeSame;
     1978  }
     1979  const CoinUInt64 cl_intersection = (cl0 & cl1);
     1980  if (cl_intersection == cl0) {
     1981    return CbcRangeSuperset;
     1982  }
     1983  if (cl_intersection == cl1) {
     1984    return CbcRangeSubset;
     1985  }
     1986  const CoinUInt64 cl_xor = (cl0 ^ cl1);
     1987  if (cl_intersection == 0 && cl_xor == 0) {
     1988    return CbcRangeDisjoint;
     1989  }
     1990  const CoinUInt64 cl_union = (cl0 | cl1);
     1991  thisMask[0] = static_cast<unsigned int>(cl_union >> 32);
     1992  thisMask[1] = static_cast<unsigned int>(cl_union & 0xffffffff);
     1993  return CbcRangeOverlap;
     1994}
     1995
     1996//##############################################################################
     1997
    18161998// Default Constructor
    18171999CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject()
     
    20042186  printf("\n");
    20052187}
     2188
     2189/** Compare the original object of \c this with the original object of \c
     2190    brObj. Assumes that there is an ordering of the original objects.
     2191    This method should be invoked only if \c this and brObj are of the same
     2192    type.
     2193    Return negative/0/positive depending on whether \c this is
     2194    smaller/same/larger than the argument.
     2195*/
     2196int
     2197CbcLongCliqueBranchingObject::compareOriginalObject
     2198(const CbcBranchingObject* brObj) const
     2199{
     2200  const CbcLongCliqueBranchingObject* br =
     2201    dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
     2202  assert(br);
     2203  return CbcCompareCliques(clique_, br->clique_);
     2204}
     2205
     2206/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     2207    same type and must have the same original object, but they may have
     2208    different feasible regions.
     2209    Return the appropriate CbcRangeCompare value (first argument being the
     2210    sub/superset if that's the case). In case of overlap (and if \c
     2211    replaceIfOverlap is true) replace the current branching object with one
     2212    whose feasible region is the overlap.
     2213*/
     2214CbcRangeCompare
     2215CbcLongCliqueBranchingObject::compareBranchingObject
     2216(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     2217{
     2218  const CbcLongCliqueBranchingObject* br =
     2219    dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
     2220  assert(br);
     2221  const int numberMembers = clique_->numberMembers();
     2222  const int numberWords=(numberMembers+31)>>5;
     2223  unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
     2224  const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
     2225
     2226  if (memcmp(thisMask, otherMask, numberWords * sizeof(unsigned int)) == 0) {
     2227    return CbcRangeSame;
     2228  }
     2229  bool canBeSuperset = true;
     2230  bool canBeSubset = true;
     2231  int i;
     2232  for (i = numberWords-1; i >= 0 && (canBeSuperset || canBeSubset); --i) {
     2233    const unsigned int both = (thisMask[i] & otherMask[i]);
     2234    canBeSuperset &= (both == thisMask[i]);
     2235    canBeSubset &= (both == otherMask[i]);
     2236  }
     2237  if (canBeSuperset) {
     2238    return CbcRangeSuperset;
     2239  }
     2240  if (canBeSubset) {
     2241    return CbcRangeSubset;
     2242  }
     2243
     2244  for (i = numberWords-1; i >= 0; --i) {
     2245    if ((thisMask[i] ^ otherMask[i]) != 0) {
     2246      break;
     2247    }
     2248  }
     2249  if (i == -1) { // complement
     2250    return CbcRangeDisjoint;
     2251  }
     2252  // must be overlap
     2253  for (i = numberWords-1; i >= 0; --i) {
     2254    thisMask[i] |= otherMask[i];
     2255  }
     2256  return CbcRangeOverlap;
     2257}
     2258
     2259//##############################################################################
     2260
    20062261// Default Constructor
    20072262CbcSOSBranchingObject::CbcSOSBranchingObject()
    2008   :CbcBranchingObject()
     2263  :CbcBranchingObject(),
     2264   firstNonzero_(-1),
     2265   lastNonzero_(-1)
    20092266{
    20102267  set_ = NULL;
     
    20212278  set_ = set;
    20222279  separator_ = separator;
     2280  computeNonzeroRange();
    20232281}
    20242282
    20252283// Copy constructor
    2026 CbcSOSBranchingObject::CbcSOSBranchingObject ( const CbcSOSBranchingObject & rhs) :CbcBranchingObject(rhs)
     2284CbcSOSBranchingObject::CbcSOSBranchingObject (const CbcSOSBranchingObject & rhs)
     2285 :CbcBranchingObject(rhs),
     2286  firstNonzero_(rhs.firstNonzero_),
     2287  lastNonzero_(rhs.lastNonzero_)
    20272288{
    20282289  set_=rhs.set_;
     
    20382299    set_=rhs.set_;
    20392300    separator_ = rhs.separator_;
     2301    firstNonzero_ = rhs.firstNonzero_;
     2302    lastNonzero_ = rhs.lastNonzero_;
    20402303  }
    20412304  return *this;
     
    20522315{
    20532316}
     2317
     2318void
     2319CbcSOSBranchingObject::computeNonzeroRange()
     2320{
     2321  const int numberMembers = set_->numberMembers();
     2322  const double * weights = set_->weights();
     2323  int i = 0;
     2324  if (way_ < 0) {
     2325    for ( i=0;i<numberMembers;i++) {
     2326      if (weights[i] > separator_)
     2327        break;
     2328    }
     2329    assert (i<numberMembers);
     2330    firstNonzero_ = 0;
     2331    lastNonzero_ = i;
     2332  } else {
     2333    for ( i=0;i<numberMembers;i++) {
     2334      if (weights[i] >= separator_)
     2335        break;
     2336    }
     2337    assert (i<numberMembers);
     2338    firstNonzero_ = i;
     2339    lastNonzero_ = numberMembers;
     2340  }
     2341}
     2342
    20542343double
    20552344CbcSOSBranchingObject::branch()
     
    20842373    way_=-1;      // Swap direction
    20852374  }
     2375  computeNonzeroRange();
    20862376  return 0.0;
    20872377}
     
    21442434}
    21452435 
     2436/** Compare the original object of \c this with the original object of \c
     2437    brObj. Assumes that there is an ordering of the original objects.
     2438    This method should be invoked only if \c this and brObj are of the same
     2439    type.
     2440    Return negative/0/positive depending on whether \c this is
     2441    smaller/same/larger than the argument.
     2442*/
     2443int
     2444CbcSOSBranchingObject::compareOriginalObject
     2445(const CbcBranchingObject* brObj) const
     2446{
     2447  const CbcSOSBranchingObject* br =
     2448    dynamic_cast<const CbcSOSBranchingObject*>(brObj);
     2449  assert(br);
     2450  const CbcSOS* s0 = set_;
     2451  const CbcSOS* s1 = br->set_;
     2452  if (s0->sosType() != s1->sosType()) {
     2453    return s0->sosType() - s1->sosType();
     2454  }
     2455  if (s0->numberMembers() != s1->numberMembers()) {
     2456    return s0->numberMembers() - s1->numberMembers();
     2457  }
     2458  const int memberCmp = memcmp(s0->members(), s1->members(),
     2459                               s0->numberMembers() * sizeof(int));
     2460  if (memberCmp != 0) {
     2461    return memberCmp;
     2462  }
     2463  return memcmp(s0->weights(), s1->weights(),
     2464                s0->numberMembers() * sizeof(double));
     2465}
     2466
     2467/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     2468    same type and must have the same original object, but they may have
     2469    different feasible regions.
     2470    Return the appropriate CbcRangeCompare value (first argument being the
     2471    sub/superset if that's the case). In case of overlap (and if \c
     2472    replaceIfOverlap is true) replace the current branching object with one
     2473    whose feasible region is the overlap.
     2474*/
     2475CbcRangeCompare
     2476CbcSOSBranchingObject::compareBranchingObject
     2477(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     2478{
     2479  const CbcSOSBranchingObject* br =
     2480    dynamic_cast<const CbcSOSBranchingObject*>(brObj);
     2481  assert(br);
     2482  if (firstNonzero_ < br->firstNonzero_) {
     2483    if (lastNonzero_ >= br->lastNonzero_) {
     2484      return CbcRangeSuperset;
     2485    } else if (lastNonzero_ <= br->firstNonzero_) {
     2486      return CbcRangeDisjoint;
     2487    } else {
     2488      // overlap
     2489      if (replaceIfOverlap) {
     2490        firstNonzero_ = br->firstNonzero_;
     2491      }
     2492      return CbcRangeOverlap;
     2493    }
     2494  } else if (firstNonzero_ > br->firstNonzero_) {
     2495    if (lastNonzero_ <= br->lastNonzero_) {
     2496      return CbcRangeSubset;
     2497    } else if (firstNonzero_ >= br->lastNonzero_) {
     2498      return CbcRangeDisjoint;
     2499    } else {
     2500      // overlap
     2501      if (replaceIfOverlap) {
     2502        lastNonzero_ = br->lastNonzero_;
     2503      }
     2504      return CbcRangeOverlap;
     2505    }
     2506  } else {
     2507    if (lastNonzero_ == br->lastNonzero_) {
     2508      return CbcRangeSame;
     2509    }
     2510    return lastNonzero_ < br->lastNonzero_ ? CbcRangeSubset : CbcRangeSuperset;
     2511  }
     2512  return CbcRangeSame; // fake return
     2513}
     2514
     2515//##############################################################################
     2516
    21462517// Default Constructor
    21472518CbcBranchDefaultDecision::CbcBranchDefaultDecision()
     
    25542925}
    25552926
     2927//##############################################################################
     2928
    25562929// Default Constructor
    25572930CbcFollowOn::CbcFollowOn ()
     
    28923265  return branch;
    28933266}
     3267
     3268//##############################################################################
     3269
    28943270// Default Constructor
    28953271CbcFixingBranchingObject::CbcFixingBranchingObject()
     
    30123388  printf("\n");
    30133389}
     3390
     3391/** Compare the original object of \c this with the original object of \c
     3392    brObj. Assumes that there is an ordering of the original objects.
     3393    This method should be invoked only if \c this and brObj are of the same
     3394    type.
     3395    Return negative/0/positive depending on whether \c this is
     3396    smaller/same/larger than the argument.
     3397*/
     3398int
     3399CbcFixingBranchingObject::compareOriginalObject
     3400(const CbcBranchingObject* brObj) const
     3401{
     3402  throw("must implement");
     3403}
     3404
     3405/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     3406    same type and must have the same original object, but they may have
     3407    different feasible regions.
     3408    Return the appropriate CbcRangeCompare value (first argument being the
     3409    sub/superset if that's the case). In case of overlap (and if \c
     3410    replaceIfOverlap is true) replace the current branching object with one
     3411    whose feasible region is the overlap.
     3412   */
     3413CbcRangeCompare
     3414CbcFixingBranchingObject::compareBranchingObject
     3415(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     3416{
     3417  const CbcFixingBranchingObject* br =
     3418    dynamic_cast<const CbcFixingBranchingObject*>(brObj);
     3419  assert(br);
     3420  // If two FixingBranchingObject's have the same base object then it's pretty
     3421  // much guaranteed
     3422  throw("must implement");
     3423}
     3424
     3425//##############################################################################
     3426
    30143427// Default Constructor
    30153428CbcNWay::CbcNWay ()
     
    32613674}
    32623675 
     3676//##############################################################################
     3677
    32633678// Default Constructor
    32643679CbcNWayBranchingObject::CbcNWayBranchingObject()
     
    33823797  printf("\n");
    33833798}
     3799
     3800/** Compare the original object of \c this with the original object of \c
     3801    brObj. Assumes that there is an ordering of the original objects.
     3802    This method should be invoked only if \c this and brObj are of the same
     3803    type.
     3804    Return negative/0/positive depending on whether \c this is
     3805    smaller/same/larger than the argument.
     3806*/
     3807int
     3808CbcNWayBranchingObject::compareOriginalObject
     3809(const CbcBranchingObject* brObj) const
     3810{
     3811  throw("must implement");
     3812}
     3813
     3814/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     3815    same type and must have the same original object, but they may have
     3816    different feasible regions.
     3817    Return the appropriate CbcRangeCompare value (first argument being the
     3818    sub/superset if that's the case). In case of overlap (and if \c
     3819    replaceIfOverlap is true) replace the current branching object with one
     3820    whose feasible region is the overlap.
     3821*/
     3822CbcRangeCompare
     3823CbcNWayBranchingObject::compareBranchingObject
     3824(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     3825{
     3826  throw("must implement");
     3827}
     3828
     3829//##############################################################################
    33843830
    33853831// Default Constructor
     
    35493995}
    35503996
     3997//##############################################################################
     3998
    35513999// Default Constructor
    35524000CbcDummyBranchingObject::CbcDummyBranchingObject(CbcModel * model)
     
    35984046  printf("Dummy branch\n");
    35994047}
     4048
     4049/** Compare the original object of \c this with the original object of \c
     4050    brObj. Assumes that there is an ordering of the original objects.
     4051    This method should be invoked only if \c this and brObj are of the same
     4052    type.
     4053    Return negative/0/positive depending on whether \c this is
     4054    smaller/same/larger than the argument.
     4055*/
     4056int
     4057CbcDummyBranchingObject::compareOriginalObject
     4058(const CbcBranchingObject* brObj) const
     4059{
     4060  throw("must implement");
     4061}
     4062
     4063/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     4064    same type and must have the same original object, but they may have
     4065    different feasible regions.
     4066    Return the appropriate CbcRangeCompare value (first argument being the
     4067    sub/superset if that's the case). In case of overlap (and if \c
     4068    replaceIfOverlap is true) replace the current branching object with one
     4069    whose feasible region is the overlap.
     4070*/
     4071CbcRangeCompare
     4072CbcDummyBranchingObject::compareBranchingObject
     4073(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     4074{
     4075  throw("must implement");
     4076}
     4077
  • branches/heur/Cbc/src/CbcBranchActual.hpp

    r848 r886  
    487487#endif
    488488
     489  /** Return the type (an integer identifier) of \c this */
     490  virtual int type() const { return 100; }
     491
     492  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     493      same type and must have the same original object, but they may have
     494      different feasible regions.
     495      Return the appropriate CbcRangeCompare value (first argument being the
     496      sub/superset if that's the case). In case of overlap (and if \c
     497      replaceIfOverlap is true) replace the current branching object with one
     498      whose feasible region is the overlap.
     499   */
     500  virtual CbcRangeCompare compareBranchingObject
     501  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     502
    489503protected:
    490504  /// Lower [0] and upper [1] bounds for the down arm (way_ = -1)
     
    661675  inline void setChangeInGuessed(double value)
    662676  { changeInGuessed_=value;}
     677
     678  /** Return the type (an integer identifier) of \c this */
     679  virtual int type() const { return 101; }
     680
     681  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     682      same type and must have the same original object, but they may have
     683      different feasible regions.
     684      Return the appropriate CbcRangeCompare value (first argument being the
     685      sub/superset if that's the case). In case of overlap (and if \c
     686      replaceIfOverlap is true) replace the current branching object with one
     687      whose feasible region is the overlap.
     688   */
     689  virtual CbcRangeCompare compareBranchingObject
     690  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     691
    663692protected:
    664693  /// Change in guessed objective value for next branch
     
    708737  */
    709738  virtual void print();
     739
     740  /** Return the type (an integer identifier) of \c this */
     741  virtual int type() const { return 102; }
     742
     743  /** Compare the original object of \c this with the original object of \c
     744      brObj. Assumes that there is an ordering of the original objects.
     745      This method should be invoked only if \c this and brObj are of the same
     746      type.
     747      Return negative/0/positive depending on whether \c this is
     748      smaller/same/larger than the argument.
     749  */
     750  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     751
     752  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     753      same type and must have the same original object, but they may have
     754      different feasible regions.
     755      Return the appropriate CbcRangeCompare value (first argument being the
     756      sub/superset if that's the case). In case of overlap (and if \c
     757      replaceIfOverlap is true) replace the current branching object with one
     758      whose feasible region is the overlap.
     759   */
     760  virtual CbcRangeCompare compareBranchingObject
     761  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     762
    710763private:
    711764  /// data
     
    755808  */
    756809  virtual void print();
     810
     811  /** Return the type (an integer identifier) of \c this */
     812  virtual int type() const { return 103; }
     813
     814  /** Compare the original object of \c this with the original object of \c
     815      brObj. Assumes that there is an ordering of the original objects.
     816      This method should be invoked only if \c this and brObj are of the same
     817      type.
     818      Return negative/0/positive depending on whether \c this is
     819      smaller/same/larger than the argument.
     820  */
     821  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     822
     823  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     824      same type and must have the same original object, but they may have
     825      different feasible regions.
     826      Return the appropriate CbcRangeCompare value (first argument being the
     827      sub/superset if that's the case). In case of overlap (and if \c
     828      replaceIfOverlap is true) replace the current branching object with one
     829      whose feasible region is the overlap.
     830   */
     831  virtual CbcRangeCompare compareBranchingObject
     832  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     833
    757834private:
    758835  /// data
     
    801878  */
    802879  virtual void print();
     880
     881  /** Return the type (an integer identifier) of \c this */
     882  virtual int type() const { return 104; }
     883
     884  /** Compare the original object of \c this with the original object of \c
     885      brObj. Assumes that there is an ordering of the original objects.
     886      This method should be invoked only if \c this and brObj are of the same
     887      type.
     888      Return negative/0/positive depending on whether \c this is
     889      smaller/same/larger than the argument.
     890  */
     891  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     892
     893  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     894      same type and must have the same original object, but they may have
     895      different feasible regions.
     896      Return the appropriate CbcRangeCompare value (first argument being the
     897      sub/superset if that's the case). In case of overlap (and if \c
     898      replaceIfOverlap is true) replace the current branching object with one
     899      whose feasible region is the overlap.
     900   */
     901  virtual CbcRangeCompare compareBranchingObject
     902  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     903
     904  /** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */
     905  void computeNonzeroRange();
     906
    803907private:
    804908  /// data
     
    806910  /// separator
    807911  double separator_;
     912  /** The following two members describe the range in the members_ of the
     913      original object that whose upper bound is not fixed to 0. This is not
     914      necessary for Cbc to function correctly, this is there for heuristics so
     915      that separate branching decisions on the same object can be pooled into
     916      one branching object. */
     917  int firstNonzero_;
     918  int lastNonzero_;
    808919};
    809920
     
    852963  virtual bool twoWay() const
    853964  { return false;}
     965
     966  /** Return the type (an integer identifier) of \c this */
     967  virtual int type() const { return 105; }
     968
     969  /** Compare the original object of \c this with the original object of \c
     970      brObj. Assumes that there is an ordering of the original objects.
     971      This method should be invoked only if \c this and brObj are of the same
     972      type.
     973      Return negative/0/positive depending on whether \c this is
     974      smaller/same/larger than the argument.
     975  */
     976  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     977
     978  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     979      same type and must have the same original object, but they may have
     980      different feasible regions.
     981      Return the appropriate CbcRangeCompare value (first argument being the
     982      sub/superset if that's the case). In case of overlap (and if \c
     983      replaceIfOverlap is true) replace the current branching object with one
     984      whose feasible region is the overlap.
     985   */
     986  virtual CbcRangeCompare compareBranchingObject
     987  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     988
    854989private:
    855990  /// order of branching - points back to CbcNWay
     
    10411176  */
    10421177  virtual void print();
     1178
     1179  /** Return the type (an integer identifier) of \c this */
     1180  virtual int type() const { return 106; }
     1181
     1182  /** Compare the original object of \c this with the original object of \c
     1183      brObj. Assumes that there is an ordering of the original objects.
     1184      This method should be invoked only if \c this and brObj are of the same
     1185      type.
     1186      Return negative/0/positive depending on whether \c this is
     1187      smaller/same/larger than the argument.
     1188  */
     1189  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     1190
     1191  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     1192      same type and must have the same original object, but they may have
     1193      different feasible regions.
     1194      Return the appropriate CbcRangeCompare value (first argument being the
     1195      sub/superset if that's the case). In case of overlap (and if \c
     1196      replaceIfOverlap is true) replace the current branching object with one
     1197      whose feasible region is the overlap.
     1198   */
     1199  virtual CbcRangeCompare compareBranchingObject
     1200  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     1201
    10431202private:
    10441203  /// data
     
    11401299  virtual void print();
    11411300
     1301  /** Return the type (an integer identifier) of \c this */
     1302  virtual int type() const { return 107; }
     1303
     1304  /** Compare the original object of \c this with the original object of \c
     1305      brObj. Assumes that there is an ordering of the original objects.
     1306      This method should be invoked only if \c this and brObj are of the same
     1307      type.
     1308      Return negative/0/positive depending on whether \c this is
     1309      smaller/same/larger than the argument.
     1310  */
     1311  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
     1312
     1313  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     1314      same type and must have the same original object, but they may have
     1315      different feasible regions.
     1316      Return the appropriate CbcRangeCompare value (first argument being the
     1317      sub/superset if that's the case). In case of overlap (and if \c
     1318      replaceIfOverlap is true) replace the current branching object with one
     1319      whose feasible region is the overlap.
     1320   */
     1321  virtual CbcRangeCompare compareBranchingObject
     1322  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     1323
    11421324};
    11431325
  • branches/heur/Cbc/src/CbcBranchBase.hpp

    r833 r886  
    1616class OsiChooseVariable;
    1717class CbcObjectUpdateData;
     18
     19//#############################################################################
     20
     21enum CbcRangeCompare {
     22  CbcRangeSame,
     23  CbcRangeDisjoint,
     24  CbcRangeSubset,
     25  CbcRangeSuperset,
     26  CbcRangeOverlap
     27};
    1828
    1929//#############################################################################
     
    349359  {originalCbcObject_=object;}
    350360
     361  // Methods used in heuristics
     362 
     363  /** Return the type (an integer identifier) of \c this */
     364  virtual int type() const = 0;
     365
     366  /** Compare the original object of \c this with the original object of \c
     367      brObj. Assumes that there is an ordering of the original objects.
     368      This method should be invoked only if \c this and brObj are of the same
     369      type.
     370      Return negative/0/positive depending on whether \c this is
     371      smaller/same/larger than the argument.
     372  */
     373  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const
     374  {
     375    const CbcBranchingObject* br=dynamic_cast<const CbcBranchingObject*>(brObj);
     376    return variable() - br->variable();
     377  }
     378
     379  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     380      same type and must have the same original object, but they may have
     381      different feasible regions.
     382      Return the appropriate CbcRangeCompare value (first argument being the
     383      sub/superset if that's the case). In case of overlap (and if \c
     384      replaceIfOverlap is true) replace the current branching object with one
     385      whose feasible region is the overlap.
     386   */
     387  virtual CbcRangeCompare compareBranchingObject
     388  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false) = 0;
     389
    351390protected:
    352391
     
    555594};
    556595
     596//#############################################################################
     597
    557598#endif
  • branches/heur/Cbc/src/CbcBranchCut.hpp

    r765 r886  
    147147  */
    148148  virtual bool boundBranch() const;
     149
     150  /** Return the type (an integer identifier) of \c this */
     151  virtual int type() const { return 200; }
     152
     153  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     154      same type and must have the same original object, but they may have
     155      different feasible regions.
     156      Return the appropriate CbcRangeCompare value (first argument being the
     157      sub/superset if that's the case). In case of overlap (and if \c
     158      replaceIfOverlap is true) replace the current branching object with one
     159      whose feasible region is the overlap.
     160   */
     161  virtual CbcRangeCompare compareBranchingObject
     162  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
    149163
    150164protected:
  • branches/heur/Cbc/src/CbcBranchDynamic.hpp

    r848 r886  
    393393  inline void setObject(CbcSimpleIntegerDynamicPseudoCost * object)
    394394  { object_=object;}
     395
     396  /** Return the type (an integer identifier) of \c this */
     397  virtual int type() const { return 400; }
     398
     399  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     400      same type and must have the same original object, but they may have
     401      different feasible regions.
     402      Return the appropriate CbcRangeCompare value (first argument being the
     403      sub/superset if that's the case). In case of overlap (and if \c
     404      replaceIfOverlap is true) replace the current branching object with one
     405      whose feasible region is the overlap.
     406   */
     407  virtual CbcRangeCompare compareBranchingObject
     408  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     409
    395410protected:
    396411  /// Change in guessed objective value for next branch
  • branches/heur/Cbc/src/CbcBranchLotsize.hpp

    r765 r886  
    202202  virtual void print();
    203203
     204  /** Return the type (an integer identifier) of \c this */
     205  virtual int type() const { return 300; }
     206
     207  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     208      same type and must have the same original object, but they may have
     209      different feasible regions.
     210      Return the appropriate CbcRangeCompare value (first argument being the
     211      sub/superset if that's the case). In case of overlap (and if \c
     212      replaceIfOverlap is true) replace the current branching object with one
     213      whose feasible region is the overlap.
     214   */
     215  virtual CbcRangeCompare compareBranchingObject
     216  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
     217
    204218protected:
    205219  /// Lower [0] and upper [1] bounds for the down arm (way_ = -1)
  • branches/heur/Cbc/src/CbcHeuristic.cpp

    r885 r886  
    2424#include "OsiPresolve.hpp"
    2525
     26//==============================================================================
     27
     28CbcHeuristicNode::CbcHeuristicNode(const CbcHeuristicNode& rhs)
     29{
     30  numObjects_ = rhs.numObjects_;
     31  brObj_ = new CbcBranchingObject*[numObjects_];
     32  for (int i = 0; i < numObjects_; ++i) {
     33    brObj_[i] = rhs.brObj_[i]->clone();
     34  }
     35}
     36
     37void
     38CbcHeuristicNodeList::gutsOfDelete()
     39{
     40  for (int i = nodes_.size() - 1; i >= 0; --i) {
     41    delete nodes_[i];
     42  }
     43}
     44
     45void
     46CbcHeuristicNodeList::gutsOfCopy(const CbcHeuristicNodeList& rhs)
     47{
     48  append(rhs);
     49}
     50
     51CbcHeuristicNodeList::CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs)
     52{
     53  gutsOfCopy(rhs);
     54}
     55
     56CbcHeuristicNodeList& CbcHeuristicNodeList::operator=
     57(const CbcHeuristicNodeList& rhs)
     58{
     59  if (this != &rhs) {
     60    gutsOfDelete();
     61    gutsOfCopy(rhs);
     62  }
     63  return *this;
     64}
     65
     66CbcHeuristicNodeList::~CbcHeuristicNodeList()
     67{
     68  gutsOfDelete();
     69}
     70
     71void
     72CbcHeuristicNodeList::append(CbcHeuristicNode*& node)
     73{
     74  nodes_.push_back(node);
     75  node = NULL;
     76}
     77
     78void
     79CbcHeuristicNodeList::append(const CbcHeuristicNodeList& nodes)
     80{
     81  nodes_.reserve(nodes_.size() + nodes.size());
     82  for (int i = 0; i < nodes.size(); ++i) {
     83    CbcHeuristicNode* node = new CbcHeuristicNode(*nodes.node(i));
     84    append(node);
     85  }
     86}
     87
     88//==============================================================================
     89
    2690// Default Constructor
    27 CbcHeuristic::CbcHeuristic()
    28   :model_(NULL),
    29    when_(2),
    30    numberNodes_(200),
    31    feasibilityPumpOptions_(-1),
    32    fractionSmall_(1.0),
    33    heuristicName_("Unknown"),
    34    howOften_(100),
    35    decayFactor_(0.5),
    36    lastRun_(0),
    37    runNodes_(NULL)
     91CbcHeuristic::CbcHeuristic() :
     92  model_(NULL),
     93  when_(2),
     94  numberNodes_(200),
     95  feasibilityPumpOptions_(-1),
     96  fractionSmall_(1.0),
     97  heuristicName_("Unknown"),
     98  howOften_(100),
     99  decayFactor_(0.5),
     100  shallowDepth_(0),
     101  howOftenShallow_(100),
     102  numInvocationsInShallow_(0),
     103  numInvocationsInDeep_(0),
     104  lastRunDeep_(0),
     105  numRuns_(0),
     106  minDistanceToRun_(4),
     107  runNodes_()
    38108{
    39109  // As CbcHeuristic virtual need to modify .cpp if above change
     
    41111
    42112// Constructor from model
    43 CbcHeuristic::CbcHeuristic(CbcModel & model)
    44 :
     113CbcHeuristic::CbcHeuristic(CbcModel & model) :
    45114  model_(&model),
    46115  when_(2),
     
    51120  howOften_(100),
    52121  decayFactor_(0.5),
    53   lastRun_(0),
    54   runNodes_(NULL)
     122  shallowDepth_(0),
     123  howOftenShallow_(100),
     124  numInvocationsInShallow_(0),
     125  numInvocationsInDeep_(0),
     126  lastRunDeep_(0),
     127  numRuns_(0),
     128  minDistanceToRun_(4),
     129  runNodes_()
    55130{}
    56131
     132void
     133CbcHeuristic::gutsOfCopy(const CbcHeuristic & rhs)
     134{
     135  model_ = rhs.model_;
     136  when_ = rhs.when_;
     137  numberNodes_ = rhs.numberNodes_;
     138  feasibilityPumpOptions_ = rhs.feasibilityPumpOptions_;
     139  fractionSmall_ = rhs.fractionSmall_;
     140  randomNumberGenerator_ = rhs.randomNumberGenerator_;
     141  heuristicName_ = rhs.heuristicName_;
     142  howOften_ = rhs.howOften_;
     143  decayFactor_ = rhs.howOften_;
     144  shallowDepth_= rhs.shallowDepth_;
     145  howOftenShallow_= rhs.howOftenShallow_;
     146  numInvocationsInShallow_ = rhs.numInvocationsInShallow_;
     147  numInvocationsInDeep_ = rhs.numInvocationsInDeep_;
     148  lastRunDeep_ = rhs.lastRunDeep_;
     149  numRuns_ = rhs.numRuns_;
     150  minDistanceToRun_ = rhs.minDistanceToRun_;
     151  runNodes_ = rhs.runNodes_;
     152}
    57153// Copy constructor
    58154CbcHeuristic::CbcHeuristic(const CbcHeuristic & rhs)
    59 :
    60   model_(rhs.model_),
    61   when_(rhs.when_),
    62   numberNodes_(rhs.numberNodes_),
    63   feasibilityPumpOptions_(rhs.feasibilityPumpOptions_),
    64   fractionSmall_(rhs.fractionSmall_),
    65   randomNumberGenerator_(rhs.randomNumberGenerator_),
    66   heuristicName_(rhs.heuristicName_),
    67   howOften_(rhs.howOften_),
    68   decayFactor_(rhs.howOften_),
    69   lastRun_(rhs.lastRun_),
    70   runNodes_(rhs.runNodes_)
    71 {}
     155{
     156  gutsOfCopy(rhs);
     157}
    72158
    73159// Assignment operator
     
    76162{
    77163  if (this!=&rhs) {
    78     model_ = rhs.model_;
    79     when_ = rhs.when_;
    80     numberNodes_ = rhs.numberNodes_;
    81     feasibilityPumpOptions_ = rhs.feasibilityPumpOptions_;
    82     fractionSmall_ = rhs.fractionSmall_;
    83     randomNumberGenerator_ = rhs.randomNumberGenerator_;
    84     heuristicName_ = rhs.heuristicName_ ;
    85     howOften_ = rhs.howOften_;
    86     decayFactor_ = rhs.howOften_;
    87     lastRun_ = rhs.lastRun_;
    88     runNodes_ = rhs.runNodes_;
     164    gutsOfDelete();
     165    gutsOfCopy(rhs);
    89166  }
    90167  return *this;
    91168}
     169
     170bool
     171CbcHeuristic::shouldHeurRun()
     172{
     173  const CbcNode* currentNode = model_->currentNode();
     174  if (currentNode == NULL) {
     175    return false;
     176  }
     177
     178  const int depth = currentNode->depth();
     179
     180  const int nodeCount = model_->getNodeCount();  // FIXME: check that this is
     181                                                 // correct in parallel
     182
     183  if (nodeCount == 0 || depth <= shallowDepth_) {
     184    // what to do when we are in the shallow part of the tree
     185    if (model_->getCurrentPassNumber() == 1) {
     186      // first time in the node...
     187      numInvocationsInShallow_ = 0;
     188    }
     189    ++numInvocationsInShallow_;
     190    // Very large howOftenShallow_ will give the original test:
     191    // (model_->getCurrentPassNumber() != 1)
     192    if ((numInvocationsInShallow_ % howOftenShallow_) != 1) {
     193      return false;
     194    }
     195    // LL: should we save these nodes in the list of nodes where the heur was
     196    // LL: run?
     197  } else {
     198    // deeper in the tree
     199    if (model_->getCurrentPassNumber() == 1) {
     200      // first time in the node...
     201      ++numInvocationsInDeep_;
     202    }
     203    if (numInvocationsInDeep_ - lastRunDeep_ < howOften_) {
     204      return false;
     205    }
     206    if (model_->getCurrentPassNumber() != 1) {
     207      // Run the heuristic only when first entering the node.
     208      // LL: I don't think this is right. It should run just before strong
     209      // LL: branching, I believe.
     210      return false;
     211    }
     212    // Get where we are and create the appropriate CbcHeuristicNode object
     213    CbcHeuristicNode* nodeDesc = new CbcHeuristicNode(*model_);
     214    if (nodeDesc->minDistance(runNodes_) < minDistanceToRun_) {
     215      delete nodeDesc;
     216      return false;
     217    }
     218    runNodes_.append(nodeDesc);
     219    ++lastRunDeep_;
     220  }
     221  ++numRuns_;
     222  return true;
     223}
     224
    92225
    93226// Resets stuff if model changes
     
    475608}
    476609
    477 //#######################################################################################
    478 
    479 inline int compare3BranchingObjects(const OsiBranchingObject* br0,
    480                                     const OsiBranchingObject* br1)
     610//##############################################################################
     611
     612inline int compare3BranchingObjects(const CbcBranchingObject* br0,
     613                                    const CbcBranchingObject* br1)
    481614{
    482615  const int t0 = br0->type();
     
    488621    return 1;
    489622  }
    490   return br0->compareBaseObject(br1);
    491 }
    492 
    493 //=======================================================================================
    494 
    495 inline bool compareBranchingObjects(const OsiBranchingObject* br0,
    496                                     const OsiBranchingObject* br1)
     623  return br0->compareOriginalObject(br1);
     624}
     625
     626//==============================================================================
     627
     628inline bool compareBranchingObjects(const CbcBranchingObject* br0,
     629                                    const CbcBranchingObject* br1)
    497630{
    498631  return compare3BranchingObjects(br0, br1) < 0;
    499632}
    500633
    501 //=======================================================================================
     634//==============================================================================
    502635
    503636CbcHeuristicNode::CbcHeuristicNode(CbcModel& model)
     
    506639  int depth = node->depth();
    507640  numObjects_ = depth; //??
    508   brObj_ = new OsiBranchingObject*[numObjects_];
     641  brObj_ = new CbcBranchingObject*[numObjects_];
    509642  CbcNodeInfo* nodeInfo = node->nodeInfo();
    510643  depth = 0;
    511644  while (nodeInfo) {
    512     brObj_[depth++] = node->branchingObject()->clone();
     645    const OsiBranchingObject* osibr =
     646      nodeInfo->owner()->branchingObject();
     647    const CbcBranchingObject* cbcbr =
     648      dynamic_cast<const CbcBranchingObject*>(osibr);
     649    assert(cbcbr);
     650    brObj_[depth++] = cbcbr->clone();
    513651    nodeInfo = nodeInfo->parent();
    514652  }
    515653  std::sort(brObj_, brObj_+depth, compareBranchingObjects);
    516654  int cnt = 0;
    517   OsiBranchingObject* br;
     655  CbcBranchingObject* br;
    518656  for (int i = 1; i < depth; ++i) {
    519657    if (compare3BranchingObjects(brObj_[cnt], brObj_[i]) == 0) {
     
    544682}
    545683
    546 //=======================================================================================
     684//==============================================================================
    547685
    548686double
     
    550688{
    551689  const double disjointWeight = 1;
    552   const double overlapWeight = 0.2;
    553   const double subsetWeight = 0.1;
     690  const double overlapWeight = 0.4;
     691  const double subsetWeight = 0.2;
    554692  int i = 0;
    555693  int j = 0;
    556   double distance = 0.0;
     694  double dist = 0.0;
    557695  while( i < numObjects_ && j < node->numObjects_) {
    558     const OsiBranchingObject* br0 = brObj_[i];
    559     const OsiBranchingObject* br1 = node->brObj_[j];
     696    CbcBranchingObject* br0 = brObj_[i];
     697    const CbcBranchingObject* br1 = node->brObj_[j];
    560698    const int brComp = compare3BranchingObjects(br0, br1);
    561699    switch (brComp) {
    562700    case -1:
    563       distance += subsetWeight;
     701      dist += subsetWeight;
    564702      ++i;
    565703      break;
    566704    case 1:
    567       distance += subsetWeight;
     705      dist += subsetWeight;
    568706      ++j;
    569707      break;
    570708    case 0:
    571709      {
    572         const int comp = brObj_[cnt]->compareBranchingObject(brObj_[i], NULL);
     710        const int comp = br0->compareBranchingObject(br1, false);
    573711        switch (comp) {
    574712        case 0: // disjoint decisions
    575           distance += disjointWeight;
     713          dist += disjointWeight;
    576714          break;
    577715        case 1: // subset one way or another
    578716        case 2:
    579           distance += subsetWeight;
     717          dist += subsetWeight;
    580718          break;
    581719        case 3: // overlap
    582           distance += overlapWeight;
     720          dist += overlapWeight;
    583721          break;
    584722        }
     
    587725    }
    588726  }
    589   distance += subsetWeight * (numObjects_ - i + node->numObjects_ - j);
    590   return distance;
    591 }
    592 
    593 //=======================================================================================
     727  dist += subsetWeight * (numObjects_ - i + node->numObjects_ - j);
     728  return dist;
     729}
     730
     731//==============================================================================
    594732
    595733CbcHeuristicNode::~CbcHeuristicNode()
     
    601739}
    602740
    603 //=======================================================================================
    604 
    605 CbcHeuristicNodeList::CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs)
    606 {
    607   nodes_ = rhs.nodes_;
    608 }
    609 
    610 //=======================================================================================
    611 
    612 CbcHeuristicNodeList&
    613 CbcHeuristicNodeList::operator=(const CbcHeuristicNodeList& rhs)
    614 {
    615   if (this != &rhs)
    616     nodes_ = rhs.nodes_;
    617 
    618   return *this;
    619 }
    620 
    621 //=======================================================================================
    622 
    623 bool
    624 CbcHeuristicNodeList::farFrom(const CbcHeuristicNode* node)
    625 {
    626   const double minDistance = 10.0;
    627 
    628   double distance = 0.0;
    629   for (int i = 0; i < (int) nodes_.size(); i++) {
    630     if(nodes_[i] != NULL)
    631       distance += nodes_[i]->distance(node);
    632   }
    633  
    634   if(distance > minDistance)
    635     return true;
    636 
    637   return false;
    638 }
    639 
    640 //#######################################################################################
     741//==============================================================================
     742
     743double
     744CbcHeuristicNode::minDistance(const CbcHeuristicNodeList& nodeList)
     745{
     746  double minDist = COIN_DBL_MAX;
     747  for (int i = nodeList.size() - 1; i >= 0; --i) {
     748    minDist = CoinMin(minDist, distance(nodeList.node(i)));
     749  }
     750  return minDist;
     751}
     752
     753//==============================================================================
     754
     755double
     756CbcHeuristicNode::avgDistance(const CbcHeuristicNodeList& nodeList)
     757{
     758  if (nodeList.size() == 0) {
     759    return COIN_DBL_MAX;
     760  }
     761  double sumDist = 0;
     762  for (int i = nodeList.size() - 1; i >= 0; --i) {
     763    sumDist += distance(nodeList.node(i));
     764  }
     765  return sumDist/nodeList.size();
     766}
     767
     768//##############################################################################
    641769
    642770// Default Constructor
  • branches/heur/Cbc/src/CbcHeuristic.hpp

    r885 r886  
    1717//#############################################################################
    1818
     19class CbcHeuristicNodeList;
     20class CbcBranchingObject;
     21
    1922/** A class describing the branching decisions that were made to get
    2023    to the node where a heuristics was invoked from */
    2124
    2225class CbcHeuristicNode {
     26private:
     27  CbcHeuristicNode();
     28  CbcHeuristicNode& operator=(const CbcHeuristicNode&);
    2329private:
    2430  /// The number of branching decisions made
     
    2733      listed multiple times. E.g., a general integer variable that has
    2834      been branched on multiple times. */
    29   OsiBranchingObject** brObj_;
    30 public:
    31   CbcHeuristicNode() {}
     35  CbcBranchingObject** brObj_;
     36public:
    3237  CbcHeuristicNode(CbcModel& model);
     38  CbcHeuristicNode(const CbcHeuristicNode& rhs);
    3339  ~CbcHeuristicNode();
    34 
    3540  double distance(const CbcHeuristicNode* node) const;
    36 #if 0
    37   inline swap(CbcHeuristicNode& node) {
    38     ::swap(numObjects_, node.numObjects_);
    39     ::swap(objects_, node.objects_);
    40   }
    41 #endif
     41  double minDistance(const CbcHeuristicNodeList& nodeList);
     42  double avgDistance(const CbcHeuristicNodeList& nodeList);
    4243};
    4344
    4445class CbcHeuristicNodeList {
     46private:
     47  void gutsOfDelete();
     48  void gutsOfCopy(const CbcHeuristicNodeList& rhs);
    4549private:
    4650  std::vector<CbcHeuristicNode*> nodes_;
     
    4953  CbcHeuristicNodeList(const CbcHeuristicNodeList& rhs);
    5054  CbcHeuristicNodeList& operator=(const CbcHeuristicNodeList& rhs);
    51   ~CbcHeuristicNodeList() {
    52     for (int i = nodes_.size() - 1; i >= 0; --i) {
    53       delete nodes_[i];
    54     }
    55   }
    56 
    57   bool farFrom(const CbcHeuristicNode* node);
    58   void append(CbcHeuristicNode*& node) {
    59     nodes_.push_back(node);
    60     node = NULL;
    61   }
    62   void append(CbcHeuristicNodeList& nodes) {
    63     nodes_.insert(nodes_.end(), nodes.nodes_.begin(), nodes.nodes_.end());
    64     nodes.nodes_.clear();
    65   }
     55  ~CbcHeuristicNodeList();
     56 
     57  void append(CbcHeuristicNode*& node);
     58  void append(const CbcHeuristicNodeList& nodes);
     59  inline const CbcHeuristicNode* node(int i) const { return nodes_[i]; }
     60  inline int size() const { return nodes_.size(); }
    6661};
    6762
     
    7065
    7166class CbcHeuristic {
     67private:
     68  void gutsOfDelete() {}
     69  void gutsOfCopy(const CbcHeuristic & rhs);
     70
    7271public:
    7372  // Default Constructor
     
    176175  void setSeed(int value);
    177176
     177  /** Check whether the heuristic should run */
     178  bool shouldHeurRun();
     179
    178180protected:
    179181
     
    192194  /// Name for printing
    193195  std::string heuristicName_;
     196
    194197  /// How often to do (code can change)
    195198  int howOften_;
    196199  /// How much to increase how often
    197200  double decayFactor_;
    198   /// Last node count where the heuristic was applied
    199   int lastRun_;
     201  /** Upto this depth we call the tree shallow and the heuristic can be called
     202      multiple times. That is, the test whether the current node is far from
     203      the others where the jeuristic was invoked will not be done, only the
     204      frequency will be tested. After that depth the heuristic will can be
     205      invoked only once per node, right before branching. That's when it'll be
     206      tested whether the heur should run at all. */
     207  int shallowDepth_;
     208  /** How often to invoke the heuristics in the shallow part of the tree */
     209  int howOftenShallow_;
     210  /** How many invocations happened within the same node when in a shallow
     211      part of the tree. */
     212  int numInvocationsInShallow_;
     213  /** How many invocations happened when in the deep part of the tree. For
     214      every node we count only one invocation. */
     215  int numInvocationsInDeep_;
     216  /** After how many deep invocations was the heuristic run last time */
     217  int lastRunDeep_;
     218  /// how many times the heuristic has actually run
     219  int numRuns_;
     220  /** How "far" should this node be from every other where the heuristic was
     221      run in order to allow the heuristic to run in this node, too. Currently
     222      this is tested, but we may switch to avgDistanceToRun_ in the future. */
     223  int minDistanceToRun_;
     224
    200225  /// The description of the nodes where this heuristic has been applied
    201   CbcHeuristicNodeList* runNodes_;
     226  CbcHeuristicNodeList runNodes_;
     227
    202228#if 0
    203229  /// Lower bounds of last node where the heuristic found a solution
  • branches/heur/Cbc/src/CbcHeuristicDiveCoefficient.cpp

    r885 r886  
    142142int
    143143CbcHeuristicDiveCoefficient::solution(double & solutionValue,
    144                                      double * betterSolution)
    145 {
    146   if (model_->getCurrentPassNumber() != 1) {
    147     return NULL;
    148   }
    149  
    150   const int nodeCount = model_->getNodeCount();  // FIXME: check that this is correct in parallel
    151   CbcHeuristicNode* nodeDesc = NULL;
    152   if (nodeCount != 0) {
    153     if (nodeCount - lastRun_ < howOften_) {
    154       return NULL;
    155     }
    156 
    157     // Get where we are and create the appropriate CbcHeuristicNode object
    158     nodeDesc = new CbcHeuristicNode(*model_);
    159     if (!runNodes_->farFrom(nodeDesc)) {
    160       delete nodeDesc;
    161       return NULL;
    162     }
    163   }
    164 
    165   if(nodeDesc != NULL)
    166     runNodes_->append(nodeDesc);
    167  
    168   lastRun_ = nodeCount;
     144                                      double * betterSolution)
     145{
     146  if (! shouldHeurRun()) {
     147    return 0;
     148  }
    169149
    170150#if 0
     
    464444  delete [] rowActivity;
    465445  delete solver;
    466   delete nodeDesc;
    467446  return returnCode;
    468447}
Note: See TracChangeset for help on using the changeset viewer.