Clp trunk
|
00001 /* $Id$ */ 00002 // Copyright (C) 2002, International Business Machines 00003 // Corporation and others. All Rights Reserved. 00004 // This code is licensed under the terms of the Eclipse Public License (EPL). 00005 00006 #ifndef ClpPackedMatrix_H 00007 #define ClpPackedMatrix_H 00008 00009 #include "CoinPragma.hpp" 00010 00011 #include "ClpMatrixBase.hpp" 00012 00013 // Compilers can produce better code if they know about __restrict 00014 #ifndef COIN_RESTRICT 00015 #ifdef COIN_USE_RESTRICT 00016 #define COIN_RESTRICT __restrict 00017 #else 00018 #define COIN_RESTRICT 00019 #endif 00020 #endif 00021 00028 class ClpPackedMatrix2; 00029 class ClpPackedMatrix3; 00030 class ClpPackedMatrix : public ClpMatrixBase { 00031 00032 public: 00035 00036 virtual CoinPackedMatrix * getPackedMatrix() const { 00037 return matrix_; 00038 } 00040 virtual bool isColOrdered() const { 00041 return matrix_->isColOrdered(); 00042 } 00044 virtual CoinBigIndex getNumElements() const { 00045 return matrix_->getNumElements(); 00046 } 00048 virtual int getNumCols() const { 00049 return matrix_->getNumCols(); 00050 } 00052 virtual int getNumRows() const { 00053 return matrix_->getNumRows(); 00054 } 00055 00060 virtual const double * getElements() const { 00061 return matrix_->getElements(); 00062 } 00064 inline double * getMutableElements() const { 00065 return matrix_->getMutableElements(); 00066 } 00072 virtual const int * getIndices() const { 00073 return matrix_->getIndices(); 00074 } 00075 00076 virtual const CoinBigIndex * getVectorStarts() const { 00077 return matrix_->getVectorStarts(); 00078 } 00080 virtual const int * getVectorLengths() const { 00081 return matrix_->getVectorLengths(); 00082 } 00084 virtual int getVectorLength(int index) const { 00085 return matrix_->getVectorSize(index); 00086 } 00087 00089 virtual void deleteCols(const int numDel, const int * indDel); 00091 virtual void deleteRows(const int numDel, const int * indDel); 00092 #ifndef CLP_NO_VECTOR 00093 00094 virtual void appendCols(int number, const CoinPackedVectorBase * const * columns); 00096 virtual void appendRows(int number, const CoinPackedVectorBase * const * rows); 00097 #endif 00098 00102 virtual int appendMatrix(int number, int type, 00103 const CoinBigIndex * starts, const int * index, 00104 const double * element, int numberOther = -1); 00109 virtual void replaceVector(const int index, 00110 const int numReplace, const double * newElements) { 00111 matrix_->replaceVector(index, numReplace, newElements); 00112 } 00116 virtual void modifyCoefficient(int row, int column, double newElement, 00117 bool keepZero = false) { 00118 matrix_->modifyCoefficient(row, column, newElement, keepZero); 00119 } 00121 virtual ClpMatrixBase * reverseOrderedCopy() const; 00123 virtual CoinBigIndex countBasis(const int * whichColumn, 00124 int & numberColumnBasic); 00126 virtual void fillBasis(ClpSimplex * model, 00127 const int * whichColumn, 00128 int & numberColumnBasic, 00129 int * row, int * start, 00130 int * rowCount, int * columnCount, 00131 CoinFactorizationDouble * element); 00134 virtual int scale(ClpModel * model, const ClpSimplex * baseModel = NULL) const ; 00137 virtual void scaleRowCopy(ClpModel * model) const ; 00139 void createScaledMatrix(ClpSimplex * model) const; 00143 virtual ClpMatrixBase * scaledColumnCopy(ClpModel * model) const ; 00154 virtual bool allElementsInRange(ClpModel * model, 00155 double smallest, double largest, 00156 int check = 15); 00160 virtual void rangeOfElements(double & smallestNegative, double & largestNegative, 00161 double & smallestPositive, double & largestPositive); 00162 00165 virtual void unpack(const ClpSimplex * model, CoinIndexedVector * rowArray, 00166 int column) const ; 00171 virtual void unpackPacked(ClpSimplex * model, 00172 CoinIndexedVector * rowArray, 00173 int column) const; 00176 virtual void add(const ClpSimplex * model, CoinIndexedVector * rowArray, 00177 int column, double multiplier) const ; 00179 virtual void add(const ClpSimplex * model, double * array, 00180 int column, double multiplier) const; 00182 virtual void releasePackedMatrix() const { } 00187 virtual CoinBigIndex * dubiousWeights(const ClpSimplex * model, int * inputWeights) const; 00189 virtual bool canDoPartialPricing() const; 00191 virtual void partialPricing(ClpSimplex * model, double start, double end, 00192 int & bestSequence, int & numberWanted); 00194 virtual int refresh(ClpSimplex * model); 00195 // Really scale matrix 00196 virtual void reallyScale(const double * rowScale, const double * columnScale); 00202 virtual void setDimensions(int numrows, int numcols); 00204 00210 virtual void times(double scalar, 00211 const double * x, double * y) const; 00213 virtual void times(double scalar, 00214 const double * x, double * y, 00215 const double * rowScale, 00216 const double * columnScale) const; 00220 virtual void transposeTimes(double scalar, 00221 const double * x, double * y) const; 00223 virtual void transposeTimes(double scalar, 00224 const double * x, double * y, 00225 const double * rowScale, 00226 const double * columnScale, 00227 double * spare = NULL) const; 00232 void transposeTimesSubset( int number, 00233 const int * which, 00234 const double * pi, double * y, 00235 const double * rowScale, 00236 const double * columnScale, 00237 double * spare = NULL) const; 00242 virtual void transposeTimes(const ClpSimplex * model, double scalar, 00243 const CoinIndexedVector * x, 00244 CoinIndexedVector * y, 00245 CoinIndexedVector * z) const; 00250 void transposeTimesByColumn(const ClpSimplex * model, double scalar, 00251 const CoinIndexedVector * x, 00252 CoinIndexedVector * y, 00253 CoinIndexedVector * z) const; 00259 virtual void transposeTimesByRow(const ClpSimplex * model, double scalar, 00260 const CoinIndexedVector * x, 00261 CoinIndexedVector * y, 00262 CoinIndexedVector * z) const; 00266 virtual void subsetTransposeTimes(const ClpSimplex * model, 00267 const CoinIndexedVector * x, 00268 const CoinIndexedVector * y, 00269 CoinIndexedVector * z) const; 00272 virtual bool canCombine(const ClpSimplex * model, 00273 const CoinIndexedVector * pi) const; 00275 virtual void transposeTimes2(const ClpSimplex * model, 00276 const CoinIndexedVector * pi1, CoinIndexedVector * dj1, 00277 const CoinIndexedVector * pi2, 00278 CoinIndexedVector * spare, 00279 double referenceIn, double devex, 00280 // Array for exact devex to say what is in reference framework 00281 unsigned int * reference, 00282 double * weights, double scaleFactor); 00284 virtual void subsetTimes2(const ClpSimplex * model, 00285 CoinIndexedVector * dj1, 00286 const CoinIndexedVector * pi2, CoinIndexedVector * dj2, 00287 double referenceIn, double devex, 00288 // Array for exact devex to say what is in reference framework 00289 unsigned int * reference, 00290 double * weights, double scaleFactor); 00292 void useEffectiveRhs(ClpSimplex * model); 00293 #if COIN_LONG_WORK 00294 // For long double versions 00295 virtual void times(CoinWorkDouble scalar, 00296 const CoinWorkDouble * x, CoinWorkDouble * y) const ; 00297 virtual void transposeTimes(CoinWorkDouble scalar, 00298 const CoinWorkDouble * x, CoinWorkDouble * y) const ; 00299 #endif 00300 00301 00304 00305 inline CoinPackedMatrix * matrix() const { 00306 return matrix_; 00307 } 00311 inline void setMatrixNull() { 00312 matrix_ = NULL; 00313 } 00315 inline void makeSpecialColumnCopy() { 00316 flags_ |= 16; 00317 } 00319 void releaseSpecialColumnCopy(); 00321 inline bool zeros() const { 00322 return ((flags_ & 1) != 0); 00323 } 00325 inline bool wantsSpecialColumnCopy() const { 00326 return ((flags_ & 16) != 0); 00327 } 00329 inline int flags() const { 00330 return flags_; 00331 } 00333 inline void checkGaps() { 00334 flags_ = (matrix_->hasGaps()) ? (flags_ | 2) : (flags_ & (~2)); 00335 } 00337 00338 00342 ClpPackedMatrix(); 00344 virtual ~ClpPackedMatrix(); 00346 00350 ClpPackedMatrix(const ClpPackedMatrix&); 00352 ClpPackedMatrix(const CoinPackedMatrix&); 00355 ClpPackedMatrix (const ClpPackedMatrix & wholeModel, 00356 int numberRows, const int * whichRows, 00357 int numberColumns, const int * whichColumns); 00358 ClpPackedMatrix (const CoinPackedMatrix & wholeModel, 00359 int numberRows, const int * whichRows, 00360 int numberColumns, const int * whichColumns); 00361 00363 ClpPackedMatrix(CoinPackedMatrix * matrix); 00364 00365 ClpPackedMatrix& operator=(const ClpPackedMatrix&); 00367 virtual ClpMatrixBase * clone() const ; 00369 virtual void copy(const ClpPackedMatrix * from); 00372 virtual ClpMatrixBase * subsetClone ( 00373 int numberRows, const int * whichRows, 00374 int numberColumns, const int * whichColumns) const ; 00376 void specialRowCopy(ClpSimplex * model, const ClpMatrixBase * rowCopy); 00378 void specialColumnCopy(ClpSimplex * model); 00380 virtual void correctSequence(const ClpSimplex * model, int & sequenceIn, int & sequenceOut) ; 00382 private: 00384 int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi, 00385 int * COIN_RESTRICT index, 00386 double * COIN_RESTRICT array, 00387 const double tolerance) const; 00389 int gutsOfTransposeTimesScaled(const double * COIN_RESTRICT pi, 00390 const double * COIN_RESTRICT columnScale, 00391 int * COIN_RESTRICT index, 00392 double * COIN_RESTRICT array, 00393 const double tolerance) const; 00395 int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi, 00396 int * COIN_RESTRICT index, 00397 double * COIN_RESTRICT array, 00398 const unsigned char * status, 00399 const double tolerance) const; 00402 int gutsOfTransposeTimesUnscaled(const double * COIN_RESTRICT pi, 00403 int * COIN_RESTRICT index, 00404 double * COIN_RESTRICT array, 00405 const unsigned char * status, 00406 int * COIN_RESTRICT spareIndex, 00407 double * COIN_RESTRICT spareArray, 00408 const double * COIN_RESTRICT reducedCost, 00409 double & upperTheta, 00410 double & bestPossible, 00411 double acceptablePivot, 00412 double dualTolerance, 00413 int & numberRemaining, 00414 const double zeroTolerance) const; 00416 int gutsOfTransposeTimesScaled(const double * COIN_RESTRICT pi, 00417 const double * COIN_RESTRICT columnScale, 00418 int * COIN_RESTRICT index, 00419 double * COIN_RESTRICT array, 00420 const unsigned char * status, 00421 const double tolerance) const; 00423 int gutsOfTransposeTimesByRowGEK(const CoinIndexedVector * COIN_RESTRICT piVector, 00424 int * COIN_RESTRICT index, 00425 double * COIN_RESTRICT output, 00426 int numberColumns, 00427 const double tolerance, 00428 const double scalar) const; 00430 int gutsOfTransposeTimesByRowGE3(const CoinIndexedVector * COIN_RESTRICT piVector, 00431 int * COIN_RESTRICT index, 00432 double * COIN_RESTRICT output, 00433 double * COIN_RESTRICT array2, 00434 const double tolerance, 00435 const double scalar) const; 00437 int gutsOfTransposeTimesByRowGE3a(const CoinIndexedVector * COIN_RESTRICT piVector, 00438 int * COIN_RESTRICT index, 00439 double * COIN_RESTRICT output, 00440 int * COIN_RESTRICT lookup, 00441 char * COIN_RESTRICT marked, 00442 const double tolerance, 00443 const double scalar) const; 00445 void gutsOfTransposeTimesByRowEQ2(const CoinIndexedVector * piVector, CoinIndexedVector * output, 00446 CoinIndexedVector * spareVector, const double tolerance, const double scalar) const; 00448 void gutsOfTransposeTimesByRowEQ1(const CoinIndexedVector * piVector, CoinIndexedVector * output, 00449 const double tolerance, const double scalar) const; 00451 void clearCopies(); 00452 00453 00454 protected: 00456 void checkFlags(int type) const; 00460 00461 CoinPackedMatrix * matrix_; 00463 int numberActiveColumns_; 00471 int flags_; 00473 ClpPackedMatrix2 * rowCopy_; 00475 ClpPackedMatrix3 * columnCopy_; 00477 }; 00478 #ifdef THREAD 00479 #include <pthread.h> 00480 typedef struct { 00481 double acceptablePivot; 00482 const ClpSimplex * model; 00483 double * spare; 00484 int * spareIndex; 00485 double * arrayTemp; 00486 int * indexTemp; 00487 int * numberInPtr; 00488 double * bestPossiblePtr; 00489 double * upperThetaPtr; 00490 int * posFreePtr; 00491 double * freePivotPtr; 00492 int * numberOutPtr; 00493 const unsigned short * count; 00494 const double * pi; 00495 const CoinBigIndex * rowStart; 00496 const double * element; 00497 const unsigned short * column; 00498 int offset; 00499 int numberInRowArray; 00500 int numberLook; 00501 } dualColumn0Struct; 00502 #endif 00503 class ClpPackedMatrix2 { 00504 00505 public: 00511 void transposeTimes(const ClpSimplex * model, 00512 const CoinPackedMatrix * rowCopy, 00513 const CoinIndexedVector * x, 00514 CoinIndexedVector * spareArray, 00515 CoinIndexedVector * z) const; 00517 inline bool usefulInfo() const { 00518 return rowStart_ != NULL; 00519 } 00521 00522 00526 ClpPackedMatrix2(); 00528 ClpPackedMatrix2(ClpSimplex * model, const CoinPackedMatrix * rowCopy); 00530 virtual ~ClpPackedMatrix2(); 00532 00536 ClpPackedMatrix2(const ClpPackedMatrix2&); 00537 ClpPackedMatrix2& operator=(const ClpPackedMatrix2&); 00539 00540 00541 protected: 00545 00546 int numberBlocks_; 00548 int numberRows_; 00550 int * offset_; 00552 mutable unsigned short * count_; 00554 mutable CoinBigIndex * rowStart_; 00556 unsigned short * column_; 00558 double * work_; 00559 #ifdef THREAD 00560 pthread_t * threadId_; 00561 dualColumn0Struct * info_; 00562 #endif 00563 00564 }; 00565 typedef struct { 00566 CoinBigIndex startElements_; // point to data 00567 int startIndices_; // point to column_ 00568 int numberInBlock_; 00569 int numberPrice_; // at beginning 00570 int numberElements_; // number elements per column 00571 } blockStruct; 00572 class ClpPackedMatrix3 { 00573 00574 public: 00580 void transposeTimes(const ClpSimplex * model, 00581 const double * pi, 00582 CoinIndexedVector * output) const; 00584 void transposeTimes2(const ClpSimplex * model, 00585 const double * pi, CoinIndexedVector * dj1, 00586 const double * piWeight, 00587 double referenceIn, double devex, 00588 // Array for exact devex to say what is in reference framework 00589 unsigned int * reference, 00590 double * weights, double scaleFactor); 00592 00593 00597 ClpPackedMatrix3(); 00599 ClpPackedMatrix3(ClpSimplex * model, const CoinPackedMatrix * columnCopy); 00601 virtual ~ClpPackedMatrix3(); 00603 00607 ClpPackedMatrix3(const ClpPackedMatrix3&); 00608 ClpPackedMatrix3& operator=(const ClpPackedMatrix3&); 00610 00613 void sortBlocks(const ClpSimplex * model); 00615 void swapOne(const ClpSimplex * model, const ClpPackedMatrix * matrix, 00616 int iColumn); 00618 00619 00620 protected: 00624 00625 int numberBlocks_; 00627 int numberColumns_; 00629 int * column_; 00631 CoinBigIndex * start_; 00633 int * row_; 00635 double * element_; 00637 blockStruct * block_; 00639 }; 00640 00641 #endif