CoinSimpFactorization.hpp
Go to the documentation of this file.
1 /* $Id: CoinSimpFactorization.hpp 1191 2009-07-25 08:38:12Z forrest $ */
2 // Copyright (C) 2008, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 
5 /*
6  This is a simple factorization of the LP Basis
7 
8 
9  */
10 #ifndef CoinSimpFactorization_H
11 #define CoinSimpFactorization_H
12 
13 #include <iostream>
14 #include <string>
15 #include <cassert>
16 #include "CoinFinite.hpp"
17 #include "CoinIndexedVector.hpp"
19 class CoinPackedMatrix;
20 
21 
24 public:
25  double *rowMax;
27  int *prevRow;
28  int *nextRow;
30  int *prevColumn;
31  int *nextColumn;
32  int *newCols;
33  //constructor
34  FactorPointers( int numRows, int numCols, int *UrowLengths_, int *UcolLengths_ );
35  // destructor
37 };
38 
40  friend void CoinSimpFactorizationUnitTest( const std::string & mpsDir );
41 
42 public:
43 
50 
52  virtual ~CoinSimpFactorization ( );
56  virtual CoinOtherFactorization * clone() const ;
58 
61  virtual void getAreas ( int numberRows,
63  int numberColumns,
64  CoinBigIndex maximumL,
65  CoinBigIndex maximumU );
66 
68  virtual void preProcess ( );
74  virtual int factor ( );
76  virtual void postProcess(const int * sequence, int * pivotVariable);
78  virtual void makeNonSingular(int * sequence, int numberColumns);
80 
83  virtual inline int numberElements ( ) const {
86  }
88  double maximumCoefficient() const;
90 
93 
101  virtual int replaceColumn ( CoinIndexedVector * regionSparse,
102  int pivotRow,
103  double pivotCheck ,
104  bool checkBeforeModifying=false,
105  double acceptablePivot=1.0e-8);
107 
118  virtual int updateColumnFT ( CoinIndexedVector * regionSparse,
119  CoinIndexedVector * regionSparse2,
120  bool noPermute=false);
121 
124  virtual int updateColumn ( CoinIndexedVector * regionSparse,
125  CoinIndexedVector * regionSparse2,
126  bool noPermute=false) const;
128  virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1,
129  CoinIndexedVector * regionSparse2,
130  CoinIndexedVector * regionSparse3,
131  bool noPermute=false);
133  int upColumn ( CoinIndexedVector * regionSparse,
134  CoinIndexedVector * regionSparse2,
135  bool noPermute=false, bool save=false) const;
140  virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse,
141  CoinIndexedVector * regionSparse2) const;
143  int upColumnTranspose ( CoinIndexedVector * regionSparse,
144  CoinIndexedVector * regionSparse2) const;
146 
151  inline void clearArrays()
153  { gutsOfDestructor();}
155  inline int * indices() const
156  { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
158  virtual inline int * permute() const
159  { return pivotRow_;}
161 
163  void gutsOfDestructor();
165  void gutsOfInitialize();
167  void gutsOfCopy(const CoinSimpFactorization &other);
168 
169 
171  void factorize(int numberOfRows,
172  int numberOfColumns,
173  const int colStarts[],
174  const int indicesRow[],
175  const double elements[]);
177  int mainLoopFactor (FactorPointers &pointers );
179  void copyLbyRows();
181  void copyUbyColumns();
183  int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
185  int findPivotShCol(FactorPointers &pointers, int &r, int &s);
187  int findPivotSimp(FactorPointers &pointers, int &r, int &s);
189  void GaussEliminate(FactorPointers &pointers, int &r, int &s);
191  int findShortRow(const int column, const int length, int &minRow,
192  int &minRowLength, FactorPointers &pointers);
194  int findShortColumn(const int row, const int length, int &minCol,
195  int &minColLength, FactorPointers &pointers);
197  double findMaxInRrow(const int row, FactorPointers &pointers);
199  void pivoting(const int pivotRow, const int pivotColumn,
200  const double invPivot, FactorPointers &pointers);
202  void updateCurrentRow(const int pivotRow, const int row,
203  const double multiplier, FactorPointers &pointers,
204  int &newNonZeros);
206  void increaseLsize();
208  void increaseRowSize(const int row, const int newSize);
210  void increaseColSize(const int column, const int newSize, const bool b);
212  void enlargeUrow(const int numNewElements);
214  void enlargeUcol(const int numNewElements, const bool b);
216  int findInRow(const int row, const int column);
218  int findInColumn(const int column, const int row);
220  void removeRowFromActSet(const int row, FactorPointers &pointers);
222  void removeColumnFromActSet(const int column, FactorPointers &pointers);
224  void allocateSpaceForU();
226  void allocateSomeArrays();
228  void initialSomeNumbers();
230  void Lxeqb(double *b) const;
232  void Lxeqb2(double *b1, double *b2) const;
234  void Uxeqb(double *b, double *sol) const;
236  void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
238  void xLeqb(double *b) const;
240  void xUeqb(double *b, double *sol) const;
242  int LUupdate(int newBasicCol);
244  void newEta(int row, int numNewElements);
246  void copyRowPermutations();
248  void Hxeqb(double *b) const;
250  void Hxeqb2(double *b1, double *b2) const;
252  void xHeqb(double *b) const;
254  void ftran(double *b, double *sol, bool save) const;
256  void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
258  void btran(double *b, double *sol) const;
260 
261 
262 
264 protected:
267  int checkPivot(double saveFromU, double oldPivot) const;
269 protected:
270 
273  double *denseVector_;
276  double *workArea2_;
278  double *workArea3_;
283 
285  double *auxVector_;
287  int *auxInd_;
288 
290  double *vecKeep_;
292  int *indKeep_;
294  mutable int keepSize_;
295 
296 
297 
303  double *Lrows_;
305  int *LrowInd_;
307  int LrowSize_;
309  int LrowCap_;
310 
316  double *Lcolumns_;
318  int *LcolInd_;
322  int LcolCap_;
323 
324 
329 #ifdef COIN_SIMP_CAPACITY
330  int *UrowCapacities_;
332 #endif
333  double *Urows_;
336  int *UrowInd_;
340  int UrowEnd_;
349 
354 #ifdef COIN_SIMP_CAPACITY
355  int *UcolCapacities_;
357 #endif
358  double *Ucolumns_;
361  int *UcolInd_;
373  int UcolEnd_;
375  int *colSlack_;
376 
378  double *invOfPivots_;
379 
381  int *colOfU_;
385  int *rowOfU_;
392 
400  int *EtaInd_;
402  double *Eta_;
404  int EtaSize_;
411 
415  double updateTol_;
419  double maxU_;
421  double maxGrowth_;
423  double maxA_;
431 };
432 #endif