00001
00002
00003
00004
00005
00006
00007
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
00033 FactorPointers( int numRows, int numCols, int *UrowLengths_, int *UcolLengths_ );
00034
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
00330 int *UrowCapacities_;
00331 #endif
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
00355 int *UcolCapacities_;
00356 #endif
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