Ignore:
Timestamp:
Jan 16, 2013 1:41:25 PM (7 years ago)
Author:
forrest
Message:

multiple root solvers, stronger strong branching and cutoff as constraint

File:
1 edited

Legend:

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

    r1641 r1839  
    128128    }
    129129}
    130 
     130static double multiplier[] = {1.23456789e2,-9.87654321};
     131static int hashCut (const OsiRowCut2 & x, int size)
     132{
     133  int xN =x.row().getNumElements();
     134  double xLb = x.lb();
     135  double xUb = x.ub();
     136  const int * xIndices = x.row().getIndices();
     137  const double * xElements = x.row().getElements();
     138  unsigned int hashValue;
     139  double value=1.0;
     140  if (xLb>-1.0e10)
     141    value += xLb*multiplier[0];
     142  if (xUb<1.0e10)
     143    value += xUb*multiplier[1];
     144  for( int j=0;j<xN;j++) {
     145    int xColumn = xIndices[j];
     146    double xValue = xElements[j];
     147    int k=(j&1);
     148    value += (j+1)*multiplier[k]*(xColumn+1)*xValue;
     149  }
     150  // should be compile time but too lazy for now
     151  if (sizeof(value)>sizeof(hashValue)) {
     152    assert (sizeof(value)==2*sizeof(hashValue));
     153    union { double d; int i[2]; } xx;
     154    xx.d = value;
     155    hashValue = (xx.i[0] + xx.i[1]);
     156  } else {
     157    assert (sizeof(value)==sizeof(hashValue));
     158    union { double d; unsigned int i[2]; } xx;
     159    xx.d = value;
     160    hashValue = xx.i[0];
     161  }
     162  return hashValue%(size);
     163}
     164static int hashCut2 (const OsiRowCut2 & x, int size)
     165{
     166  int xN =x.row().getNumElements();
     167  double xLb = x.lb();
     168  double xUb = x.ub();
     169  const int * xIndices = x.row().getIndices();
     170  const double * xElements = x.row().getElements();
     171  unsigned int hashValue;
     172  double value=1.0;
     173  if (xLb>-1.0e10)
     174    value += xLb*multiplier[0];
     175  if (xUb<1.0e10)
     176    value += xUb*multiplier[1];
     177  for( int j=0;j<xN;j++) {
     178    int xColumn = xIndices[j];
     179    double xValue = xElements[j];
     180    int k=(j&1);
     181    value += (j+1)*multiplier[k]*(xColumn+1)*xValue;
     182  }
     183  // should be compile time but too lazy for now
     184  if (sizeof(value)>sizeof(hashValue)) {
     185    assert (sizeof(value)==2*sizeof(hashValue));
     186    union { double d; int i[2]; } xx;
     187    xx.d = value;
     188    hashValue = (xx.i[0] + xx.i[1]);
     189  } else {
     190    assert (sizeof(value)==sizeof(hashValue));
     191    union { double d; unsigned int i[2]; } xx;
     192    xx.d = value;
     193    hashValue = xx.i[0];
     194  }
     195  return hashValue%(size);
     196}
     197static bool same (const OsiRowCut2 & x, const OsiRowCut2 & y)
     198{
     199  int xN =x.row().getNumElements();
     200  int yN =y.row().getNumElements();
     201  bool identical=false;
     202  if (xN==yN) {
     203    double xLb = x.lb();
     204    double xUb = x.ub();
     205    double yLb = y.lb();
     206    double yUb = y.ub();
     207    if (fabs(xLb-yLb)<1.0e-8&&fabs(xUb-yUb)<1.0e-8) {
     208      const int * xIndices = x.row().getIndices();
     209      const double * xElements = x.row().getElements();
     210      const int * yIndices = y.row().getIndices();
     211      const double * yElements = y.row().getElements();
     212      int j;
     213      for( j=0;j<xN;j++) {
     214        if (xIndices[j]!=yIndices[j])
     215          break;
     216        if (fabs(xElements[j]-yElements[j])>1.0e-12)
     217          break;
     218      }
     219      identical =  (j==xN);
     220    }
     221  }
     222  return identical;
     223}
     224static bool same2 (const OsiRowCut2 & x, const OsiRowCut2 & y)
     225{
     226  int xN =x.row().getNumElements();
     227  int yN =y.row().getNumElements();
     228  bool identical=false;
     229  if (xN==yN) {
     230    double xLb = x.lb();
     231    double xUb = x.ub();
     232    double yLb = y.lb();
     233    double yUb = y.ub();
     234    if (fabs(xLb-yLb)<1.0e-8&&fabs(xUb-yUb)<1.0e-8) {
     235      const int * xIndices = x.row().getIndices();
     236      const double * xElements = x.row().getElements();
     237      const int * yIndices = y.row().getIndices();
     238      const double * yElements = y.row().getElements();
     239      int j;
     240      for( j=0;j<xN;j++) {
     241        if (xIndices[j]!=yIndices[j])
     242          break;
     243        if (fabs(xElements[j]-yElements[j])>1.0e-12)
     244          break;
     245      }
     246      identical =  (j==xN);
     247    }
     248  }
     249  return identical;
     250}
     251CbcRowCuts::CbcRowCuts(int initialMaxSize, int hashMultiplier)
     252{
     253  numberCuts_=0;
     254  size_ = initialMaxSize;
     255  hashMultiplier_ = hashMultiplier;
     256  int hashSize=hashMultiplier_*size_;
     257  if (size_) {
     258    rowCut_ = new  OsiRowCut2 * [size_];
     259    hash_ = new CoinHashLink[hashSize];
     260  } else {
     261    rowCut_ = NULL;
     262    hash_ = NULL;
     263  }
     264  for (int i=0;i<hashSize;i++) {
     265    hash_[i].index=-1;
     266    hash_[i].next=-1;
     267  }
     268  lastHash_=-1;
     269}
     270CbcRowCuts::~CbcRowCuts()
     271{
     272  for (int i=0;i<numberCuts_;i++)
     273    delete rowCut_[i];
     274  delete [] rowCut_;
     275  delete [] hash_;
     276}
     277CbcRowCuts::CbcRowCuts(const CbcRowCuts& rhs)
     278{
     279  numberCuts_=rhs.numberCuts_;
     280  hashMultiplier_ = rhs.hashMultiplier_;
     281  size_ = rhs.size_;
     282  int hashSize= size_*hashMultiplier_;
     283  lastHash_=rhs.lastHash_;
     284  if (size_) {
     285    rowCut_ = new  OsiRowCut2 * [size_];
     286    hash_ = new CoinHashLink[hashSize];
     287    for (int i=0;i<hashSize;i++) {
     288      hash_[i] = rhs.hash_[i];
     289    }
     290    for (int i=0;i<size_;i++) {
     291      if (rhs.rowCut_[i])
     292        rowCut_[i]=new OsiRowCut2(*rhs.rowCut_[i]);
     293      else
     294        rowCut_[i]=NULL;
     295    }
     296  } else {
     297    rowCut_ = NULL;
     298    hash_ = NULL;
     299  }
     300}
     301CbcRowCuts&
     302CbcRowCuts::operator=(const CbcRowCuts& rhs)
     303{
     304  if (this != &rhs) {
     305    for (int i=0;i<numberCuts_;i++)
     306      delete rowCut_[i];
     307    delete [] rowCut_;
     308    delete [] hash_;
     309    numberCuts_=rhs.numberCuts_;
     310    hashMultiplier_ = rhs.hashMultiplier_;
     311    size_ = rhs.size_;
     312    lastHash_=rhs.lastHash_;
     313    if (size_) {
     314      rowCut_ = new  OsiRowCut2 * [size_];
     315      int hashSize= size_*hashMultiplier_;
     316      hash_ = new CoinHashLink[hashSize];
     317      for (int i=0;i<hashSize;i++) {
     318        hash_[i] = rhs.hash_[i];
     319      }
     320      for (int i=0;i<size_;i++) {
     321        if (rhs.rowCut_[i])
     322          rowCut_[i]=new OsiRowCut2(*rhs.rowCut_[i]);
     323        else
     324          rowCut_[i]=NULL;
     325      }
     326    } else {
     327      rowCut_ = NULL;
     328      hash_ = NULL;
     329    }
     330  }
     331  return *this;
     332}
     333void
     334CbcRowCuts::eraseRowCut(int sequence)
     335{
     336  // find
     337  assert (sequence>=0&&sequence<numberCuts_);
     338  OsiRowCut2 * cut = rowCut_[sequence];
     339  int hashSize= size_*hashMultiplier_;
     340  int ipos = hashCut(*cut,hashSize);
     341  int found = -1;
     342  while ( true ) {
     343    int j1 = hash_[ipos].index;
     344    if ( j1 >= 0 ) {
     345      if (j1!=sequence) {
     346        int k = hash_[ipos].next;
     347        if ( k != -1 )
     348          ipos = k;
     349        else
     350          break;
     351      } else {
     352        found = j1;
     353        break;
     354      }
     355    } else {
     356      break;
     357    }
     358  }
     359  assert (found>=0);
     360  assert (hash_[ipos].index==sequence);
     361  // shuffle up
     362  while (hash_[ipos].next>=0) {
     363    int k = hash_[ipos].next;
     364    hash_[ipos]=hash_[k];
     365    ipos=k;
     366  }
     367  delete cut;
     368  // move last to found
     369  numberCuts_--;
     370  if (numberCuts_) {
     371    ipos = hashCut(*rowCut_[numberCuts_],hashSize);
     372    while ( true ) {
     373      int j1 = hash_[ipos].index;
     374      if (j1!=numberCuts_) {
     375        int k = hash_[ipos].next;
     376        ipos = k;
     377      } else {
     378        // change
     379        hash_[ipos].index=found;
     380        rowCut_[found]=rowCut_[numberCuts_];
     381        rowCut_[numberCuts_]=NULL;
     382        break;
     383      }
     384    }
     385  }
     386  assert (!rowCut_[numberCuts_]);
     387}
     388// Return 0 if added, 1 if not, -1 if not added because of space
     389int
     390CbcRowCuts::addCutIfNotDuplicate(const OsiRowCut & cut,int whichType)
     391{
     392  int hashSize= size_*hashMultiplier_;
     393  if (numberCuts_==size_) {
     394    size_ = 2*size_+100;
     395    hashSize=hashMultiplier_*size_;
     396    OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
     397    delete [] hash_;
     398    hash_ = new CoinHashLink[hashSize];
     399    for (int i=0;i<hashSize;i++) {
     400      hash_[i].index=-1;
     401      hash_[i].next=-1;
     402    }
     403    for (int i=0;i<numberCuts_;i++) {
     404      temp[i]=rowCut_[i];
     405      int ipos = hashCut(*temp[i],hashSize);
     406      int found = -1;
     407      int jpos=ipos;
     408      while ( true ) {
     409        int j1 = hash_[ipos].index;
     410       
     411        if ( j1 >= 0 ) {
     412          if ( !same(*temp[i],*temp[j1]) ) {
     413            int k = hash_[ipos].next;
     414            if ( k != -1 )
     415              ipos = k;
     416            else
     417              break;
     418          } else {
     419            found = j1;
     420            break;
     421          }
     422        } else {
     423          break;
     424        }
     425      }
     426      if (found<0) {
     427        assert (hash_[ipos].next==-1);
     428        if (ipos==jpos) {
     429          // first
     430          hash_[ipos].index=i;
     431        } else {
     432          // find next space
     433          while ( true ) {
     434            ++lastHash_;
     435            assert (lastHash_<hashSize);
     436            if ( hash_[lastHash_].index == -1 )
     437              break;
     438          }
     439          hash_[ipos].next = lastHash_;
     440          hash_[lastHash_].index = i;
     441        }
     442      }
     443    }
     444    delete [] rowCut_;
     445    rowCut_ = temp;
     446  }
     447  if (numberCuts_<size_) {
     448    double newLb = cut.lb();
     449    double newUb = cut.ub();
     450    CoinPackedVector vector = cut.row();
     451    int numberElements =vector.getNumElements();
     452    int * newIndices = vector.getIndices();
     453    double * newElements = vector.getElements();
     454    CoinSort_2(newIndices,newIndices+numberElements,newElements);
     455    int i;
     456    bool bad=false;
     457    for (i=0;i<numberElements;i++) {
     458      double value = fabs(newElements[i]);
     459      if (value<1.0e-12||value>1.0e12)
     460        bad=true;
     461    }
     462    if (bad)
     463      return 1;
     464    OsiRowCut2 newCut(whichType);
     465    newCut.setLb(newLb);
     466    newCut.setUb(newUb);
     467    newCut.setRow(vector);
     468    int ipos = hashCut(newCut,hashSize);
     469    int found = -1;
     470    int jpos=ipos;
     471    while ( true ) {
     472      int j1 = hash_[ipos].index;
     473     
     474      if ( j1 >= 0 ) {
     475        if ( !same(newCut,*rowCut_[j1]) ) {
     476          int k = hash_[ipos].next;
     477          if ( k != -1 )
     478            ipos = k;
     479          else
     480            break;
     481        } else {
     482          found = j1;
     483          break;
     484        }
     485      } else {
     486        break;
     487      }
     488    }
     489    if (found<0) {
     490      assert (hash_[ipos].next==-1);
     491      if (ipos==jpos) {
     492        // first
     493        hash_[ipos].index=numberCuts_;
     494      } else {
     495        // find next space
     496        while ( true ) {
     497          ++lastHash_;
     498          assert (lastHash_<hashSize);
     499          if ( hash_[lastHash_].index == -1 )
     500            break;
     501        }
     502        hash_[ipos].next = lastHash_;
     503        hash_[lastHash_].index = numberCuts_;
     504      }
     505      OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
     506      newCutPtr->setLb(newLb);
     507      newCutPtr->setUb(newUb);
     508      newCutPtr->setRow(vector);
     509      rowCut_[numberCuts_++]=newCutPtr;
     510      return 0;
     511    } else {
     512      return 1;
     513    }
     514  } else {
     515    return -1;
     516  }
     517}
     518// Return 0 if added, 1 if not, -1 if not added because of space
     519int
     520CbcRowCuts::addCutIfNotDuplicateWhenGreedy(const OsiRowCut & cut,int whichType)
     521{
     522  int hashSize= size_*hashMultiplier_;
     523  if (numberCuts_==size_) {
     524    size_ = 2*size_+100;
     525    hashSize=hashMultiplier_*size_;
     526    OsiRowCut2 ** temp = new  OsiRowCut2 * [size_];
     527    delete [] hash_;
     528    hash_ = new CoinHashLink[hashSize];
     529    for (int i=0;i<hashSize;i++) {
     530      hash_[i].index=-1;
     531      hash_[i].next=-1;
     532    }
     533    for (int i=0;i<numberCuts_;i++) {
     534      temp[i]=rowCut_[i];
     535      int ipos = hashCut2(*temp[i],hashSize);
     536      int found = -1;
     537      int jpos=ipos;
     538      while ( true ) {
     539        int j1 = hash_[ipos].index;
     540       
     541        if ( j1 >= 0 ) {
     542          if ( !same2(*temp[i],*temp[j1]) ) {
     543            int k = hash_[ipos].next;
     544            if ( k != -1 )
     545              ipos = k;
     546            else
     547              break;
     548          } else {
     549            found = j1;
     550            break;
     551          }
     552        } else {
     553          break;
     554        }
     555      }
     556      if (found<0) {
     557        assert (hash_[ipos].next==-1);
     558        if (ipos==jpos) {
     559          // first
     560          hash_[ipos].index=i;
     561        } else {
     562          // find next space
     563          while ( true ) {
     564            ++lastHash_;
     565            assert (lastHash_<hashSize);
     566            if ( hash_[lastHash_].index == -1 )
     567              break;
     568          }
     569          hash_[ipos].next = lastHash_;
     570          hash_[lastHash_].index = i;
     571        }
     572      }
     573    }
     574    delete [] rowCut_;
     575    rowCut_ = temp;
     576  }
     577  if (numberCuts_<size_) {
     578    double newLb = cut.lb();
     579    double newUb = cut.ub();
     580    CoinPackedVector vector = cut.row();
     581    int numberElements =vector.getNumElements();
     582    int * newIndices = vector.getIndices();
     583    double * newElements = vector.getElements();
     584    CoinSort_2(newIndices,newIndices+numberElements,newElements);
     585    int i;
     586    bool bad=false;
     587    for (i=0;i<numberElements;i++) {
     588      double value = fabs(newElements[i]);
     589      if (value<1.0e-12||value>1.0e12)
     590        bad=true;
     591    }
     592    if (bad)
     593      return 1;
     594    OsiRowCut2 newCut(whichType);
     595    newCut.setLb(newLb);
     596    newCut.setUb(newUb);
     597    newCut.setRow(vector);
     598    int ipos = hashCut2(newCut,hashSize);
     599    int found = -1;
     600    int jpos=ipos;
     601    while ( true ) {
     602      int j1 = hash_[ipos].index;
     603     
     604      if ( j1 >= 0 ) {
     605        if ( !same2(newCut,*rowCut_[j1]) ) {
     606          int k = hash_[ipos].next;
     607          if ( k != -1 )
     608            ipos = k;
     609          else
     610            break;
     611        } else {
     612          found = j1;
     613          break;
     614        }
     615      } else {
     616        break;
     617      }
     618    }
     619    if (found<0) {
     620      assert (hash_[ipos].next==-1);
     621      if (ipos==jpos) {
     622        // first
     623        hash_[ipos].index=numberCuts_;
     624      } else {
     625        // find next space
     626        while ( true ) {
     627          ++lastHash_;
     628          assert (lastHash_<hashSize);
     629          if ( hash_[lastHash_].index == -1 )
     630            break;
     631        }
     632        hash_[ipos].next = lastHash_;
     633        hash_[lastHash_].index = numberCuts_;
     634      }
     635      OsiRowCut2 * newCutPtr = new OsiRowCut2(whichType);
     636      newCutPtr->setLb(newLb);
     637      newCutPtr->setUb(newUb);
     638      newCutPtr->setRow(vector);
     639      rowCut_[numberCuts_++]=newCutPtr;
     640      return 0;
     641    } else {
     642      return 1;
     643    }
     644  } else {
     645    return -1;
     646  }
     647}
     648// Add in cuts as normal cuts and delete
     649void
     650CbcRowCuts::addCuts(OsiCuts & cs)
     651{
     652  for (int i=0;i<numberCuts_;i++) {
     653    cs.insert(*rowCut_[i]);
     654    delete rowCut_[i] ;
     655    rowCut_[i] = NULL ;
     656  }
     657  numberCuts_=0;
     658}
Note: See TracChangeset for help on using the changeset viewer.