coin-Bcp
CoinAbcDenseFactorization.hpp
Go to the documentation of this file.
1 /* $Id: CoinAbcDenseFactorization.hpp 2385 2019-01-06 19:43:06Z unxusr $ */
2 // Copyright (C) 2008, International Business Machines
3 // Corporation and others, Copyright (C) 2012, FasterCoin. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 /*
7  Authors
8 
9  John Forrest
10 
11  */
12 #ifndef CoinAbcDenseFactorization_H
13 #define CoinAbcDenseFactorization_H
14 
15 #include <iostream>
16 #include <string>
17 #include <cassert>
18 #include "CoinTypes.hpp"
19 #include "CoinAbcCommon.hpp"
20 #include "CoinIndexedVector.hpp"
21 class CoinPackedMatrix;
24 
25 public:
32 
34  virtual ~CoinAbcAnyFactorization();
37 
39  virtual CoinAbcAnyFactorization *clone() const = 0;
41 
44  inline int status() const
46  {
47  return status_;
48  }
50  inline void setStatus(int value)
51  {
52  status_ = value;
53  }
55  inline int pivots() const
56  {
57  return numberPivots_;
58  }
59 #if ABC_PARALLEL == 2
60  inline void setParallelMode(int value)
62  {
63  parallelMode_ = value;
64  };
65 #endif
66  inline void setPivots(int value)
68  {
69  numberPivots_ = value;
70  }
72  inline int numberSlacks() const
73  {
74  return numberSlacks_;
75  }
77  inline void setNumberSlacks(int value)
78  {
79  numberSlacks_ = value;
80  }
82  inline void setNumberRows(int value)
83  {
84  numberRows_ = value;
85  }
87  inline int numberRows() const
88  {
89  return numberRows_;
90  }
92  inline CoinSimplexInt numberDense() const
93  {
94  return numberDense_;
95  }
97  inline int numberGoodColumns() const
98  {
99  return numberGoodU_;
100  }
102  inline void relaxAccuracyCheck(double value)
103  {
104  relaxCheck_ = value;
105  }
106  inline double getAccuracyCheck() const
107  {
108  return relaxCheck_;
109  }
111  inline int maximumPivots() const
112  {
113  return maximumPivots_;
114  }
116  virtual void maximumPivots(int value);
117 
119  inline double pivotTolerance() const
120  {
121  return pivotTolerance_;
122  }
123  void pivotTolerance(double value);
125  inline double minimumPivotTolerance() const
126  {
127  return minimumPivotTolerance_;
128  }
129  void minimumPivotTolerance(double value);
131  {
132  return NULL;
133  }
135  inline double areaFactor() const
136  {
137  return areaFactor_;
138  }
139  inline void areaFactor(CoinSimplexDouble value)
140  {
141  areaFactor_ = value;
142  }
144  inline double zeroTolerance() const
145  {
146  return zeroTolerance_;
147  }
148  void zeroTolerance(double value);
150  virtual CoinFactorizationDouble *elements() const;
152  virtual int *pivotRow() const;
154  virtual CoinFactorizationDouble *workArea() const;
156  virtual int *intWorkArea() const;
158  virtual int *numberInRow() const;
160  virtual int *numberInColumn() const;
162  virtual CoinBigIndex *starts() const;
164  virtual int *permuteBack() const;
166  virtual void goSparse() {}
167 #ifndef NDEBUG
168  virtual inline void checkMarkArrays() const
169  {
170  }
171 #endif
172 
176  inline int solveMode() const
177  {
178  return solveMode_;
179  }
184  inline void setSolveMode(int value)
185  {
186  solveMode_ = value;
187  }
189  virtual bool wantsTableauColumn() const;
194  virtual void setUsefulInformation(const int *info, int whereFrom);
196  virtual void clearArrays() {}
198 
200  virtual int *indices() const = 0;
203  virtual int *permute() const = 0;
205  virtual int *pivotColumn() const;
207  virtual int numberElements() const = 0;
209 
211  virtual void getAreas(int numberRows,
213  int numberColumns,
214  CoinBigIndex maximumL,
215  CoinBigIndex maximumU)
216  = 0;
217 
219  virtual void preProcess() = 0;
225  virtual int factor(AbcSimplex *model) = 0;
226 #ifdef EARLY_FACTORIZE
227  virtual int factorize(AbcSimplex * /*model*/, CoinIndexedVector & /*stuff*/)
229  {
230  return -2;
231  }
232 #endif
233  virtual void postProcess(const int *sequence, int *pivotVariable) = 0;
236  virtual void makeNonSingular(int *sequence) = 0;
238 
241 #if 0
242 
246  virtual int checkReplace ( CoinIndexedVector * /*regionSparse*/,
247  int /*pivotRow*/,
248  double & /*pivotCheck*/,
249  double /*acceptablePivot = 1.0e-8*/)
250  {return 0;}
255  virtual int replaceColumn ( CoinIndexedVector * regionSparse,
256  int pivotRow,
257  double pivotCheck ,
258  bool skipBtranU=false,
259  double acceptablePivot=1.0e-8)=0;
260 #endif
261 #ifdef EARLY_FACTORIZE
262  virtual int replaceColumns(const AbcSimplex * /*model*/,
264  CoinIndexedVector & /*stuff*/,
265  int /*firstPivot*/, int /*lastPivot*/, bool /*cleanUp*/)
266  {
267  return -1;
268  }
269 #endif
270 #ifdef ABC_LONG_FACTORIZATION
271  virtual void clearHiddenArrays() {}
273 #endif
274 
278  virtual
279 #ifdef ABC_LONG_FACTORIZATION
280  long
281 #endif
282  double
284  int /*pivotRow*/)
285  {
286  return 0.0;
287  }
288  virtual
289 #ifdef ABC_LONG_FACTORIZATION
290  long
291 #endif
292  double
294  CoinIndexedVector * /*partialUpdate*/,
295  int /*pivotRow*/)
296  {
297  return 0.0;
298  }
299  virtual void checkReplacePart1a(CoinIndexedVector * /* regionSparse */,
300  int /*pivotRow*/)
301  {
302  }
303  virtual double checkReplacePart1b(CoinIndexedVector * /*regionSparse*/,
304  int /*pivotRow*/)
305  {
306  return 0.0;
307  }
310  virtual int checkReplacePart2(int pivotRow,
311  double btranAlpha,
312  double ftranAlpha,
313 #ifdef ABC_LONG_FACTORIZATION
314  long
315 #endif
316  double ftAlpha,
317  double acceptablePivot = 1.0e-8)
318  = 0;
321  virtual void replaceColumnPart3(const AbcSimplex *model,
322  CoinIndexedVector *regionSparse,
323  CoinIndexedVector *tableauColumn,
324  int pivotRow,
325 #ifdef ABC_LONG_FACTORIZATION
326  long
327 #endif
328  double alpha)
329  = 0;
332  virtual void replaceColumnPart3(const AbcSimplex *model,
333  CoinIndexedVector *regionSparse,
334  CoinIndexedVector *tableauColumn,
335  CoinIndexedVector *partialUpdate,
336  int pivotRow,
337 #ifdef ABC_LONG_FACTORIZATION
338  long
339 #endif
340  double alpha)
341  = 0;
343 
351  virtual int updateColumnFT(CoinIndexedVector &regionSparse) = 0;
352  virtual int updateColumnFTPart1(CoinIndexedVector &regionSparse) = 0;
353  virtual void updateColumnFTPart2(CoinIndexedVector &regionSparse) = 0;
354  virtual void updateColumnFT(CoinIndexedVector &regionSparseFT,
355  CoinIndexedVector &partialUpdate,
356  int which)
357  = 0;
360  virtual int updateColumn(CoinIndexedVector &regionSparse) const = 0;
362  virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT,
363  CoinIndexedVector &regionOther)
364  = 0;
367  virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const = 0;
369  virtual void updateFullColumn(CoinIndexedVector &regionSparse) const = 0;
372  virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const = 0;
374  virtual void updateWeights(CoinIndexedVector &regionSparse) const = 0;
376  virtual void updateColumnCpu(CoinIndexedVector &regionSparse, int whichCpu) const;
378  virtual void updateColumnTransposeCpu(CoinIndexedVector &regionSparse, int whichCpu) const;
380 
382 protected:
385  double pivotTolerance_;
390  double areaFactor_;
393  //#ifndef slackValue_
394 #define slackValue2_ 1.0
395  //#endif
397  double relaxCheck_;
413  int status_;
416 #if ABC_PARALLEL == 2
417  int parallelMode_;
418 #endif
419  int *pivotRow_;
434 };
443  friend void CoinAbcDenseFactorizationUnitTest(const std::string &mpsDir);
444 
445 public:
452 
454  virtual ~CoinAbcDenseFactorization();
458  virtual CoinAbcAnyFactorization *clone() const;
460 
463  virtual void getAreas(int numberRows,
465  int numberColumns,
466  CoinBigIndex maximumL,
467  CoinBigIndex maximumU);
468 
470  virtual void preProcess();
476  virtual int factor(AbcSimplex *model);
478  virtual void postProcess(const int *sequence, int *pivotVariable);
480  virtual void makeNonSingular(int *sequence);
482 
485  virtual inline int numberElements() const
487  {
489  }
491  double maximumCoefficient() const;
493 
496 
501  virtual int replaceColumn(CoinIndexedVector *regionSparse,
502  int pivotRow,
503  double pivotCheck,
504  bool skipBtranU = false,
505  double acceptablePivot = 1.0e-8);
508  virtual int checkReplacePart2(int pivotRow,
509  double btranAlpha,
510  double ftranAlpha,
511 #ifdef ABC_LONG_FACTORIZATION
512  long
513 #endif
514  double ftAlpha,
515  double acceptablePivot = 1.0e-8);
518  virtual void replaceColumnPart3(const AbcSimplex *model,
519  CoinIndexedVector *regionSparse,
520  CoinIndexedVector *tableauColumn,
521  int pivotRow,
522 #ifdef ABC_LONG_FACTORIZATION
523  long
524 #endif
525  double alpha);
528  virtual void replaceColumnPart3(const AbcSimplex *model,
529  CoinIndexedVector *regionSparse,
530  CoinIndexedVector *tableauColumn,
531  CoinIndexedVector * /*partialUpdate*/,
532  int pivotRow,
533 #ifdef ABC_LONG_FACTORIZATION
534  long
535 #endif
536  double alpha)
537  {
538  replaceColumnPart3(model, regionSparse, tableauColumn, pivotRow, alpha);
539  }
541 
549  virtual int updateColumnFT(CoinIndexedVector &regionSparse)
550  {
551  return updateColumn(regionSparse);
552  }
553  virtual int updateColumnFTPart1(CoinIndexedVector &regionSparse)
554  {
555  return updateColumn(regionSparse);
556  }
557  virtual void updateColumnFTPart2(CoinIndexedVector & /*regionSparse*/)
558  {
559  }
560  virtual void updateColumnFT(CoinIndexedVector &regionSparseFT, CoinIndexedVector & /*partialUpdate*/, int /*which*/)
561  {
562  updateColumnFT(regionSparseFT);
563  }
566  virtual int updateColumn(CoinIndexedVector &regionSparse) const;
568  virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT,
569  CoinIndexedVector &regionOther);
572  virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const;
574  virtual void updateFullColumn(CoinIndexedVector &regionSparse) const
575  {
576  updateColumn(regionSparse);
577  }
580  virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const
581  {
582  updateColumnTranspose(regionSparse);
583  }
585  virtual void updateWeights(CoinIndexedVector &regionSparse) const;
587 
592  inline void clearArrays()
594  {
596  }
598  virtual inline int *indices() const
599  {
600  return reinterpret_cast< int * >(elements_ + numberRows_ * numberRows_);
601  }
603  virtual inline int *permute() const
604  {
605  return NULL; /*pivotRow_*/
606  ;
607  }
609 
611  void gutsOfDestructor();
613  void gutsOfInitialize();
615  void gutsOfCopy(const CoinAbcDenseFactorization &other);
616 
618 protected:
621  int checkPivot(double saveFromU, double oldPivot) const;
623 protected:
628 
631 
632 };
633 #endif
634 
635 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
636 */
virtual int factor(AbcSimplex *model)=0
Does most of factorization returning status 0 - OK -99 - needs more memory -1 - singular - use number...
int CoinBigIndex
virtual int * pivotColumn() const
Returns pivotColumn or permute.
virtual void getAreas(int numberRows, int numberColumns, CoinBigIndex maximumL, CoinBigIndex maximumU)
Gets space for a factorization.
virtual void makeNonSingular(int *sequence)
Makes a non-singular basis by replacing variables.
void gutsOfCopy(const CoinAbcDenseFactorization &other)
The real work of copy.
virtual void updateWeights(CoinIndexedVector &regionSparse) const
Updates one column for dual steepest edge weights (FTRAN)
int maximumPivots() const
Maximum number of pivots between factorizations.
void gutsOfDestructor()
The real work of desstructor.
double pivotTolerance() const
Pivot tolerance.
double CoinSimplexDouble
double zeroTolerance() const
Zero tolerance.
virtual int updateColumnFT(CoinIndexedVector &regionSparse)
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
virtual void getAreas(int numberRows, int numberColumns, CoinBigIndex maximumL, CoinBigIndex maximumU)=0
Gets space for a factorization.
int checkPivot(double saveFromU, double oldPivot) const
Returns accuracy status of replaceColumn returns 0=OK, 1=Probably OK, 2=singular. ...
Abstract base class which also has some scalars so can be used from Dense or Simp.
CoinSimplexInt numberDense() const
Number of dense rows after factorization.
virtual void updateColumnCpu(CoinIndexedVector &regionSparse, int whichCpu) const
Updates one column (FTRAN)
virtual void replaceColumnPart3(const AbcSimplex *model, CoinIndexedVector *regionSparse, CoinIndexedVector *tableauColumn, int pivotRow, double alpha)=0
Replaces one Column to basis, partial update already in U.
virtual void clearArrays()
Get rid of all memory.
virtual CoinAbcAnyFactorization * clone() const =0
Clone.
int numberRows() const
Number of Rows after factorization.
virtual CoinFactorizationDouble * pivotRegion() const
Returns status.
virtual int * permute() const
Returns permute in.
virtual void postProcess(const int *sequence, int *pivotVariable)=0
Does post processing on valid factorization - putting variables on correct rows.
void setNumberSlacks(int value)
Sets number of slacks.
CoinAbcAnyFactorization()
Default constructor.
virtual CoinFactorizationDouble * elements() const
Returns array to put basis elements in.
virtual CoinAbcAnyFactorization * clone() const
Clone.
virtual int * permuteBack() const
Returns permute back.
int numberDense_
Number of dense rows in factorization.
virtual ~CoinAbcDenseFactorization()
Destructor.
Sparse Matrix Base Class.
virtual int checkReplacePart2(int pivotRow, double btranAlpha, double ftranAlpha, double ftAlpha, double acceptablePivot=1.0e-8)=0
Checks if can replace one Column to basis, returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots.
virtual void updateColumnFTPart2(CoinIndexedVector &)
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
virtual void makeNonSingular(int *sequence)=0
Makes a non-singular basis by replacing variables.
This deals with Factorization and Updates This is a simple dense version so other people can write a ...
int numberRows_
Number of Rows in factorization.
virtual double checkReplacePart1b(CoinIndexedVector *, int)
Checks if can replace one Column to basis, returns update alpha Fills in region for use later partial...
virtual void postProcess(const int *sequence, int *pivotVariable)
Does post processing on valid factorization - putting variables on correct rows.
int CoinSimplexInt
virtual void updateWeights(CoinIndexedVector &regionSparse) const =0
Updates one column for dual steepest edge weights (FTRAN)
int status_
Status of factorization.
virtual void preProcess()
PreProcesses column ordered copy of basis.
void setStatus(int value)
Sets status.
virtual void checkMarkArrays() const
Returns status.
virtual int updateColumnFT(CoinIndexedVector &regionSparse)=0
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
virtual int updateColumnFTPart1(CoinIndexedVector &regionSparse)=0
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
virtual int * numberInRow() const
Number of entries in each row.
double CoinFactorizationDouble
Definition: CoinTypes.hpp:57
int numberSlacks() const
Returns number of slacks.
virtual int updateColumn(CoinIndexedVector &regionSparse) const =0
This version has same effect as above with FTUpdate==false so number returned is always &gt;=0...
virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT, CoinIndexedVector &regionOther)
does FTRAN on two unpacked columns
virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const =0
Updates one column (BTRAN) from unpacked regionSparse.
double zeroTolerance_
Zero tolerance.
void areaFactor(CoinSimplexDouble value)
Returns status.
CoinSimplexInt maximumRowsAdjusted_
Use for array size to get multiple of 8.
void gutsOfInitialize()
The real work of constructor.
virtual void checkReplacePart1a(CoinIndexedVector *, int)
Checks if can replace one Column to basis, returns update alpha Fills in region for use later partial...
void relaxAccuracyCheck(double value)
Allows change of pivot accuracy check 1.0 == none &gt;1.0 relaxed.
int status() const
Returns status.
Indexed Vector.
void setSolveMode(int value)
Set solve mode e.g.
CoinAbcAnyFactorization & operator=(const CoinAbcAnyFactorization &other)
= copy
CoinFactorizationDouble * workArea_
Work area of numberRows_.
virtual int * intWorkArea() const
Returns int work area.
virtual int replaceColumn(CoinIndexedVector *regionSparse, int pivotRow, double pivotCheck, bool skipBtranU=false, double acceptablePivot=1.0e-8)
Replaces one Column to basis, returns 0=OK, 1=Probably OK, 2=singular, 3=no room If skipBtranU is fal...
double relaxCheck_
Relax check on accuracy in replaceColumn.
virtual double checkReplacePart1(CoinIndexedVector *, CoinIndexedVector *, int)
Checks if can replace one Column to basis, returns update alpha Fills in region for use later partial...
virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const =0
Updates one column (BTRAN) from unpacked regionSparse.
virtual void updateFullColumn(CoinIndexedVector &regionSparse) const
This version does FTRAN on array when indices not set up.
CoinAbcDenseFactorization()
Default constructor.
virtual int numberElements() const =0
Total number of elements in factorization.
virtual int numberElements() const
Total number of elements in factorization.
int pivots() const
Returns number of pivots since factorization.
virtual int updateColumnFTPart1(CoinIndexedVector &regionSparse)
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
int maximumRows_
Maximum rows ever (i.e. use to copy arrays etc)
virtual void replaceColumnPart3(const AbcSimplex *model, CoinIndexedVector *regionSparse, CoinIndexedVector *tableauColumn, int pivotRow, double alpha)
Replaces one Column to basis, partial update already in U.
virtual ~CoinAbcAnyFactorization()
Destructor.
virtual int factor(AbcSimplex *model)
Does most of factorization returning status 0 - OK -99 - needs more memory -1 - singular - use number...
virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT, CoinIndexedVector &regionOther)=0
does FTRAN on two unpacked columns
virtual CoinBigIndex * starts() const
Returns array to put basis starts in.
virtual int * pivotRow() const
Returns pivot row.
virtual CoinFactorizationDouble * workArea() const
Returns work area.
int solveMode() const
Get solve mode e.g.
virtual int updateColumn(CoinIndexedVector &regionSparse) const
This version has same effect as above with FTUpdate==false so number returned is always &gt;=0...
CoinBigIndex maximumSpace_
Maximum length of iterating area.
friend void CoinAbcDenseFactorizationUnitTest(const std::string &mpsDir)
virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const
Updates one column (BTRAN) from unpacked regionSparse.
virtual void goSparse()
Sees whether to go sparse.
virtual int * indices() const
Returns array to put basis indices in.
virtual int * indices() const =0
Returns array to put basis indices in.
virtual double checkReplacePart1(CoinIndexedVector *, int)
Checks if can replace one Column to basis, returns update alpha Fills in region for use later partial...
virtual int * permute() const =0
Returns permute in.
virtual void updateColumnFT(CoinIndexedVector &regionSparseFT, CoinIndexedVector &, int)
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
int numberGoodU_
Number factorized in U (not row singletons)
int numberGoodColumns() const
Number of good columns in factorization.
double pivotTolerance_
Pivot tolerance.
CoinFactorizationDouble * elements_
Elements of factorization and updates length is maxR*maxR+maxSpace will always be long enough so can ...
double areaFactor() const
Area factor.
double maximumCoefficient() const
Returns maximum absolute value in factorization.
virtual void updateColumnTransposeCpu(CoinIndexedVector &regionSparse, int whichCpu) const
Updates one column (BTRAN)
virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const
Updates one column (BTRAN) from unpacked regionSparse.
virtual int checkReplacePart2(int pivotRow, double btranAlpha, double ftranAlpha, double ftAlpha, double acceptablePivot=1.0e-8)
Checks if can replace one Column to basis, returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots.
CoinBigIndex factorElements_
Number of elements after factorization.
void setNumberRows(int value)
Set number of Rows after factorization.
virtual int * numberInColumn() const
Number of entries in each column.
virtual void updateFullColumn(CoinIndexedVector &regionSparse) const =0
This version does FTRAN on array when indices not set up.
virtual void replaceColumnPart3(const AbcSimplex *model, CoinIndexedVector *regionSparse, CoinIndexedVector *tableauColumn, CoinIndexedVector *, int pivotRow, double alpha)
Replaces one Column to basis, partial update in vector.
virtual void updateColumnFTPart2(CoinIndexedVector &regionSparse)=0
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
int numberPivots_
Number pivots since last factorization.
int maximumPivots_
Maximum number of pivots before factorization.
virtual bool wantsTableauColumn() const
Returns true if wants tableauColumn in replaceColumn.
void clearArrays()
Get rid of all memory.
double minimumPivotTolerance() const
Minimum pivot tolerance.
double minimumPivotTolerance_
Minimum pivot tolerance.
CoinAbcDenseFactorization & operator=(const CoinAbcDenseFactorization &other)
= copy
void setPivots(int value)
Sets number of pivots since factorization.
virtual void setUsefulInformation(const int *info, int whereFrom)
Useful information for factorization 0 - iteration number whereFrom is 0 for factorize and 1 for repl...
double getAccuracyCheck() const
Returns status.
virtual void preProcess()=0
PreProcesses column ordered copy of basis.