# CoinSimpFactorization.hpp

Go to the documentation of this file.

    00001 /* $Id: CoinSimpFactorization.hpp 1416 2011-04-17 09:57:29Z stefan $ */
    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
    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

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines