- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Bcps-0.91.0/CoinUtils/src/CoinSimpFactorization.hpp

Go to the documentation of this file.

    00001 // Copyright (C) 2008, International Business Machines
    00002 // Corporation and others.  All Rights Reserved.
    00003
    00004 /*
    00005    This is a simple factorization of the LP Basis
    00006
    00007
    00008  */
    00009 #ifndef CoinSimpFactorization_H
    00010 #define CoinSimpFactorization_H
    00011
    00012 #include <iostream>
    00013 #include <string>
    00014 #include <cassert>
    00015 #include "CoinFinite.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 CoinSmallFactorization {
    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 CoinSmallFactorization * 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);
    00105
    00116     virtual int updateColumnFT ( CoinIndexedVector * regionSparse,
    00117                          CoinIndexedVector * regionSparse2,
    00118                          bool noPermute=false);
    00119
    00122     virtual int updateColumn ( CoinIndexedVector * regionSparse,
    00123                        CoinIndexedVector * regionSparse2,
    00124                        bool noPermute=false) const;
    00126     virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1,
    00127                            CoinIndexedVector * regionSparse2,
    00128                            CoinIndexedVector * regionSparse3,
    00129                            bool noPermute=false);
    00131     int upColumn ( CoinIndexedVector * regionSparse,
    00132                    CoinIndexedVector * regionSparse2,
    00133                    bool noPermute=false, bool save=false) const;
    00138     virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse,
    00139                                 CoinIndexedVector * regionSparse2) const;
    00141     int upColumnTranspose ( CoinIndexedVector * regionSparse,
    00142                                 CoinIndexedVector * regionSparse2) const;
    00144
    00145
    00149
    00150   inline void clearArrays()
    00151   { gutsOfDestructor();}
    00153   inline int * indices() const
    00154   { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
    00156   virtual inline int * permute() const
    00157   { return pivotRow_;}
    00159
    00161   void gutsOfDestructor();
    00163   void gutsOfInitialize();
    00165   void gutsOfCopy(const CoinSimpFactorization &other);
    00166
    00167
    00169   void factorize(int numberOfRows,
    00170                  int numberOfColumns,
    00171                  const int colStarts[],
    00172                  const int indicesRow[],
    00173                  const double elements[]);
    00175     int mainLoopFactor (FactorPointers &pointers );
    00177     void copyLbyRows();
    00179     void copyUbyColumns();
    00181     int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
    00183     int findPivotShCol(FactorPointers &pointers, int &r, int &s);
    00185     int findPivotSimp(FactorPointers &pointers, int &r, int &s);
    00187     void GaussEliminate(FactorPointers &pointers, int &r, int &s);
    00189     int findShortRow(const int column, const int length, int &minRow,
    00190                      int &minRowLength, FactorPointers &pointers);
    00192     int findShortColumn(const int row, const int length, int &minCol,
    00193                         int &minColLength, FactorPointers &pointers);
    00195     double findMaxInRrow(const int row, FactorPointers &pointers);
    00197     void pivoting(const int pivotRow, const int pivotColumn,
    00198                   const double invPivot, FactorPointers &pointers);
    00200     void updateCurrentRow(const int pivotRow, const int row,
    00201                           const double multiplier, FactorPointers &pointers,
    00202                           int &newNonZeros);
    00204     void increaseLsize();
    00206     void increaseRowSize(const int row, const int newSize);
    00208     void increaseColSize(const int column, const int newSize, const bool b);
    00210     void enlargeUrow(const int numNewElements);
    00212     void enlargeUcol(const int numNewElements, const bool b);
    00214     int findInRow(const int row, const int column);
    00216     int findInColumn(const int column, const int row);
    00218     void removeRowFromActSet(const int row, FactorPointers &pointers);
    00220     void removeColumnFromActSet(const int column, FactorPointers &pointers);
    00222     void allocateSpaceForU();
    00224     void allocateSomeArrays();
    00226     void initialSomeNumbers();
    00228     void Lxeqb(double *b) const;
    00230     void Lxeqb2(double *b1, double *b2) const;
    00232     void Uxeqb(double *b, double *sol) const;
    00234     void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
    00236     void xLeqb(double *b) const;
    00238     void xUeqb(double *b, double *sol) const;
    00240     int LUupdate(int newBasicCol);
    00242     void newEta(int row, int numNewElements);
    00244     void copyRowPermutations();
    00246     void Hxeqb(double *b) const;
    00248     void Hxeqb2(double *b1, double *b2) const;
    00250     void xHeqb(double *b) const;
    00252     void ftran(double *b, double *sol, bool save) const;
    00254     void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
    00256     void btran(double *b, double *sol) const;
    00258
    00259
    00260
    00262 protected:
    00265   int checkPivot(double saveFromU, double oldPivot) const;
    00267 protected:
    00268
    00271
    00272     double *denseVector_;
    00274     double *workArea2_;
    00276     double *workArea3_;
    00278     int *vecLabels_;
    00280     int *indVector_;
    00281
    00283     double *auxVector_;
    00285     int *auxInd_;
    00286
    00288     double *vecKeep_;
    00290     int *indKeep_;
    00292     mutable int keepSize_;
    00293
    00294
    00295
    00297     int *LrowStarts_;
    00299     int *LrowLengths_;
    00301     double *Lrows_;
    00303     int *LrowInd_;
    00305     int LrowSize_;
    00307     int LrowCap_;
    00308
    00310     int *LcolStarts_;
    00312     int *LcolLengths_;
    00314     double *Lcolumns_;
    00316     int *LcolInd_;
    00318     int LcolSize_;
    00320     int LcolCap_;
    00321
    00322
    00324     int *UrowStarts_;
    00326     int *UrowLengths_;
    00327 #ifdef COIN_SIMP_CAPACITY
    00329     int *UrowCapacities_;
    00330 #endif
    00332     double *Urows_;
    00334     int *UrowInd_;
    00336     int UrowMaxCap_;
    00338     int UrowEnd_;
    00340     int firstRowInU_;
    00342     int lastRowInU_;
    00344     int *prevRowInU_;
    00346     int *nextRowInU_;
    00347
    00349     int *UcolStarts_;
    00351     int *UcolLengths_;
    00352 #ifdef COIN_SIMP_CAPACITY
    00354     int *UcolCapacities_;
    00355 #endif
    00357     double *Ucolumns_;
    00359     int *UcolInd_;
    00361     int *prevColInU_;
    00363     int *nextColInU_;
    00365     int firstColInU_;
    00367     int lastColInU_;
    00369     int UcolMaxCap_;
    00371     int UcolEnd_;
    00373     int *colSlack_;
    00374
    00376     double *invOfPivots_;
    00377
    00379     int *colOfU_;
    00381     int *colPosition_;
    00383     int *rowOfU_;
    00385     int *rowPosition_;
    00387     int *secRowOfU_;
    00389     int *secRowPosition_;
    00390
    00392     int *EtaPosition_;
    00394     int *EtaStarts_;
    00396     int *EtaLengths_;
    00398     int *EtaInd_;
    00400     double *Eta_;
    00402     int EtaSize_;
    00404     int lastEtaRow_;
    00406     int maxEtaRows_;
    00408     int EtaMaxCap_;
    00409
    00411     int minIncrease_;
    00413     double updateTol_;
    00415     bool doSuhlHeuristic_;
    00417     double maxU_;
    00419     double maxGrowth_;
    00421     double maxA_;
    00423     int pivotCandLimit_;
    00425     int numberSlacks_;
    00427     int firstNumberSlacks_;
    00429 };
    00430 #endif