CoinUtils
trunk
|
00001 /* $Id$ */ 00002 // Copyright (C) 2008, 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 /* 00007 This is a simple factorization of the LP Basis 00008 */ 00009 #ifndef CoinSimpFactorization_H 00010 #define CoinSimpFactorization_H 00011 00012 #include <iostream> 00013 #include <string> 00014 #include <cassert> 00015 #include "CoinTypes.hpp" 00016 #include "CoinIndexedVector.hpp" 00017 #include "CoinDenseFactorization.hpp" 00018 class CoinPackedMatrix; 00019 00020 00022 class FactorPointers{ 00023 public: 00024 double *rowMax; 00025 int *firstRowKnonzeros; 00026 int *prevRow; 00027 int *nextRow; 00028 int *firstColKnonzeros; 00029 int *prevColumn; 00030 int *nextColumn; 00031 int *newCols; 00032 //constructor 00033 FactorPointers( int numRows, int numCols, int *UrowLengths_, int *UcolLengths_ ); 00034 // destructor 00035 ~ FactorPointers(); 00036 }; 00037 00038 class CoinSimpFactorization : public CoinOtherFactorization { 00039 friend void CoinSimpFactorizationUnitTest( const std::string & mpsDir ); 00040 00041 public: 00042 00045 00046 CoinSimpFactorization ( ); 00048 CoinSimpFactorization ( const CoinSimpFactorization &other); 00049 00051 virtual ~CoinSimpFactorization ( ); 00053 CoinSimpFactorization & operator = ( const CoinSimpFactorization & other ); 00055 virtual CoinOtherFactorization * clone() const ; 00057 00060 00061 virtual void getAreas ( int numberRows, 00062 int numberColumns, 00063 CoinBigIndex maximumL, 00064 CoinBigIndex maximumU ); 00065 00067 virtual void preProcess ( ); 00073 virtual int factor ( ); 00075 virtual void postProcess(const int * sequence, int * pivotVariable); 00077 virtual void makeNonSingular(int * sequence, int numberColumns); 00079 00082 00083 virtual inline int numberElements ( ) const { 00084 return numberRows_*(numberColumns_+numberPivots_); 00085 } 00087 double maximumCoefficient() const; 00089 00092 00100 virtual int replaceColumn ( CoinIndexedVector * regionSparse, 00101 int pivotRow, 00102 double pivotCheck , 00103 bool checkBeforeModifying=false, 00104 double acceptablePivot=1.0e-8); 00106 00117 virtual int updateColumnFT ( CoinIndexedVector * regionSparse, 00118 CoinIndexedVector * regionSparse2, 00119 bool noPermute=false); 00120 00123 virtual int updateColumn ( CoinIndexedVector * regionSparse, 00124 CoinIndexedVector * regionSparse2, 00125 bool noPermute=false) const; 00127 virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1, 00128 CoinIndexedVector * regionSparse2, 00129 CoinIndexedVector * regionSparse3, 00130 bool noPermute=false); 00132 int upColumn ( CoinIndexedVector * regionSparse, 00133 CoinIndexedVector * regionSparse2, 00134 bool noPermute=false, bool save=false) const; 00139 virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse, 00140 CoinIndexedVector * regionSparse2) const; 00142 int upColumnTranspose ( CoinIndexedVector * regionSparse, 00143 CoinIndexedVector * regionSparse2) const; 00145 00146 00150 00151 inline void clearArrays() 00152 { gutsOfDestructor();} 00154 inline int * indices() const 00155 { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);} 00157 virtual inline int * permute() const 00158 { return pivotRow_;} 00160 00162 void gutsOfDestructor(); 00164 void gutsOfInitialize(); 00166 void gutsOfCopy(const CoinSimpFactorization &other); 00167 00168 00170 void factorize(int numberOfRows, 00171 int numberOfColumns, 00172 const int colStarts[], 00173 const int indicesRow[], 00174 const double elements[]); 00176 int mainLoopFactor (FactorPointers &pointers ); 00178 void copyLbyRows(); 00180 void copyUbyColumns(); 00182 int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack); 00184 int findPivotShCol(FactorPointers &pointers, int &r, int &s); 00186 int findPivotSimp(FactorPointers &pointers, int &r, int &s); 00188 void GaussEliminate(FactorPointers &pointers, int &r, int &s); 00190 int findShortRow(const int column, const int length, int &minRow, 00191 int &minRowLength, FactorPointers &pointers); 00193 int findShortColumn(const int row, const int length, int &minCol, 00194 int &minColLength, FactorPointers &pointers); 00196 double findMaxInRrow(const int row, FactorPointers &pointers); 00198 void pivoting(const int pivotRow, const int pivotColumn, 00199 const double invPivot, FactorPointers &pointers); 00201 void updateCurrentRow(const int pivotRow, const int row, 00202 const double multiplier, FactorPointers &pointers, 00203 int &newNonZeros); 00205 void increaseLsize(); 00207 void increaseRowSize(const int row, const int newSize); 00209 void increaseColSize(const int column, const int newSize, const bool b); 00211 void enlargeUrow(const int numNewElements); 00213 void enlargeUcol(const int numNewElements, const bool b); 00215 int findInRow(const int row, const int column); 00217 int findInColumn(const int column, const int row); 00219 void removeRowFromActSet(const int row, FactorPointers &pointers); 00221 void removeColumnFromActSet(const int column, FactorPointers &pointers); 00223 void allocateSpaceForU(); 00225 void allocateSomeArrays(); 00227 void initialSomeNumbers(); 00229 void Lxeqb(double *b) const; 00231 void Lxeqb2(double *b1, double *b2) const; 00233 void Uxeqb(double *b, double *sol) const; 00235 void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const; 00237 void xLeqb(double *b) const; 00239 void xUeqb(double *b, double *sol) const; 00241 int LUupdate(int newBasicCol); 00243 void newEta(int row, int numNewElements); 00245 void copyRowPermutations(); 00247 void Hxeqb(double *b) const; 00249 void Hxeqb2(double *b1, double *b2) const; 00251 void xHeqb(double *b) const; 00253 void ftran(double *b, double *sol, bool save) const; 00255 void ftran2(double *b1, double *sol1, double *b2, double *sol2) const; 00257 void btran(double *b, double *sol) const; 00259 00260 00261 00263 protected: 00266 int checkPivot(double saveFromU, double oldPivot) const; 00268 protected: 00269 00272 00273 double *denseVector_; 00275 double *workArea2_; 00277 double *workArea3_; 00279 int *vecLabels_; 00281 int *indVector_; 00282 00284 double *auxVector_; 00286 int *auxInd_; 00287 00289 double *vecKeep_; 00291 int *indKeep_; 00293 mutable int keepSize_; 00294 00295 00296 00298 int *LrowStarts_; 00300 int *LrowLengths_; 00302 double *Lrows_; 00304 int *LrowInd_; 00306 int LrowSize_; 00308 int LrowCap_; 00309 00311 int *LcolStarts_; 00313 int *LcolLengths_; 00315 double *Lcolumns_; 00317 int *LcolInd_; 00319 int LcolSize_; 00321 int LcolCap_; 00322 00323 00325 int *UrowStarts_; 00327 int *UrowLengths_; 00328 #ifdef COIN_SIMP_CAPACITY 00329 00330 int *UrowCapacities_; 00331 #endif 00332 00333 double *Urows_; 00335 int *UrowInd_; 00337 int UrowMaxCap_; 00339 int UrowEnd_; 00341 int firstRowInU_; 00343 int lastRowInU_; 00345 int *prevRowInU_; 00347 int *nextRowInU_; 00348 00350 int *UcolStarts_; 00352 int *UcolLengths_; 00353 #ifdef COIN_SIMP_CAPACITY 00354 00355 int *UcolCapacities_; 00356 #endif 00357 00358 double *Ucolumns_; 00360 int *UcolInd_; 00362 int *prevColInU_; 00364 int *nextColInU_; 00366 int firstColInU_; 00368 int lastColInU_; 00370 int UcolMaxCap_; 00372 int UcolEnd_; 00374 int *colSlack_; 00375 00377 double *invOfPivots_; 00378 00380 int *colOfU_; 00382 int *colPosition_; 00384 int *rowOfU_; 00386 int *rowPosition_; 00388 int *secRowOfU_; 00390 int *secRowPosition_; 00391 00393 int *EtaPosition_; 00395 int *EtaStarts_; 00397 int *EtaLengths_; 00399 int *EtaInd_; 00401 double *Eta_; 00403 int EtaSize_; 00405 int lastEtaRow_; 00407 int maxEtaRows_; 00409 int EtaMaxCap_; 00410 00412 int minIncrease_; 00414 double updateTol_; 00416 bool doSuhlHeuristic_; 00418 double maxU_; 00420 double maxGrowth_; 00422 double maxA_; 00424 int pivotCandLimit_; 00426 int numberSlacks_; 00428 int firstNumberSlacks_; 00430 }; 00431 #endif