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

- File List
- File Members

# /home/coin/SVN-release/CoinUtils-2.6.1/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
    00331     int *UrowCapacities_;
    00332 #endif
    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
    00356     int *UcolCapacities_;
    00357 #endif
    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