Ignore:
Timestamp:
Apr 10, 2008 1:55:10 PM (13 years ago)
Author:
ladanyi
Message:

Incorporated changes from branches/heur

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcBranchActual.cpp

    r904 r912  
    1111//#define CBC_DEBUG
    1212
     13#include "CoinTypes.hpp"
    1314#include "OsiSolverInterface.hpp"
    1415#include "OsiSolverBranch.hpp"
     
    1819#include "CoinSort.hpp"
    1920#include "CoinError.hpp"
     21
     22//##############################################################################
    2023
    2124// Default Constructor
     
    332335  return branch;
    333336}
     337
     338//##############################################################################
    334339
    335340// Default Constructor
     
    709714}
    710715
     716//##############################################################################
     717
    711718/** Default Constructor
    712719
     
    939946  return NULL;
    940947}
     948
     949//##############################################################################
     950
    941951// Default Constructor
    942952CbcIntegerBranchingObject::CbcIntegerBranchingObject()
     
    13321342}
    13331343
     1344/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     1345    same type and must have the same original object, but they may have
     1346    different feasible regions.
     1347    Return the appropriate CbcRangeCompare value (first argument being the
     1348    sub/superset if that's the case). In case of overlap (and if \c
     1349    replaceIfOverlap is true) replace the current branching object with one
     1350    whose feasible region is the overlap.
     1351   */
     1352CbcRangeCompare
     1353CbcIntegerBranchingObject::compareBranchingObject
     1354(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     1355{
     1356  const CbcIntegerBranchingObject* br =
     1357    dynamic_cast<const CbcIntegerBranchingObject*>(brObj);
     1358  assert(br);
     1359  double* thisBd = way_ < 0 ? down_ : up_;
     1360  const double* otherBd = br->way_ < 0 ? br->down_ : br->up_;
     1361  return CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
     1362}
     1363
     1364//##############################################################################
    13341365
    13351366/** Default Constructor
     
    15691600}
    15701601
     1602//##############################################################################
     1603
    15711604// Default Constructor
    15721605CbcIntegerPseudoCostBranchingObject::CbcIntegerPseudoCostBranchingObject()
     
    16401673}
    16411674
     1675/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     1676    same type and must have the same original object, but they may have
     1677    different feasible regions.
     1678    Return the appropriate CbcRangeCompare value (first argument being the
     1679    sub/superset if that's the case). In case of overlap (and if \c
     1680    replaceIfOverlap is true) replace the current branching object with one
     1681    whose feasible region is the overlap.
     1682*/
     1683CbcRangeCompare
     1684CbcIntegerPseudoCostBranchingObject::compareBranchingObject
     1685(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     1686{
     1687  const CbcIntegerPseudoCostBranchingObject* br =
     1688    dynamic_cast<const CbcIntegerPseudoCostBranchingObject*>(brObj);
     1689  assert(br);
     1690  double* thisBd = way_ < 0 ? down_ : up_;
     1691  const double* otherBd = br->way_ < 0 ? br->down_ : br->up_;
     1692  return CbcCompareRanges(thisBd, otherBd, replaceIfOverlap);
     1693}
     1694
     1695
     1696//##############################################################################
    16421697
    16431698// Default Constructor
     
    18141869  printf("\n");
    18151870}
    1816  
     1871
     1872static inline int
     1873CbcCompareCliques(const CbcClique* cl0, const CbcClique* cl1)
     1874{
     1875  if (cl0->cliqueType() < cl1->cliqueType()) {
     1876    return -1;
     1877  }
     1878  if (cl0->cliqueType() > cl1->cliqueType()) {
     1879    return 1;
     1880  }
     1881  if (cl0->numberMembers() != cl1->numberMembers()) {
     1882    return cl0->numberMembers() - cl1->numberMembers();
     1883  }
     1884  if (cl0->numberNonSOSMembers() != cl1->numberNonSOSMembers()) {
     1885    return cl0->numberNonSOSMembers() - cl1->numberNonSOSMembers();
     1886  }
     1887  return memcmp(cl0->members(), cl1->members(),
     1888                cl0->numberMembers() * sizeof(int));
     1889}
     1890
     1891/** Compare the original object of \c this with the original object of \c
     1892    brObj. Assumes that there is an ordering of the original objects.
     1893    This method should be invoked only if \c this and brObj are of the same
     1894    type.
     1895    Return negative/0/positive depending on whether \c this is
     1896    smaller/same/larger than the argument.
     1897*/
     1898int
     1899CbcCliqueBranchingObject::compareOriginalObject
     1900(const CbcBranchingObject* brObj) const
     1901{
     1902  const CbcCliqueBranchingObject* br =
     1903    dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
     1904  assert(br);
     1905  return CbcCompareCliques(clique_, br->clique_);
     1906}
     1907
     1908/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     1909    same type and must have the same original object, but they may have
     1910    different feasible regions.
     1911    Return the appropriate CbcRangeCompare value (first argument being the
     1912    sub/superset if that's the case). In case of overlap (and if \c
     1913    replaceIfOverlap is true) replace the current branching object with one
     1914    whose feasible region is the overlap.
     1915*/
     1916CbcRangeCompare
     1917CbcCliqueBranchingObject::compareBranchingObject
     1918(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     1919{
     1920  const CbcCliqueBranchingObject* br =
     1921    dynamic_cast<const CbcCliqueBranchingObject*>(brObj);
     1922  assert(br);
     1923  unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
     1924  const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
     1925  const CoinUInt64 cl0 =
     1926    (static_cast<CoinUInt64>(thisMask[0]) << 32) | thisMask[1];
     1927  const CoinUInt64 cl1 =
     1928    (static_cast<CoinUInt64>(otherMask[0]) << 32) | otherMask[1];
     1929  if (cl0 == cl1) {
     1930    return CbcRangeSame;
     1931  }
     1932  const CoinUInt64 cl_intersection = (cl0 & cl1);
     1933  if (cl_intersection == cl0) {
     1934    return CbcRangeSuperset;
     1935  }
     1936  if (cl_intersection == cl1) {
     1937    return CbcRangeSubset;
     1938  }
     1939  const CoinUInt64 cl_xor = (cl0 ^ cl1);
     1940  if (cl_intersection == 0 && cl_xor == 0) {
     1941    return CbcRangeDisjoint;
     1942  }
     1943  const CoinUInt64 cl_union = (cl0 | cl1);
     1944  thisMask[0] = static_cast<unsigned int>(cl_union >> 32);
     1945  thisMask[1] = static_cast<unsigned int>(cl_union & 0xffffffff);
     1946  return CbcRangeOverlap;
     1947}
     1948
     1949//##############################################################################
     1950
    18171951// Default Constructor
    18181952CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject()
     
    20052139  printf("\n");
    20062140}
     2141
     2142/** Compare the original object of \c this with the original object of \c
     2143    brObj. Assumes that there is an ordering of the original objects.
     2144    This method should be invoked only if \c this and brObj are of the same
     2145    type.
     2146    Return negative/0/positive depending on whether \c this is
     2147    smaller/same/larger than the argument.
     2148*/
     2149int
     2150CbcLongCliqueBranchingObject::compareOriginalObject
     2151(const CbcBranchingObject* brObj) const
     2152{
     2153  const CbcLongCliqueBranchingObject* br =
     2154    dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
     2155  assert(br);
     2156  return CbcCompareCliques(clique_, br->clique_);
     2157}
     2158
     2159/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     2160    same type and must have the same original object, but they may have
     2161    different feasible regions.
     2162    Return the appropriate CbcRangeCompare value (first argument being the
     2163    sub/superset if that's the case). In case of overlap (and if \c
     2164    replaceIfOverlap is true) replace the current branching object with one
     2165    whose feasible region is the overlap.
     2166*/
     2167CbcRangeCompare
     2168CbcLongCliqueBranchingObject::compareBranchingObject
     2169(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     2170{
     2171  const CbcLongCliqueBranchingObject* br =
     2172    dynamic_cast<const CbcLongCliqueBranchingObject*>(brObj);
     2173  assert(br);
     2174  const int numberMembers = clique_->numberMembers();
     2175  const int numberWords=(numberMembers+31)>>5;
     2176  unsigned int* thisMask = way_ < 0 ? upMask_ : downMask_;
     2177  const unsigned int* otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
     2178
     2179  if (memcmp(thisMask, otherMask, numberWords * sizeof(unsigned int)) == 0) {
     2180    return CbcRangeSame;
     2181  }
     2182  bool canBeSuperset = true;
     2183  bool canBeSubset = true;
     2184  int i;
     2185  for (i = numberWords-1; i >= 0 && (canBeSuperset || canBeSubset); --i) {
     2186    const unsigned int both = (thisMask[i] & otherMask[i]);
     2187    canBeSuperset &= (both == thisMask[i]);
     2188    canBeSubset &= (both == otherMask[i]);
     2189  }
     2190  if (canBeSuperset) {
     2191    return CbcRangeSuperset;
     2192  }
     2193  if (canBeSubset) {
     2194    return CbcRangeSubset;
     2195  }
     2196
     2197  for (i = numberWords-1; i >= 0; --i) {
     2198    if ((thisMask[i] ^ otherMask[i]) != 0) {
     2199      break;
     2200    }
     2201  }
     2202  if (i == -1) { // complement
     2203    return CbcRangeDisjoint;
     2204  }
     2205  // must be overlap
     2206  for (i = numberWords-1; i >= 0; --i) {
     2207    thisMask[i] |= otherMask[i];
     2208  }
     2209  return CbcRangeOverlap;
     2210}
     2211
     2212//##############################################################################
     2213
    20072214// Default Constructor
    20082215CbcSOSBranchingObject::CbcSOSBranchingObject()
    2009   :CbcBranchingObject()
     2216  :CbcBranchingObject(),
     2217   firstNonzero_(-1),
     2218   lastNonzero_(-1)
    20102219{
    20112220  set_ = NULL;
     
    20222231  set_ = set;
    20232232  separator_ = separator;
     2233  computeNonzeroRange();
    20242234}
    20252235
    20262236// Copy constructor
    2027 CbcSOSBranchingObject::CbcSOSBranchingObject ( const CbcSOSBranchingObject & rhs) :CbcBranchingObject(rhs)
     2237CbcSOSBranchingObject::CbcSOSBranchingObject (const CbcSOSBranchingObject & rhs)
     2238 :CbcBranchingObject(rhs),
     2239  firstNonzero_(rhs.firstNonzero_),
     2240  lastNonzero_(rhs.lastNonzero_)
    20282241{
    20292242  set_=rhs.set_;
     
    20392252    set_=rhs.set_;
    20402253    separator_ = rhs.separator_;
     2254    firstNonzero_ = rhs.firstNonzero_;
     2255    lastNonzero_ = rhs.lastNonzero_;
    20412256  }
    20422257  return *this;
     
    20532268{
    20542269}
     2270
     2271void
     2272CbcSOSBranchingObject::computeNonzeroRange()
     2273{
     2274  const int numberMembers = set_->numberMembers();
     2275  const double * weights = set_->weights();
     2276  int i = 0;
     2277  if (way_ < 0) {
     2278    for ( i=0;i<numberMembers;i++) {
     2279      if (weights[i] > separator_)
     2280        break;
     2281    }
     2282    assert (i<numberMembers);
     2283    firstNonzero_ = 0;
     2284    lastNonzero_ = i;
     2285  } else {
     2286    for ( i=0;i<numberMembers;i++) {
     2287      if (weights[i] >= separator_)
     2288        break;
     2289    }
     2290    assert (i<numberMembers);
     2291    firstNonzero_ = i;
     2292    lastNonzero_ = numberMembers;
     2293  }
     2294}
     2295
    20552296double
    20562297CbcSOSBranchingObject::branch()
     
    20852326    way_=-1;      // Swap direction
    20862327  }
     2328  computeNonzeroRange();
    20872329  return 0.0;
    20882330}
     
    21452387}
    21462388 
     2389/** Compare the original object of \c this with the original object of \c
     2390    brObj. Assumes that there is an ordering of the original objects.
     2391    This method should be invoked only if \c this and brObj are of the same
     2392    type.
     2393    Return negative/0/positive depending on whether \c this is
     2394    smaller/same/larger than the argument.
     2395*/
     2396int
     2397CbcSOSBranchingObject::compareOriginalObject
     2398(const CbcBranchingObject* brObj) const
     2399{
     2400  const CbcSOSBranchingObject* br =
     2401    dynamic_cast<const CbcSOSBranchingObject*>(brObj);
     2402  assert(br);
     2403  const CbcSOS* s0 = set_;
     2404  const CbcSOS* s1 = br->set_;
     2405  if (s0->sosType() != s1->sosType()) {
     2406    return s0->sosType() - s1->sosType();
     2407  }
     2408  if (s0->numberMembers() != s1->numberMembers()) {
     2409    return s0->numberMembers() - s1->numberMembers();
     2410  }
     2411  const int memberCmp = memcmp(s0->members(), s1->members(),
     2412                               s0->numberMembers() * sizeof(int));
     2413  if (memberCmp != 0) {
     2414    return memberCmp;
     2415  }
     2416  return memcmp(s0->weights(), s1->weights(),
     2417                s0->numberMembers() * sizeof(double));
     2418}
     2419
     2420/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     2421    same type and must have the same original object, but they may have
     2422    different feasible regions.
     2423    Return the appropriate CbcRangeCompare value (first argument being the
     2424    sub/superset if that's the case). In case of overlap (and if \c
     2425    replaceIfOverlap is true) replace the current branching object with one
     2426    whose feasible region is the overlap.
     2427*/
     2428CbcRangeCompare
     2429CbcSOSBranchingObject::compareBranchingObject
     2430(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     2431{
     2432  const CbcSOSBranchingObject* br =
     2433    dynamic_cast<const CbcSOSBranchingObject*>(brObj);
     2434  assert(br);
     2435  if (firstNonzero_ < br->firstNonzero_) {
     2436    if (lastNonzero_ >= br->lastNonzero_) {
     2437      return CbcRangeSuperset;
     2438    } else if (lastNonzero_ <= br->firstNonzero_) {
     2439      return CbcRangeDisjoint;
     2440    } else {
     2441      // overlap
     2442      if (replaceIfOverlap) {
     2443        firstNonzero_ = br->firstNonzero_;
     2444      }
     2445      return CbcRangeOverlap;
     2446    }
     2447  } else if (firstNonzero_ > br->firstNonzero_) {
     2448    if (lastNonzero_ <= br->lastNonzero_) {
     2449      return CbcRangeSubset;
     2450    } else if (firstNonzero_ >= br->lastNonzero_) {
     2451      return CbcRangeDisjoint;
     2452    } else {
     2453      // overlap
     2454      if (replaceIfOverlap) {
     2455        lastNonzero_ = br->lastNonzero_;
     2456      }
     2457      return CbcRangeOverlap;
     2458    }
     2459  } else {
     2460    if (lastNonzero_ == br->lastNonzero_) {
     2461      return CbcRangeSame;
     2462    }
     2463    return lastNonzero_ < br->lastNonzero_ ? CbcRangeSubset : CbcRangeSuperset;
     2464  }
     2465  return CbcRangeSame; // fake return
     2466}
     2467
     2468//##############################################################################
     2469
    21472470// Default Constructor
    21482471CbcBranchDefaultDecision::CbcBranchDefaultDecision()
     
    25552878}
    25562879
     2880//##############################################################################
     2881
    25572882// Default Constructor
    25582883CbcFollowOn::CbcFollowOn ()
     
    28933218  return branch;
    28943219}
     3220
     3221//##############################################################################
     3222
    28953223// Default Constructor
    28963224CbcFixingBranchingObject::CbcFixingBranchingObject()
     
    30133341  printf("\n");
    30143342}
     3343
     3344/** Compare the original object of \c this with the original object of \c
     3345    brObj. Assumes that there is an ordering of the original objects.
     3346    This method should be invoked only if \c this and brObj are of the same
     3347    type.
     3348    Return negative/0/positive depending on whether \c this is
     3349    smaller/same/larger than the argument.
     3350*/
     3351int
     3352CbcFixingBranchingObject::compareOriginalObject
     3353(const CbcBranchingObject* brObj) const
     3354{
     3355  throw("must implement");
     3356}
     3357
     3358/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     3359    same type and must have the same original object, but they may have
     3360    different feasible regions.
     3361    Return the appropriate CbcRangeCompare value (first argument being the
     3362    sub/superset if that's the case). In case of overlap (and if \c
     3363    replaceIfOverlap is true) replace the current branching object with one
     3364    whose feasible region is the overlap.
     3365   */
     3366CbcRangeCompare
     3367CbcFixingBranchingObject::compareBranchingObject
     3368(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     3369{
     3370  const CbcFixingBranchingObject* br =
     3371    dynamic_cast<const CbcFixingBranchingObject*>(brObj);
     3372  assert(br);
     3373  // If two FixingBranchingObject's have the same base object then it's pretty
     3374  // much guaranteed
     3375  throw("must implement");
     3376}
     3377
     3378//##############################################################################
     3379
    30153380// Default Constructor
    30163381CbcNWay::CbcNWay ()
     
    32623627}
    32633628 
     3629//##############################################################################
     3630
    32643631// Default Constructor
    32653632CbcNWayBranchingObject::CbcNWayBranchingObject()
     
    33833750  printf("\n");
    33843751}
     3752
     3753/** Compare the original object of \c this with the original object of \c
     3754    brObj. Assumes that there is an ordering of the original objects.
     3755    This method should be invoked only if \c this and brObj are of the same
     3756    type.
     3757    Return negative/0/positive depending on whether \c this is
     3758    smaller/same/larger than the argument.
     3759*/
     3760int
     3761CbcNWayBranchingObject::compareOriginalObject
     3762(const CbcBranchingObject* brObj) const
     3763{
     3764  throw("must implement");
     3765}
     3766
     3767/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     3768    same type and must have the same original object, but they may have
     3769    different feasible regions.
     3770    Return the appropriate CbcRangeCompare value (first argument being the
     3771    sub/superset if that's the case). In case of overlap (and if \c
     3772    replaceIfOverlap is true) replace the current branching object with one
     3773    whose feasible region is the overlap.
     3774*/
     3775CbcRangeCompare
     3776CbcNWayBranchingObject::compareBranchingObject
     3777(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     3778{
     3779  throw("must implement");
     3780}
     3781
     3782//##############################################################################
    33853783
    33863784// Default Constructor
     
    35503948}
    35513949
     3950//##############################################################################
     3951
    35523952// Default Constructor
    35533953CbcDummyBranchingObject::CbcDummyBranchingObject(CbcModel * model)
     
    35993999  printf("Dummy branch\n");
    36004000}
     4001
     4002/** Compare the original object of \c this with the original object of \c
     4003    brObj. Assumes that there is an ordering of the original objects.
     4004    This method should be invoked only if \c this and brObj are of the same
     4005    type.
     4006    Return negative/0/positive depending on whether \c this is
     4007    smaller/same/larger than the argument.
     4008*/
     4009int
     4010CbcDummyBranchingObject::compareOriginalObject
     4011(const CbcBranchingObject* brObj) const
     4012{
     4013  throw("must implement");
     4014}
     4015
     4016/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
     4017    same type and must have the same original object, but they may have
     4018    different feasible regions.
     4019    Return the appropriate CbcRangeCompare value (first argument being the
     4020    sub/superset if that's the case). In case of overlap (and if \c
     4021    replaceIfOverlap is true) replace the current branching object with one
     4022    whose feasible region is the overlap.
     4023*/
     4024CbcRangeCompare
     4025CbcDummyBranchingObject::compareBranchingObject
     4026(const CbcBranchingObject* brObj, const bool replaceIfOverlap)
     4027{
     4028  throw("must implement");
     4029}
     4030
Note: See TracChangeset for help on using the changeset viewer.