DyLP  1.10.4
CoinSimpFactorization.hpp
Go to the documentation of this file.
1 /* $Id: CoinSimpFactorization.hpp 2083 2019-01-06 19:38:09Z unxusr $ */
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 
22 public:
23  double *rowMax;
25  int *prevRow;
26  int *nextRow;
28  int *prevColumn;
29  int *nextColumn;
30  int *newCols;
31  //constructor
32  FactorPointers(int numRows, int numCols, int *UrowLengths_, int *UcolLengths_);
33  // destructor
35 };
36 
38  friend void CoinSimpFactorizationUnitTest(const std::string &mpsDir);
39 
40 public:
47 
49  virtual ~CoinSimpFactorization();
51  CoinSimpFactorization &operator=(const CoinSimpFactorization &other);
53  virtual CoinOtherFactorization *clone() const;
55 
58  virtual void getAreas(int numberRows,
60  int numberColumns,
61  int maximumL,
62  int maximumU);
63 
65  virtual void preProcess();
71  virtual int factor();
73  virtual void postProcess(const int *sequence, int *pivotVariable);
75  virtual void makeNonSingular(int *sequence, int numberColumns);
77 
80  virtual inline int numberElements() const
82  {
83  return numberRows_ * (numberColumns_ + numberPivots_);
84  }
86  double maximumCoefficient() const;
88 
91 
99  virtual int replaceColumn(CoinIndexedVector *regionSparse,
100  int pivotRow,
101  double pivotCheck,
102  bool checkBeforeModifying = false,
103  double acceptablePivot = 1.0e-8);
105 
116  virtual int updateColumnFT(CoinIndexedVector *regionSparse,
117  CoinIndexedVector *regionSparse2,
118  bool noPermute = false);
119 
122  virtual int updateColumn(CoinIndexedVector *regionSparse,
123  CoinIndexedVector *regionSparse2,
124  bool noPermute = false) const;
126  virtual int updateTwoColumnsFT(CoinIndexedVector *regionSparse1,
127  CoinIndexedVector *regionSparse2,
128  CoinIndexedVector *regionSparse3,
129  bool noPermute = false);
131  int upColumn(CoinIndexedVector *regionSparse,
132  CoinIndexedVector *regionSparse2,
133  bool noPermute = false, bool save = false) const;
138  virtual int updateColumnTranspose(CoinIndexedVector *regionSparse,
139  CoinIndexedVector *regionSparse2) const;
141  int upColumnTranspose(CoinIndexedVector *regionSparse,
142  CoinIndexedVector *regionSparse2) const;
144 
149  inline void clearArrays()
151  {
152  gutsOfDestructor();
153  }
155  inline int *indices() const
156  {
157  return reinterpret_cast< int * >(elements_ + numberRows_ * numberRows_);
158  }
160  virtual inline int *permute() const
161  {
162  return pivotRow_;
163  }
165 
167  void gutsOfDestructor();
169  void gutsOfInitialize();
171  void gutsOfCopy(const CoinSimpFactorization &other);
172 
174  void factorize(int numberOfRows,
175  int numberOfColumns,
176  const int colStarts[],
177  const int indicesRow[],
178  const double elements[]);
180  int mainLoopFactor(FactorPointers &pointers);
182  void copyLbyRows();
184  void copyUbyColumns();
186  int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
188  int findPivotShCol(FactorPointers &pointers, int &r, int &s);
190  int findPivotSimp(FactorPointers &pointers, int &r, int &s);
192  void GaussEliminate(FactorPointers &pointers, int &r, int &s);
194  int findShortRow(const int column, const int length, int &minRow,
195  int &minRowLength, FactorPointers &pointers);
197  int findShortColumn(const int row, const int length, int &minCol,
198  int &minColLength, FactorPointers &pointers);
200  double findMaxInRrow(const int row, FactorPointers &pointers);
202  void pivoting(const int pivotRow, const int pivotColumn,
203  const double invPivot, FactorPointers &pointers);
205  void updateCurrentRow(const int pivotRow, const int row,
206  const double multiplier, FactorPointers &pointers,
207  int &newNonZeros);
209  void increaseLsize();
211  void increaseRowSize(const int row, const int newSize);
213  void increaseColSize(const int column, const int newSize, const bool b);
215  void enlargeUrow(const int numNewElements);
217  void enlargeUcol(const int numNewElements, const bool b);
219  int findInRow(const int row, const int column);
221  int findInColumn(const int column, const int row);
223  void removeRowFromActSet(const int row, FactorPointers &pointers);
225  void removeColumnFromActSet(const int column, FactorPointers &pointers);
227  void allocateSpaceForU();
229  void allocateSomeArrays();
231  void initialSomeNumbers();
233  void Lxeqb(double *b) const;
235  void Lxeqb2(double *b1, double *b2) const;
237  void Uxeqb(double *b, double *sol) const;
239  void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
241  void xLeqb(double *b) const;
243  void xUeqb(double *b, double *sol) const;
245  int LUupdate(int newBasicCol);
247  void newEta(int row, int numNewElements);
249  void copyRowPermutations();
251  void Hxeqb(double *b) const;
253  void Hxeqb2(double *b1, double *b2) const;
255  void xHeqb(double *b) const;
257  void ftran(double *b, double *sol, bool save) const;
259  void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
261  void btran(double *b, double *sol) const;
263 
265 protected:
268  int checkPivot(double saveFromU, double oldPivot) const;
270 protected:
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 
301  double *Lrows_;
303  int *LrowInd_;
307  int LrowCap_;
308 
314  double *Lcolumns_;
316  int *LcolInd_;
320  int LcolCap_;
321 
326 #ifdef COIN_SIMP_CAPACITY
327  int *UrowCapacities_;
329 #endif
330  double *Urows_;
333  int *UrowInd_;
337  int UrowEnd_;
346 
351 #ifdef COIN_SIMP_CAPACITY
352  int *UcolCapacities_;
354 #endif
355  double *Ucolumns_;
358  int *UcolInd_;
370  int UcolEnd_;
372  int *colSlack_;
373 
375  double *invOfPivots_;
376 
378  int *colOfU_;
382  int *rowOfU_;
389 
397  int *EtaInd_;
399  double *Eta_;
401  int EtaSize_;
408 
412  double updateTol_;
416  double maxU_;
418  double maxGrowth_;
420  double maxA_;
428 };
429 #endif
430 
431 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
432 */
int lastColInU_
last column in U
int * EtaStarts_
Starts of eta vectors.
int pivotCandLimit_
maximum number of candidates for pivot
int * LrowInd_
indices in the rows of L
int * UcolLengths_
Lengths of the columns of U.
int * indices() const
Returns array to put basis indices in.
int * UrowLengths_
Lengths of the rows of U.
double maxGrowth_
bound on the growth rate
int minIncrease_
minimum storage increase
int UrowMaxCap_
maximum capacity of Urows
Abstract base class which also has some scalars so can be used from Dense or Simp.
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
int maxEtaRows_
maximum number of eta vectors
double * workArea3_
work array
int UcolMaxCap_
maximum capacity of Ucolumns_
int firstRowInU_
first row in U
int * LrowLengths_
Lengths of the rows of L.
bool doSuhlHeuristic_
do Shul heuristic
int * LcolStarts_
Starts of the columns of L.
int * EtaInd_
columns of eta vectors
int * prevColInU_
previous column in U
int * secRowPosition_
position of row after permutation during LUupdate
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
int * LcolInd_
indices in the columns of L
FactorPointers(int numRows, int numCols, int *UrowLengths_, int *UcolLengths_)
double * workArea2_
work array
double * Eta_
elements of eta vectors
double * Lcolumns_
L by columns.
virtual int * permute() const
Returns permute in.
double * invOfPivots_
inverse values of the elements of diagonal of U
int * LrowStarts_
Starts of the rows of L.
int keepSize_
number of nonzeros
int * auxInd_
auxiliary vector
int numberSlacks_
number of slacks in basis
int EtaMaxCap_
Capacity of Eta_.
Indexed Vector.
int firstNumberSlacks_
number of slacks in irst basis
int * prevRowInU_
previous row in U
int * EtaPosition_
position of Eta vector
int * colSlack_
indicator of slack variables
int * nextRowInU_
next row in U
int LrowSize_
Size of Lrows_;.
int * indKeep_
indices of this vector
int LcolSize_
numbers of elements in L
Sparse Matrix Base Class.
int * indVector_
array of indices
int * rowOfU_
permutations of rows
double * vecKeep_
vector to keep for LUupdate
int * nextColInU_
next column in U
int * colOfU_
permutation of columns
int * UrowStarts_
Starts of the rows of U.
int firstColInU_
first column in U
int * vecLabels_
array of labels (should be initialized to zero)
int LcolCap_
maximum capacity of L
int LrowCap_
Capacity of Lrows_.
int * EtaLengths_
Lengths of eta vectors.
int * secRowOfU_
permutations of rows during LUupdate
int * colPosition_
position of column after permutation
double * auxVector_
auxiliary vector
int UcolEnd_
last used position in Ucolumns_
int * UrowInd_
Indices in the rows of U.