00001
00002
00003 #if defined(_MSC_VER)
00004
00005 # pragma warning(disable:4786)
00006 #endif
00007
00008 #include <cassert>
00009
00010 #include "CoinWarmStartBasis.hpp"
00011 #include <cmath>
00012 #include <iostream>
00013
00014
00015
00016 void
00017 CoinWarmStartBasis::setSize(int ns, int na) {
00018 delete[] structuralStatus_;
00019 delete[] artificialStatus_;
00020
00021 int nint = (ns+15) >> 4;
00022 structuralStatus_ = new char[4*nint];
00023
00024 memset (structuralStatus_, 0, (4*nint) * sizeof(char));
00025 nint = (na+15) >> 4;
00026 artificialStatus_ = new char[4*nint];
00027 memset (artificialStatus_, 0, (4*nint) * sizeof(char));
00028 numArtificial_ = na;
00029 numStructural_ = ns;
00030 }
00031
00032 void
00033 CoinWarmStartBasis::assignBasisStatus(int ns, int na, char*& sStat,
00034 char*& aStat) {
00035 delete[] structuralStatus_;
00036 delete[] artificialStatus_;
00037 numStructural_ = ns;
00038 numArtificial_ = na;
00039 structuralStatus_ = sStat;
00040 artificialStatus_ = aStat;
00041 sStat = NULL;
00042 aStat = NULL;
00043 }
00044 CoinWarmStartBasis::CoinWarmStartBasis(int ns, int na,
00045 const char* sStat, const char* aStat) :
00046 numStructural_(ns), numArtificial_(na),
00047 structuralStatus_(NULL), artificialStatus_(NULL) {
00048
00049 int nint = (ns+15) >> 4;
00050 structuralStatus_ = new char[4*nint];
00051 structuralStatus_[4*nint-3]=0;
00052 structuralStatus_[4*nint-2]=0;
00053 structuralStatus_[4*nint-1]=0;
00054 memcpy (structuralStatus_, sStat, ((ns + 3) / 4) * sizeof(char));
00055 nint = (na+15) >> 4;
00056 artificialStatus_ = new char[4*nint];
00057 artificialStatus_[4*nint-3]=0;
00058 artificialStatus_[4*nint-2]=0;
00059 artificialStatus_[4*nint-1]=0;
00060 memcpy (artificialStatus_, aStat, ((na + 3) / 4) * sizeof(char));
00061 }
00062
00063 CoinWarmStartBasis::CoinWarmStartBasis(const CoinWarmStartBasis& ws) :
00064 numStructural_(ws.numStructural_), numArtificial_(ws.numArtificial_),
00065 structuralStatus_(NULL), artificialStatus_(NULL) {
00066
00067 int nint = (numStructural_+15) >> 4;
00068 structuralStatus_ = new char[4*nint];
00069 memcpy (structuralStatus_, ws.structuralStatus_,
00070 (4*nint) * sizeof(char));
00071 nint = (numArtificial_+15) >> 4;
00072 artificialStatus_ = new char[4*nint];
00073 memcpy (artificialStatus_, ws.artificialStatus_,
00074 (4*nint) * sizeof(char));
00075 }
00076
00077 CoinWarmStartBasis&
00078 CoinWarmStartBasis::operator=(const CoinWarmStartBasis& rhs)
00079 {
00080 if (this != &rhs) {
00081 numStructural_=rhs.numStructural_;
00082 numArtificial_=rhs.numArtificial_;
00083 delete [] structuralStatus_;
00084 delete [] artificialStatus_;
00085
00086 int nint = (numStructural_+15) >> 4;
00087 structuralStatus_ = new char[4*nint];
00088 memcpy (structuralStatus_, rhs.structuralStatus_,
00089 (4*nint) * sizeof(char));
00090 nint = (numArtificial_+15) >> 4;
00091 artificialStatus_ = new char[4*nint];
00092 memcpy (artificialStatus_, rhs.artificialStatus_,
00093 (4*nint) * sizeof(char));
00094 }
00095 return *this;
00096 }
00097
00098
00099 void
00100 CoinWarmStartBasis::resize (int newNumberRows, int newNumberColumns)
00101 {
00102 char * array;
00103 int i , nCharNew, nCharOld;
00104 if (newNumberRows!=numArtificial_) {
00105 nCharOld = 4*((numArtificial_+15)>>4);
00106 nCharNew = 4*((newNumberRows+15)>>4);
00107 array = new char[nCharNew];
00108
00109 memset(array,0,nCharNew*sizeof(char));
00110 memcpy(array,artificialStatus_,(nCharOld>nCharNew)?nCharNew:nCharOld);
00111 delete [] artificialStatus_;
00112 artificialStatus_ = array;
00113 for (i=numArtificial_;i<newNumberRows;i++)
00114 setArtifStatus(i, basic);
00115 numArtificial_ = newNumberRows;
00116 }
00117 if (newNumberColumns!=numStructural_) {
00118 nCharOld = 4*((numStructural_+15)>>4);
00119 nCharNew = 4*((newNumberColumns+15)>>4);
00120 array = new char[nCharNew];
00121
00122 memset(array,0,nCharNew*sizeof(char));
00123 memcpy(array,structuralStatus_,(nCharOld>nCharNew)?nCharNew:nCharOld);
00124 delete [] structuralStatus_;
00125 structuralStatus_ = array;
00126 for (i=numStructural_;i<newNumberColumns;i++)
00127 setStructStatus(i, atLowerBound);
00128 numStructural_ = newNumberColumns;
00129 }
00130 }
00131
00132 void
00133 CoinWarmStartBasis::deleteRows(int number, const int * which)
00134 {
00135 int i ;
00136 char * deleted = new char[numArtificial_];
00137 int numberDeleted=0;
00138 memset(deleted,0,numArtificial_*sizeof(char));
00139 for (i=0;i<number;i++) {
00140 int j = which[i];
00141 if (j>=0&&j<numArtificial_&&!deleted[j]) {
00142 numberDeleted++;
00143 deleted[j]=1;
00144 }
00145 }
00146 int nCharNew = 4*((numArtificial_-numberDeleted+15)>>4);
00147 char * array = new char[nCharNew];
00148
00149 array[nCharNew-3]=0;
00150 array[nCharNew-2]=0;
00151 array[nCharNew-1]=0;
00152 int put=0;
00153 # ifdef COIN_DEBUG
00154 int numberNotBasic=0;
00155 # endif
00156 for (i=0;i<numArtificial_;i++) {
00157 Status status = getArtifStatus(i);
00158 if (!deleted[i]) {
00159 setStatus(array,put,status) ;
00160 put++; }
00161 # ifdef COIN_DEBUG
00162 else
00163 if (status!=CoinWarmStartBasis::basic)
00164 { numberNotBasic++ ; }
00165 # endif
00166 }
00167 delete [] artificialStatus_;
00168 artificialStatus_ = array;
00169 delete [] deleted;
00170 numArtificial_ -= numberDeleted;
00171 # ifdef COIN_DEBUG
00172 if (numberNotBasic)
00173 std::cout<<numberNotBasic<<" non basic artificials deleted"<<std::endl;
00174 # endif
00175 }
00176
00177
00178 void
00179 CoinWarmStartBasis::deleteColumns(int number, const int * which)
00180 {
00181 int i ;
00182 char * deleted = new char[numStructural_];
00183 int numberDeleted=0;
00184 memset(deleted,0,numStructural_*sizeof(char));
00185 for (i=0;i<number;i++) {
00186 int j = which[i];
00187 if (j>=0&&j<numStructural_&&!deleted[j]) {
00188 numberDeleted++;
00189 deleted[j]=1;
00190 }
00191 }
00192 int nCharNew = 4*((numStructural_-numberDeleted+15)>>4);
00193 char * array = new char[nCharNew];
00194
00195 array[nCharNew-3]=0;
00196 array[nCharNew-2]=0;
00197 array[nCharNew-1]=0;
00198 int put=0;
00199 # ifdef COIN_DEBUG
00200 int numberBasic=0;
00201 # endif
00202 for (i=0;i<numStructural_;i++) {
00203 Status status = getStructStatus(i);
00204 if (!deleted[i]) {
00205 setStatus(array,put,status) ;
00206 put++; }
00207 # ifdef COIN_DEBUG
00208 else
00209 if (status==CoinWarmStartBasis::basic)
00210 { numberBasic++ ; }
00211 # endif
00212 }
00213 delete [] structuralStatus_;
00214 structuralStatus_ = array;
00215 delete [] deleted;
00216 numStructural_ -= numberDeleted;
00217 #ifdef COIN_DEBUG
00218 if (numberBasic)
00219 std::cout<<numberBasic<<" basic structurals deleted"<<std::endl;
00220 #endif
00221 }
00222
00223 void
00224 CoinWarmStartBasis::print() const
00225 {
00226 std::cout<<"Basis "<<this<<" has "<<numArtificial_<<" rows and "
00227 <<numStructural_<<" columns"<<std::endl;
00228 std::cout<<"Rows:"<<std::endl;
00229 int i;
00230 char type[]={'F','B','U','L'};
00231
00232 for (i=0;i<numArtificial_;i++)
00233 std::cout<<type[getArtifStatus(i)];
00234 std::cout<<std::endl;
00235 std::cout<<"Columns:"<<std::endl;
00236
00237 for (i=0;i<numStructural_;i++)
00238 std::cout<<type[getStructStatus(i)];
00239 std::cout<<std::endl;
00240 }
00241 CoinWarmStartBasis::CoinWarmStartBasis()
00242 {
00243
00244 numStructural_ = 0;
00245 numArtificial_ = 0;
00246 structuralStatus_ = NULL;
00247 artificialStatus_ = NULL;
00248 }
00249 CoinWarmStartBasis::~CoinWarmStartBasis()
00250 {
00251 delete[] structuralStatus_;
00252 delete[] artificialStatus_;
00253 }
00254
00255 int
00256 CoinWarmStartBasis::numberBasicStructurals()
00257 {
00258 int i ;
00259 int numberBasic=0;
00260 for (i=0;i<numStructural_;i++) {
00261 Status status = getStructStatus(i);
00262 if (status==CoinWarmStartBasis::basic)
00263 numberBasic++;
00264 }
00265 return numberBasic;
00266 }
00267
00268
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278 CoinWarmStartDiff*
00279 CoinWarmStartBasis::generateDiff (const CoinWarmStart *const oldCWS) const
00280 {
00281
00282
00283
00284 const CoinWarmStartBasis *oldBasis =
00285 dynamic_cast<const CoinWarmStartBasis *>(oldCWS) ;
00286 if (!oldBasis)
00287 { throw CoinError("Old basis not derived from CoinWarmStartBasis.",
00288 "generateDiff","CoinWarmStartBasis") ; }
00289 const CoinWarmStartBasis *newBasis = this ;
00290
00291
00292
00293
00294 const int oldArtifCnt = oldBasis->getNumArtificial() ;
00295 const int oldStructCnt = oldBasis->getNumStructural() ;
00296 const int newArtifCnt = newBasis->getNumArtificial() ;
00297 const int newStructCnt = newBasis->getNumStructural() ;
00298
00299 assert(newArtifCnt >= oldArtifCnt) ;
00300 assert(newStructCnt >= oldStructCnt) ;
00301
00302 int sizeOldArtif = (oldArtifCnt+15)>>4 ;
00303 int sizeNewArtif = (newArtifCnt+15)>>4 ;
00304 int sizeOldStruct = (oldStructCnt+15)>>4 ;
00305 int sizeNewStruct = (newStructCnt+15)>>4 ;
00306 int maxBasisLength = sizeNewArtif+sizeNewStruct ;
00307
00308 unsigned int *diffNdx = new unsigned int [maxBasisLength];
00309 unsigned int *diffVal = new unsigned int [maxBasisLength];
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322 const unsigned int *oldStatus =
00323 reinterpret_cast<const unsigned int *>(oldBasis->getArtificialStatus()) ;
00324 const unsigned int *newStatus =
00325 reinterpret_cast<const unsigned int *>(newBasis->getArtificialStatus()) ;
00326 int numberChanged = 0 ;
00327 int i ;
00328 for (i = 0 ; i < sizeOldArtif ; i++)
00329 { if (oldStatus[i] != newStatus[i])
00330 { diffNdx[numberChanged] = i|0x80000000 ;
00331 diffVal[numberChanged++] = newStatus[i] ; } }
00332 for ( ; i < sizeNewArtif ; i++)
00333 { diffNdx[numberChanged] = i|0x80000000 ;
00334 diffVal[numberChanged++] = newStatus[i] ; }
00335
00336
00337
00338 oldStatus =
00339 reinterpret_cast<const unsigned int *>(oldBasis->getStructuralStatus()) ;
00340 newStatus =
00341 reinterpret_cast<const unsigned int *>(newBasis->getStructuralStatus()) ;
00342 for (i = 0 ; i < sizeOldStruct ; i++)
00343 { if (oldStatus[i] != newStatus[i])
00344 { diffNdx[numberChanged] = i ;
00345 diffVal[numberChanged++] = newStatus[i] ; } }
00346 for ( ; i < sizeNewStruct ; i++)
00347 { diffNdx[numberChanged] = i ;
00348 diffVal[numberChanged++] = newStatus[i] ; }
00349
00350
00351
00352 CoinWarmStartBasisDiff *diff =
00353 new CoinWarmStartBasisDiff(numberChanged,diffNdx,diffVal) ;
00354
00355
00356
00357 delete[] diffNdx ;
00358 delete[] diffVal ;
00359
00360 return (dynamic_cast<CoinWarmStartDiff *>(diff)) ; }
00361
00362
00363
00364
00365
00366
00367 void CoinWarmStartBasis::applyDiff (const CoinWarmStartDiff *const cwsdDiff)
00368 {
00369
00370
00371
00372 const CoinWarmStartBasisDiff *diff =
00373 dynamic_cast<const CoinWarmStartBasisDiff *>(cwsdDiff) ;
00374 if (!diff)
00375 { throw CoinError("Diff not derived from CoinWarmStartBasisDiff.",
00376 "applyDiff","CoinWarmStartBasis") ; }
00377
00378
00379
00380
00381 const int numberChanges = diff->sze_ ;
00382 const unsigned int *diffNdxs = diff->diffNdxs_ ;
00383 const unsigned int *diffVals = diff->diffVals_ ;
00384 unsigned int *structStatus =
00385 reinterpret_cast<unsigned int *>(this->getStructuralStatus()) ;
00386 unsigned int *artifStatus =
00387 reinterpret_cast<unsigned int *>(this->getArtificialStatus()) ;
00388
00389 for (int i = 0 ; i < numberChanges ; i++)
00390 { unsigned int diffNdx = diffNdxs[i] ;
00391 unsigned int diffVal = diffVals[i] ;
00392 if ((diffNdx&0x80000000) == 0)
00393 { structStatus[diffNdx] = diffVal ; }
00394 else
00395 { artifStatus[diffNdx&0x7fffffff] = diffVal ; } }
00396
00397 return ; }
00398
00399
00400
00401
00402
00403
00404
00405
00406 CoinWarmStartBasisDiff::CoinWarmStartBasisDiff (int sze,
00407 const unsigned int *const diffNdxs, const unsigned int *const diffVals)
00408 : sze_(sze),
00409 diffNdxs_(0),
00410 diffVals_(0)
00411
00412 { if (sze > 0)
00413 { diffNdxs_ = new unsigned int[sze] ;
00414 memcpy(diffNdxs_,diffNdxs,sze*sizeof(unsigned int)) ;
00415 diffVals_ = new unsigned int[sze] ;
00416 memcpy(diffVals_,diffVals,sze*sizeof(unsigned int)) ; }
00417
00418 return ; }
00419
00420
00421
00422
00423
00424 CoinWarmStartBasisDiff::CoinWarmStartBasisDiff
00425 (const CoinWarmStartBasisDiff &rhs)
00426 : sze_(rhs.sze_),
00427 diffNdxs_(0),
00428 diffVals_(0)
00429 { if (sze_ > 0)
00430 { diffNdxs_ = new unsigned int[sze_] ;
00431 memcpy(diffNdxs_,rhs.diffNdxs_,sze_*sizeof(unsigned int)) ;
00432 diffVals_ = new unsigned int[sze_] ;
00433 memcpy(diffVals_,rhs.diffVals_,sze_*sizeof(unsigned int)) ; }
00434
00435 return ; }
00436
00437
00438
00439
00440
00441 CoinWarmStartBasisDiff&
00442 CoinWarmStartBasisDiff::operator= (const CoinWarmStartBasisDiff &rhs)
00443
00444 { if (this != &rhs)
00445 { if (sze_ > 0)
00446 { delete[] diffNdxs_ ;
00447 delete[] diffVals_ ; }
00448 sze_ = rhs.sze_ ;
00449 if (sze_ > 0)
00450 { diffNdxs_ = new unsigned int[sze_] ;
00451 memcpy(diffNdxs_,rhs.diffNdxs_,sze_*sizeof(unsigned int)) ;
00452 diffVals_ = new unsigned int[sze_] ;
00453 memcpy(diffVals_,rhs.diffVals_,sze_*sizeof(unsigned int)) ; }
00454 else
00455 { diffNdxs_ = 0 ;
00456 diffVals_ = 0 ; } }
00457
00458 return (*this) ; }
00459