CoinUtils  trunk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
CoinSimpFactorization.hpp
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines