Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CoinSimpFactorization.hpp
Go to the documentation of this file.
1 /* $Id: CoinSimpFactorization.hpp 1416 2011-04-17 09:57:29Z stefan $ */
2 // Copyright (C) 2008, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 /*
7  This is a simple factorization of the LP Basis
8  */
9 #ifndef CoinSimpFactorization_H
10 #define CoinSimpFactorization_H
11 
12 #include <iostream>
13 #include <string>
14 #include <cassert>
15 #include "CoinTypes.hpp"
16 #include "CoinIndexedVector.hpp"
18 class CoinPackedMatrix;
19 
20 
23 public:
24  double *rowMax;
26  int *prevRow;
27  int *nextRow;
29  int *prevColumn;
30  int *nextColumn;
31  int *newCols;
32  //constructor
33  FactorPointers( int numRows, int numCols, int *UrowLengths_, int *UcolLengths_ );
34  // destructor
36 };
37 
39  friend void CoinSimpFactorizationUnitTest( const std::string & mpsDir );
40 
41 public:
42 
49 
51  virtual ~CoinSimpFactorization ( );
55  virtual CoinOtherFactorization * clone() const ;
57 
60  virtual void getAreas ( int numberRows,
62  int numberColumns,
63  CoinBigIndex maximumL,
64  CoinBigIndex maximumU );
65 
67  virtual void preProcess ( );
73  virtual int factor ( );
75  virtual void postProcess(const int * sequence, int * pivotVariable);
77  virtual void makeNonSingular(int * sequence, int numberColumns);
79 
82  virtual inline int numberElements ( ) const {
85  }
87  double maximumCoefficient() const;
89 
92 
100  virtual int replaceColumn ( CoinIndexedVector * regionSparse,
101  int pivotRow,
102  double pivotCheck ,
103  bool checkBeforeModifying=false,
104  double acceptablePivot=1.0e-8);
106 
117  virtual int updateColumnFT ( CoinIndexedVector * regionSparse,
118  CoinIndexedVector * regionSparse2,
119  bool noPermute=false);
120 
123  virtual int updateColumn ( CoinIndexedVector * regionSparse,
124  CoinIndexedVector * regionSparse2,
125  bool noPermute=false) const;
127  virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1,
128  CoinIndexedVector * regionSparse2,
129  CoinIndexedVector * regionSparse3,
130  bool noPermute=false);
132  int upColumn ( CoinIndexedVector * regionSparse,
133  CoinIndexedVector * regionSparse2,
134  bool noPermute=false, bool save=false) const;
139  virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse,
140  CoinIndexedVector * regionSparse2) const;
142  int upColumnTranspose ( CoinIndexedVector * regionSparse,
143  CoinIndexedVector * regionSparse2) const;
145 
150  inline void clearArrays()
152  { gutsOfDestructor();}
154  inline int * indices() const
155  { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
157  virtual inline int * permute() const
158  { return pivotRow_;}
160 
162  void gutsOfDestructor();
164  void gutsOfInitialize();
166  void gutsOfCopy(const CoinSimpFactorization &other);
167 
168 
170  void factorize(int numberOfRows,
171  int numberOfColumns,
172  const int colStarts[],
173  const int indicesRow[],
174  const double elements[]);
176  int mainLoopFactor (FactorPointers &pointers );
178  void copyLbyRows();
180  void copyUbyColumns();
182  int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
184  int findPivotShCol(FactorPointers &pointers, int &r, int &s);
186  int findPivotSimp(FactorPointers &pointers, int &r, int &s);
188  void GaussEliminate(FactorPointers &pointers, int &r, int &s);
190  int findShortRow(const int column, const int length, int &minRow,
191  int &minRowLength, FactorPointers &pointers);
193  int findShortColumn(const int row, const int length, int &minCol,
194  int &minColLength, FactorPointers &pointers);
196  double findMaxInRrow(const int row, FactorPointers &pointers);
198  void pivoting(const int pivotRow, const int pivotColumn,
199  const double invPivot, FactorPointers &pointers);
201  void updateCurrentRow(const int pivotRow, const int row,
202  const double multiplier, FactorPointers &pointers,
203  int &newNonZeros);
205  void increaseLsize();
207  void increaseRowSize(const int row, const int newSize);
209  void increaseColSize(const int column, const int newSize, const bool b);
211  void enlargeUrow(const int numNewElements);
213  void enlargeUcol(const int numNewElements, const bool b);
215  int findInRow(const int row, const int column);
217  int findInColumn(const int column, const int row);
219  void removeRowFromActSet(const int row, FactorPointers &pointers);
221  void removeColumnFromActSet(const int column, FactorPointers &pointers);
223  void allocateSpaceForU();
225  void allocateSomeArrays();
227  void initialSomeNumbers();
229  void Lxeqb(double *b) const;
231  void Lxeqb2(double *b1, double *b2) const;
233  void Uxeqb(double *b, double *sol) const;
235  void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
237  void xLeqb(double *b) const;
239  void xUeqb(double *b, double *sol) const;
241  int LUupdate(int newBasicCol);
243  void newEta(int row, int numNewElements);
245  void copyRowPermutations();
247  void Hxeqb(double *b) const;
249  void Hxeqb2(double *b1, double *b2) const;
251  void xHeqb(double *b) const;
253  void ftran(double *b, double *sol, bool save) const;
255  void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
257  void btran(double *b, double *sol) const;
259 
260 
261 
263 protected:
266  int checkPivot(double saveFromU, double oldPivot) const;
268 protected:
269 
272  double *denseVector_;
275  double *workArea2_;
277  double *workArea3_;
282 
284  double *auxVector_;
286  int *auxInd_;
287 
289  double *vecKeep_;
291  int *indKeep_;
293  mutable int keepSize_;
294 
295 
296 
302  double *Lrows_;
304  int *LrowInd_;
306  int LrowSize_;
308  int LrowCap_;
309 
315  double *Lcolumns_;
317  int *LcolInd_;
321  int LcolCap_;
322 
323 
328 #ifdef COIN_SIMP_CAPACITY
329  int *UrowCapacities_;
331 #endif
332  double *Urows_;
335  int *UrowInd_;
339  int UrowEnd_;
348 
353 #ifdef COIN_SIMP_CAPACITY
354  int *UcolCapacities_;
356 #endif
357  double *Ucolumns_;
360  int *UcolInd_;
372  int UcolEnd_;
374  int *colSlack_;
375 
377  double *invOfPivots_;
378 
380  int *colOfU_;
384  int *rowOfU_;
391 
399  int *EtaInd_;
401  double *Eta_;
403  int EtaSize_;
410 
414  double updateTol_;
418  double maxU_;
420  double maxGrowth_;
422  double maxA_;
430 };
431 #endif
void increaseRowSize(const int row, const int newSize)
allocates more space for a row of U
virtual int updateColumnFT(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2, bool noPermute=false)
Updates one column (FTRAN) from regionSparse2 Tries to do FT update number returned is negative if no...
int lastColInU_
last column in U
int * EtaStarts_
Starts of eta vectors.
virtual int factor()
Does most of factorization returning status 0 - OK -99 - needs more memory -1 - singular - use number...
int pivotCandLimit_
maximum number of candidates for pivot
void enlargeUrow(const int numNewElements)
allocates more space for rows of U
int * LrowInd_
indices in the rows of L
int * UcolLengths_
Lengths of the columns of U.
void btran(double *b, double *sol) const
does BTRAN
int * UrowLengths_
Lengths of the rows of U.
double maxGrowth_
bound on the growth rate
int minIncrease_
minimum storage increase
void ftran2(double *b1, double *sol1, double *b2, double *sol2) const
same as above but with two columns
int UrowMaxCap_
maximum capacity of Urows
virtual void postProcess(const int *sequence, int *pivotVariable)
Does post processing on valid factorization - putting variables on correct rows.
Abstract base class which also has some scalars so can be used from Dense or Simp.
virtual void getAreas(int numberRows, int numberColumns, CoinBigIndex maximumL, CoinBigIndex maximumU)
Gets space for a factorization.
int numberPivots_
Number pivots since last factorization.
int * LcolLengths_
Lengths of the columns of L.
int EtaSize_
number of elements in Eta_
int * UcolInd_
Indices in the columns of U.
pointers used during factorization
void allocateSomeArrays()
allocates several working arrays
int maxEtaRows_
maximum number of eta vectors
void factorize(int numberOfRows, int numberOfColumns, const int colStarts[], const int indicesRow[], const double elements[])
calls factorization
int numberRows_
Number of Rows in factorization.
double * workArea3_
work array
int UcolMaxCap_
maximum capacity of Ucolumns_
int firstRowInU_
first row in U
void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const
same as above but with two rhs
void newEta(int row, int numNewElements)
creates a new eta vector
virtual ~CoinSimpFactorization()
Destructor.
int * LrowLengths_
Lengths of the rows of L.
bool doSuhlHeuristic_
do Shul heuristic
void gutsOfCopy(const CoinSimpFactorization &other)
The real work of copy.
int * LcolStarts_
Starts of the columns of L.
int numberRows() const
Number of Rows after factorization.
void clearArrays()
Get rid of all memory.
int * EtaInd_
columns of eta vectors
int * prevColInU_
previous column in U
int * secRowPosition_
position of row after permutation during LUupdate
void GaussEliminate(FactorPointers &pointers, int &r, int &s)
does Gauss elimination
void removeColumnFromActSet(const int column, FactorPointers &pointers)
declares a column inactive
int * UcolStarts_
Starts of the columns of U.
double updateTol_
maximum size for the diagonal of U after update
int UrowEnd_
number of used places in Urows
int * rowPosition_
position of row after permutation
void gutsOfDestructor()
The real work of destructor.
int findShortColumn(const int row, const int length, int &minCol, int &minColLength, FactorPointers &pointers)
finds short column that intersects a given row
void xHeqb(double *b) const
solves x H = b
int findShortRow(const int column, const int length, int &minRow, int &minRowLength, FactorPointers &pointers)
finds short row that intersects a given column
int * LcolInd_
indices in the columns of L
void increaseLsize()
allocates more space for L
FactorPointers(int numRows, int numCols, int *UrowLengths_, int *UcolLengths_)
double * workArea2_
work array
int * indices() const
Returns array to put basis indices in.
double * Eta_
elements of eta vectors
virtual int replaceColumn(CoinIndexedVector *regionSparse, int pivotRow, double pivotCheck, bool checkBeforeModifying=false, double acceptablePivot=1.0e-8)
Replaces one Column to basis, returns 0=OK, 1=Probably OK, 2=singular, 3=no room If checkBeforeModify...
double * Lcolumns_
L by columns.
void ftran(double *b, double *sol, bool save) const
does FTRAN
CoinFactorizationDouble * elements_
Elements of factorization and updates length is maxR*maxR+maxSpace will always be long enough so can ...
double * invOfPivots_
inverse values of the elements of diagonal of U
int upColumnTranspose(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2) const
does updateColumnTranspose, the other is a wrapper
void Lxeqb(double *b) const
solves L x = b
int * LrowStarts_
Starts of the rows of L.
virtual int updateTwoColumnsFT(CoinIndexedVector *regionSparse1, CoinIndexedVector *regionSparse2, CoinIndexedVector *regionSparse3, bool noPermute=false)
does FTRAN on two columns
virtual CoinFactorizationDouble * elements() const
Returns array to put basis elements in.
int numberColumns() const
Total number of columns in factorization.
int keepSize_
number of nonzeros
int LUupdate(int newBasicCol)
updates factorization after a Simplex iteration
int * auxInd_
auxiliary vector
int numberSlacks_
number of slacks in basis
double * denseVector_
work array (should be initialized to zero)
int EtaMaxCap_
Capacity of Eta_.
Indexed Vector.
int firstNumberSlacks_
number of slacks in irst basis
void removeRowFromActSet(const int row, FactorPointers &pointers)
declares a row inactive
void pivoting(const int pivotRow, const int pivotColumn, const double invPivot, FactorPointers &pointers)
does pivoting
double maximumCoefficient() const
Returns maximum absolute value in factorization.
void copyLbyRows()
copies L by rows
int * prevRowInU_
previous row in U
void copyUbyColumns()
copies U by columns
int * EtaPosition_
position of Eta vector
int * colSlack_
indicator of slack variables
void gutsOfInitialize()
The real work of constructor.
void Hxeqb(double *b) const
solves H x = b, where H is a product of eta matrices
virtual int * permute() const
Returns permute in.
CoinSimpFactorization()
Default constructor.
int checkPivot(double saveFromU, double oldPivot) const
int * nextRowInU_
next row in U
virtual void makeNonSingular(int *sequence, int numberColumns)
Makes a non-singular basis by replacing variables.
int LrowSize_
Size of Lrows_;.
virtual int updateColumnTranspose(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2) const
Updates one column (BTRAN) from regionSparse2 regionSparse starts as zero and is zero at end Note - i...
int * indKeep_
indices of this vector
void Hxeqb2(double *b1, double *b2) const
same as above but with two rhs
void updateCurrentRow(const int pivotRow, const int row, const double multiplier, FactorPointers &pointers, int &newNonZeros)
part of pivoting
void xLeqb(double *b) const
solves x L = b
int LcolSize_
numbers of elements in L
virtual int numberElements() const
Total number of elements in factorization.
Sparse Matrix Base Class.
int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack)
finds a pivot element using Markowitz count
void allocateSpaceForU()
allocates space for U
void increaseColSize(const int column, const int newSize, const bool b)
allocates more space for a column of U
int * indVector_
array of indices
void xUeqb(double *b, double *sol) const
solves x U = b
int * rowOfU_
permutations of rows
double * vecKeep_
vector to keep for LUupdate
int CoinBigIndex
int findPivotShCol(FactorPointers &pointers, int &r, int &s)
finds a pivot in a shortest column
int * nextColInU_
next column in U
int * colOfU_
permutation of columns
void initialSomeNumbers()
initializes some numbers
int * UrowStarts_
Starts of the rows of U.
void copyRowPermutations()
makes a copy of row permutations
int firstColInU_
first column in U
void enlargeUcol(const int numNewElements, const bool b)
allocates more space for columns of U
virtual CoinOtherFactorization * clone() const
Clone.
int * vecLabels_
array of labels (should be initialized to zero)
int findPivotSimp(FactorPointers &pointers, int &r, int &s)
finds a pivot in the first column available
int findInRow(const int row, const int column)
finds a given row in a column
int upColumn(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2, bool noPermute=false, bool save=false) const
does updatecolumn if save==true keeps column for replace column
virtual int * pivotRow() const
Returns pivot row.
int LcolCap_
maximum capacity of L
int findInColumn(const int column, const int row)
finds a given column in a row
int LrowCap_
Capacity of Lrows_.
void Lxeqb2(double *b1, double *b2) const
same as above but with two rhs
double * Ucolumns_
U by columns.
int * EtaLengths_
Lengths of eta vectors.
int * secRowOfU_
permutations of rows during LUupdate
int numberColumns_
Number of Columns in factorization.
virtual int updateColumn(CoinIndexedVector *regionSparse, CoinIndexedVector *regionSparse2, bool noPermute=false) const
This version has same effect as above with FTUpdate==false so number returned is always &gt;=0...
void Uxeqb(double *b, double *sol) const
solves U x = b
virtual void preProcess()
PreProcesses column ordered copy of basis.
int * colPosition_
position of column after permutation
double * auxVector_
auxiliary vector
int UcolEnd_
last used position in Ucolumns_
CoinSimpFactorization & operator=(const CoinSimpFactorization &other)
= copy
int * UrowInd_
Indices in the rows of U.
double findMaxInRrow(const int row, FactorPointers &pointers)
finds maximum absolute value in a row
int mainLoopFactor(FactorPointers &pointers)
main loop of factorization
friend void CoinSimpFactorizationUnitTest(const std::string &mpsDir)