• Main Page
  • Related Pages
  • Modules
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

/build/buildd/coinutils-2.6.4/CoinUtils/src/CoinSimpFactorization.hpp

Go to the documentation of this file.
00001 /* $Id: CoinSimpFactorization.hpp 1191 2009-07-25 08:38:12Z forrest $ */
00002 // Copyright (C) 2008, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
00004 
00005 /* 
00006    This is a simple factorization of the LP Basis
00007    
00008 
00009  */
00010 #ifndef CoinSimpFactorization_H
00011 #define CoinSimpFactorization_H
00012 
00013 #include <iostream>
00014 #include <string>
00015 #include <cassert>
00016 #include "CoinFinite.hpp"
00017 #include "CoinIndexedVector.hpp"
00018 #include "CoinDenseFactorization.hpp"
00019 class CoinPackedMatrix;
00020 
00021 
00023 class FactorPointers{
00024 public:
00025     double *rowMax;
00026     int *firstRowKnonzeros;
00027     int *prevRow;
00028     int *nextRow;
00029     int *firstColKnonzeros;
00030     int *prevColumn;
00031     int *nextColumn;
00032     int *newCols;
00033     //constructor
00034     FactorPointers( int numRows, int numCols, int *UrowLengths_, int *UcolLengths_ );
00035     // destructor
00036     ~ FactorPointers();
00037 };
00038 
00039 class CoinSimpFactorization : public CoinOtherFactorization {
00040    friend void CoinSimpFactorizationUnitTest( const std::string & mpsDir );
00041 
00042 public:
00043 
00046 
00047   CoinSimpFactorization (  );
00049   CoinSimpFactorization ( const CoinSimpFactorization &other);
00050   
00052   virtual ~CoinSimpFactorization (  );
00054   CoinSimpFactorization & operator = ( const CoinSimpFactorization & other );
00056   virtual CoinOtherFactorization * clone() const ;
00058 
00061 
00062   virtual void getAreas ( int numberRows,
00063                   int numberColumns,
00064                   CoinBigIndex maximumL,
00065                   CoinBigIndex maximumU );
00066   
00068   virtual void preProcess ( );
00074   virtual int factor ( );
00076   virtual void postProcess(const int * sequence, int * pivotVariable);
00078   virtual void makeNonSingular(int * sequence, int numberColumns);
00080 
00083 
00084   virtual inline int numberElements (  ) const {
00085     return numberRows_*(numberColumns_+numberPivots_);
00086   }
00088   double maximumCoefficient() const;
00090 
00093 
00101   virtual int replaceColumn ( CoinIndexedVector * regionSparse,
00102                       int pivotRow,
00103                       double pivotCheck ,
00104                               bool checkBeforeModifying=false,
00105                               double acceptablePivot=1.0e-8);
00107 
00118     virtual int updateColumnFT ( CoinIndexedVector * regionSparse,
00119                          CoinIndexedVector * regionSparse2,
00120                          bool noPermute=false);
00121     
00124     virtual int updateColumn ( CoinIndexedVector * regionSparse,
00125                        CoinIndexedVector * regionSparse2,
00126                        bool noPermute=false) const;
00128     virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1,
00129                            CoinIndexedVector * regionSparse2,
00130                            CoinIndexedVector * regionSparse3,
00131                            bool noPermute=false);
00133     int upColumn ( CoinIndexedVector * regionSparse,
00134                    CoinIndexedVector * regionSparse2,
00135                    bool noPermute=false, bool save=false) const;
00140     virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse,
00141                                 CoinIndexedVector * regionSparse2) const;
00143     int upColumnTranspose ( CoinIndexedVector * regionSparse,
00144                                 CoinIndexedVector * regionSparse2) const;
00146 
00147 
00151 
00152   inline void clearArrays()
00153   { gutsOfDestructor();}
00155   inline int * indices() const
00156   { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
00158   virtual inline int * permute() const
00159   { return pivotRow_;}
00161 
00163   void gutsOfDestructor();
00165   void gutsOfInitialize();
00167   void gutsOfCopy(const CoinSimpFactorization &other);
00168 
00169     
00171   void factorize(int numberOfRows,
00172                  int numberOfColumns,
00173                  const int colStarts[],
00174                  const int indicesRow[],
00175                  const double elements[]);
00177     int mainLoopFactor (FactorPointers &pointers );
00179     void copyLbyRows();
00181     void copyUbyColumns();
00183     int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
00185     int findPivotShCol(FactorPointers &pointers, int &r, int &s);
00187     int findPivotSimp(FactorPointers &pointers, int &r, int &s);
00189     void GaussEliminate(FactorPointers &pointers, int &r, int &s);
00191     int findShortRow(const int column, const int length, int &minRow, 
00192                      int &minRowLength, FactorPointers &pointers);
00194     int findShortColumn(const int row, const int length, int &minCol, 
00195                         int &minColLength, FactorPointers &pointers);
00197     double findMaxInRrow(const int row, FactorPointers &pointers);
00199     void pivoting(const int pivotRow, const int pivotColumn,
00200                   const double invPivot, FactorPointers &pointers);
00202     void updateCurrentRow(const int pivotRow, const int row, 
00203                           const double multiplier, FactorPointers &pointers,
00204                           int &newNonZeros);
00206     void increaseLsize();
00208     void increaseRowSize(const int row, const int newSize);
00210     void increaseColSize(const int column, const int newSize, const bool b);
00212     void enlargeUrow(const int numNewElements);
00214     void enlargeUcol(const int numNewElements, const bool b);
00216     int findInRow(const int row, const int column);
00218     int findInColumn(const int column, const int row);
00220     void removeRowFromActSet(const int row, FactorPointers &pointers);
00222     void removeColumnFromActSet(const int column, FactorPointers &pointers);
00224     void allocateSpaceForU();
00226     void allocateSomeArrays();
00228     void initialSomeNumbers();
00230     void Lxeqb(double *b) const;
00232     void Lxeqb2(double *b1, double *b2) const;
00234     void Uxeqb(double *b, double *sol) const;
00236     void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
00238     void xLeqb(double *b) const;
00240     void xUeqb(double *b, double *sol) const;
00242     int LUupdate(int newBasicCol);
00244     void newEta(int row, int numNewElements);
00246     void copyRowPermutations();
00248     void Hxeqb(double *b) const;
00250     void Hxeqb2(double *b1, double *b2) const;
00252     void xHeqb(double *b) const;
00254     void ftran(double *b, double *sol, bool save) const;
00256     void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
00258     void btran(double *b, double *sol) const;
00260 
00261 
00262 
00264 protected:
00267   int checkPivot(double saveFromU, double oldPivot) const;
00269 protected:
00270 
00273 
00274     double *denseVector_;
00276     double *workArea2_; 
00278     double *workArea3_;
00280     int *vecLabels_;
00282     int *indVector_;
00283 
00285     double *auxVector_;
00287     int *auxInd_;
00288 
00290     double *vecKeep_;
00292     int *indKeep_;
00294     mutable int keepSize_;
00295 
00296     
00297 
00299     int *LrowStarts_;
00301     int *LrowLengths_;
00303     double *Lrows_;
00305     int *LrowInd_;
00307     int LrowSize_; 
00309     int LrowCap_;
00310 
00312     int *LcolStarts_;
00314     int *LcolLengths_;
00316     double *Lcolumns_;
00318     int *LcolInd_;
00320     int LcolSize_;
00322     int LcolCap_;
00323    
00324 
00326     int *UrowStarts_;
00328     int *UrowLengths_;
00329 #ifdef COIN_SIMP_CAPACITY
00330 
00331     int *UrowCapacities_;
00332 #endif
00333 
00334     double *Urows_;
00336     int *UrowInd_;
00338     int UrowMaxCap_;
00340     int UrowEnd_;
00342     int firstRowInU_;
00344     int lastRowInU_;
00346     int *prevRowInU_;
00348     int *nextRowInU_;
00349 
00351     int *UcolStarts_;
00353     int *UcolLengths_;
00354 #ifdef COIN_SIMP_CAPACITY
00355 
00356     int *UcolCapacities_;
00357 #endif
00358 
00359     double *Ucolumns_;
00361     int *UcolInd_;
00363     int *prevColInU_;
00365     int *nextColInU_;
00367     int firstColInU_;
00369     int lastColInU_;
00371     int UcolMaxCap_;
00373     int UcolEnd_;    
00375     int *colSlack_;
00376  
00378     double *invOfPivots_;
00379 
00381     int *colOfU_;
00383     int *colPosition_;
00385     int *rowOfU_;
00387     int *rowPosition_;
00389     int *secRowOfU_;
00391     int *secRowPosition_;
00392     
00394     int *EtaPosition_;
00396     int *EtaStarts_;
00398     int *EtaLengths_;
00400     int *EtaInd_;
00402     double *Eta_;
00404     int EtaSize_;
00406     int lastEtaRow_;
00408     int maxEtaRows_;
00410     int EtaMaxCap_;
00411     
00413     int minIncrease_;
00415     double updateTol_;
00417     bool doSuhlHeuristic_;
00419     double maxU_;
00421     double maxGrowth_;
00423     double maxA_;
00425     int pivotCandLimit_;    
00427     int numberSlacks_;    
00429     int firstNumberSlacks_;
00431 };
00432 #endif

Generated on Fri Oct 15 2010 18:21:02 by  doxygen 1.7.1