Clp  1.16.10
CoinAbcDenseFactorization.hpp
Go to the documentation of this file.
1 /* $Id: CoinAbcDenseFactorization.hpp 1910 2013-01-27 02:00:13Z stefan $ */
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 /*
8  Authors
9 
10  John Forrest
11 
12  */
13 #ifndef CoinAbcDenseFactorization_H
14 #define CoinAbcDenseFactorization_H
15 
16 #include <iostream>
17 #include <string>
18 #include <cassert>
19 #include "CoinTypes.hpp"
20 #include "CoinAbcCommon.hpp"
21 #include "CoinIndexedVector.hpp"
22 class CoinPackedMatrix;
25 
26 public:
27 
34 
36  virtual ~CoinAbcAnyFactorization ( );
39 
41  virtual CoinAbcAnyFactorization * clone() const = 0;
43 
46  inline int status ( ) const {
48  return status_;
49  }
51  inline void setStatus ( int value)
52  { status_=value; }
54  inline int pivots ( ) const {
55  return numberPivots_;
56  }
57 #if ABC_PARALLEL==2
58  inline void setParallelMode(int value)
60  {parallelMode_=value;};
61 #endif
62  inline void setPivots ( int value )
64  { numberPivots_=value; }
66  inline int numberSlacks ( ) const {
67  return numberSlacks_;
68  }
70  inline void setNumberSlacks ( int value )
71  { numberSlacks_=value; }
73  inline void setNumberRows(int value)
74  { numberRows_ = value; }
76  inline int numberRows ( ) const {
77  return numberRows_;
78  }
80  inline CoinSimplexInt numberDense ( ) const {
81  return numberDense_;
82  }
84  inline int numberGoodColumns ( ) const {
85  return numberGoodU_;
86  }
88  inline void relaxAccuracyCheck(double value)
89  { relaxCheck_ = value;}
90  inline double getAccuracyCheck() const
91  { return relaxCheck_;}
93  inline int maximumPivots ( ) const {
94  return maximumPivots_ ;
95  }
97  virtual void maximumPivots ( int value );
98 
100  inline double pivotTolerance ( ) const {
101  return pivotTolerance_ ;
102  }
103  void pivotTolerance ( double value );
105  inline double minimumPivotTolerance ( ) const {
106  return minimumPivotTolerance_ ;
107  }
108  void minimumPivotTolerance ( double value );
109  virtual CoinFactorizationDouble * pivotRegion() const
110  { return NULL;}
112  inline double areaFactor ( ) const {
113  return areaFactor_ ;
114  }
115  inline void areaFactor ( CoinSimplexDouble value ) {
116  areaFactor_=value;
117  }
119  inline double zeroTolerance ( ) const {
120  return zeroTolerance_ ;
121  }
122  void zeroTolerance ( double value );
124  virtual CoinFactorizationDouble * elements() const;
126  virtual int * pivotRow() const;
128  virtual CoinFactorizationDouble * workArea() const;
130  virtual int * intWorkArea() const;
132  virtual int * numberInRow() const;
134  virtual int * numberInColumn() const;
136  virtual CoinBigIndex * starts() const;
138  virtual int * permuteBack() const;
140  virtual void goSparse() {}
141 #ifndef NDEBUG
142  virtual inline void checkMarkArrays() const {}
143 #endif
144 
148  inline int solveMode() const
149  { return solveMode_ ;}
154  inline void setSolveMode(int value)
155  { solveMode_ = value;}
157  virtual bool wantsTableauColumn() const;
162  virtual void setUsefulInformation(const int * info,int whereFrom);
164  virtual void clearArrays() {}
166 
168  virtual int * indices() const = 0;
171  virtual int * permute() const = 0;
173  virtual int * pivotColumn() const;
175  virtual int numberElements ( ) const = 0;
177 
179  virtual void getAreas ( int numberRows,
181  int numberColumns,
182  CoinBigIndex maximumL,
183  CoinBigIndex maximumU ) = 0;
184 
186  virtual void preProcess ( ) = 0;
192  virtual int factor (AbcSimplex * model) = 0;
193 #ifdef EARLY_FACTORIZE
194  virtual int factorize (AbcSimplex * /*model*/, CoinIndexedVector & /*stuff*/)
196  { return -2;}
197 #endif
198  virtual void postProcess(const int * sequence, int * pivotVariable) = 0;
201  virtual void makeNonSingular(int * sequence) = 0;
203 
206 #if 0
207 
211  virtual int checkReplace ( CoinIndexedVector * /*regionSparse*/,
212  int /*pivotRow*/,
213  double & /*pivotCheck*/,
214  double /*acceptablePivot = 1.0e-8*/)
215  {return 0;}
220  virtual int replaceColumn ( CoinIndexedVector * regionSparse,
221  int pivotRow,
222  double pivotCheck ,
223  bool skipBtranU=false,
224  double acceptablePivot=1.0e-8)=0;
225 #endif
226 #ifdef EARLY_FACTORIZE
227  virtual int replaceColumns ( const AbcSimplex * /*model*/,
229  CoinIndexedVector & /*stuff*/,
230  int /*firstPivot*/,int /*lastPivot*/,bool /*cleanUp*/)
231  { return -1;}
232 #endif
233 #ifdef ABC_LONG_FACTORIZATION
234  virtual void clearHiddenArrays() {}
236 #endif
237 
241  virtual
242 #ifdef ABC_LONG_FACTORIZATION
243  long
244 #endif
245  double checkReplacePart1 ( CoinIndexedVector * /*regionSparse*/,
246  int /*pivotRow*/)
247  {return 0.0;}
248  virtual
249 #ifdef ABC_LONG_FACTORIZATION
250  long
251 #endif
252  double checkReplacePart1 ( CoinIndexedVector * /*regionSparse*/,
253  CoinIndexedVector * /*partialUpdate*/,
254  int /*pivotRow*/)
255  {return 0.0;}
256  virtual void checkReplacePart1a ( CoinIndexedVector * /* regionSparse */,
257  int /*pivotRow*/)
258  {}
259  virtual double checkReplacePart1b (CoinIndexedVector * /*regionSparse*/,
260  int /*pivotRow*/)
261  {return 0.0;}
264  virtual int checkReplacePart2 ( int pivotRow,
265  double btranAlpha,
266  double ftranAlpha,
267 #ifdef ABC_LONG_FACTORIZATION
268  long
269 #endif
270  double ftAlpha,
271  double acceptablePivot = 1.0e-8) = 0;
274  virtual void replaceColumnPart3 ( const AbcSimplex * model,
275  CoinIndexedVector * regionSparse,
276  CoinIndexedVector * tableauColumn,
277  int pivotRow,
278 #ifdef ABC_LONG_FACTORIZATION
279  long
280 #endif
281  double alpha ) = 0;
284  virtual void replaceColumnPart3 ( const AbcSimplex * model,
285  CoinIndexedVector * regionSparse,
286  CoinIndexedVector * tableauColumn,
287  CoinIndexedVector * partialUpdate,
288  int pivotRow,
289 #ifdef ABC_LONG_FACTORIZATION
290  long
291 #endif
292  double alpha )=0;
294 
302  virtual int updateColumnFT ( CoinIndexedVector & regionSparse) = 0;
303  virtual int updateColumnFTPart1 ( CoinIndexedVector & regionSparse) = 0;
304  virtual void updateColumnFTPart2 ( CoinIndexedVector & regionSparse) = 0;
305  virtual void updateColumnFT ( CoinIndexedVector & regionSparseFT,
306  CoinIndexedVector & partialUpdate,
307  int which)=0;
310  virtual int updateColumn ( CoinIndexedVector & regionSparse) const = 0;
312  virtual int updateTwoColumnsFT(CoinIndexedVector & regionFT,
313  CoinIndexedVector & regionOther) = 0;
316  virtual int updateColumnTranspose ( CoinIndexedVector & regionSparse) const = 0;
318  virtual void updateFullColumn ( CoinIndexedVector & regionSparse) const = 0;
321  virtual void updateFullColumnTranspose ( CoinIndexedVector & regionSparse) const = 0;
323  virtual void updateWeights ( CoinIndexedVector & regionSparse) const=0;
325  virtual void updateColumnCpu ( CoinIndexedVector & regionSparse,int whichCpu) const;
327  virtual void updateColumnTransposeCpu ( CoinIndexedVector & regionSparse,int whichCpu) const;
329 
331 protected:
332 
335  double pivotTolerance_;
340  double areaFactor_;
343  //#ifndef slackValue_
344 #define slackValue2_ 1.0
345  //#endif
347  double relaxCheck_;
349  CoinBigIndex factorElements_;
363  int status_;
366 #if ABC_PARALLEL==2
367  int parallelMode_;
368 #endif
369  int * pivotRow_;
375  CoinFactorizationDouble * elements_;
377  CoinFactorizationDouble * workArea_;
384 };
395  friend void CoinAbcDenseFactorizationUnitTest( const std::string & mpsDir );
396 
397 public:
398 
405 
407  virtual ~CoinAbcDenseFactorization ( );
411  virtual CoinAbcAnyFactorization * clone() const ;
413 
416  virtual void getAreas ( int numberRows,
418  int numberColumns,
419  CoinBigIndex maximumL,
420  CoinBigIndex maximumU );
421 
423  virtual void preProcess ( );
429  virtual int factor (AbcSimplex * model);
431  virtual void postProcess(const int * sequence, int * pivotVariable);
433  virtual void makeNonSingular(int * sequence);
435 
438  virtual inline int numberElements ( ) const {
441  }
443  double maximumCoefficient() const;
445 
448 
453  virtual int replaceColumn ( CoinIndexedVector * regionSparse,
454  int pivotRow,
455  double pivotCheck ,
456  bool skipBtranU=false,
457  double acceptablePivot=1.0e-8);
460  virtual int checkReplacePart2 ( int pivotRow,
461  double btranAlpha,
462  double ftranAlpha,
463 #ifdef ABC_LONG_FACTORIZATION
464  long
465 #endif
466  double ftAlpha,
467  double acceptablePivot = 1.0e-8) ;
470  virtual void replaceColumnPart3 ( const AbcSimplex * model,
471  CoinIndexedVector * regionSparse,
472  CoinIndexedVector * tableauColumn,
473  int pivotRow,
474 #ifdef ABC_LONG_FACTORIZATION
475  long
476 #endif
477  double alpha );
480  virtual void replaceColumnPart3 ( const AbcSimplex * model,
481  CoinIndexedVector * regionSparse,
482  CoinIndexedVector * tableauColumn,
483  CoinIndexedVector * /*partialUpdate*/,
484  int pivotRow,
485 #ifdef ABC_LONG_FACTORIZATION
486  long
487 #endif
488  double alpha )
489  { replaceColumnPart3(model,regionSparse,tableauColumn,pivotRow,alpha);}
491 
499  virtual int updateColumnFT ( CoinIndexedVector & regionSparse)
500  {return updateColumn(regionSparse);}
501  virtual int updateColumnFTPart1 ( CoinIndexedVector & regionSparse)
502  {return updateColumn(regionSparse);}
503  virtual void updateColumnFTPart2 ( CoinIndexedVector & /*regionSparse*/)
504  {}
505  virtual void updateColumnFT ( CoinIndexedVector & regionSparseFT,CoinIndexedVector & /*partialUpdate*/,int /*which*/)
506  { updateColumnFT(regionSparseFT);}
509  virtual int updateColumn ( CoinIndexedVector & regionSparse) const;
511  virtual int updateTwoColumnsFT(CoinIndexedVector & regionFT,
512  CoinIndexedVector & regionOther);
515  virtual int updateColumnTranspose ( CoinIndexedVector & regionSparse) const;
517  virtual void updateFullColumn ( CoinIndexedVector & regionSparse) const
518  {updateColumn(regionSparse);}
521  virtual void updateFullColumnTranspose ( CoinIndexedVector & regionSparse) const
522  {updateColumnTranspose(regionSparse);}
524  virtual void updateWeights ( CoinIndexedVector & regionSparse) const;
526 
531  inline void clearArrays()
533  { gutsOfDestructor();}
535  virtual inline int * indices() const
536  { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
538  virtual inline int * permute() const
539  { return NULL;/*pivotRow_*/;}
541 
543  void gutsOfDestructor();
545  void gutsOfInitialize();
547  void gutsOfCopy(const CoinAbcDenseFactorization &other);
548 
550 protected:
553  int checkPivot(double saveFromU, double oldPivot) const;
555 protected:
557  CoinBigIndex maximumSpace_;
560 
563 
564 };
565 #endif
virtual void updateColumnTransposeCpu(CoinIndexedVector &regionSparse, int whichCpu) const
Updates one column (BTRAN)
virtual void makeNonSingular(int *sequence)=0
Makes a non-singular basis by replacing variables.
virtual CoinFactorizationDouble * elements() const
Returns array to put basis elements in.
CoinSimplexInt maximumRowsAdjusted_
Use for array size to get multiple of 8.
virtual int factor(AbcSimplex *model)
Does most of factorization returning status 0 - OK -99 - needs more memory -1 - singular - use number...
virtual int updateColumn(CoinIndexedVector &regionSparse) const
This version has same effect as above with FTUpdate==false so number returned is always >=0...
virtual int factor(AbcSimplex *model)=0
Does most of factorization returning status 0 - OK -99 - needs more memory -1 - singular - use number...
int numberRows_
Number of Rows in factorization.
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...
virtual CoinAbcAnyFactorization * clone() const
Clone.
CoinFactorizationDouble * elements_
Elements of factorization and updates length is maxR*maxR+maxSpace will always be long enough so can ...
virtual void preProcess()
PreProcesses column ordered copy of basis.
double maximumCoefficient() const
Returns maximum absolute value in factorization.
virtual double checkReplacePart1(CoinIndexedVector *, int)
Checks if can replace one Column to basis, returns update alpha Fills in region for use later partial...
virtual void replaceColumnPart3(const AbcSimplex *model, CoinIndexedVector *regionSparse, CoinIndexedVector *tableauColumn, int pivotRow, double alpha)
Replaces one Column to basis, partial update already in U.
void areaFactor(CoinSimplexDouble value)
virtual ~CoinAbcAnyFactorization()
Destructor.
Abstract base class which also has some scalars so can be used from Dense or Simp.
virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const =0
Updates one column (BTRAN) from unpacked regionSparse.
virtual int updateColumnFTPart1(CoinIndexedVector &regionSparse)=0
virtual int * pivotRow() const
Returns pivot row.
int numberPivots_
Number pivots since last factorization.
int numberSlacks() const
Returns number of slacks.
virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const =0
Updates one column (BTRAN) from unpacked regionSparse.
virtual void updateColumnFTPart2(CoinIndexedVector &)
CoinSimplexInt numberDense() const
Number of dense rows after factorization.
CoinAbcAnyFactorization()
Default constructor.
virtual void updateFullColumn(CoinIndexedVector &regionSparse) const =0
This version does FTRAN on array when indices not set up.
double relaxCheck_
Relax check on accuracy in replaceColumn.
int maximumRows_
Maximum rows ever (i.e. use to copy arrays etc)
virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT, CoinIndexedVector &regionOther)=0
does FTRAN on two unpacked columns
void gutsOfInitialize()
The real work of constructor.
virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT, CoinIndexedVector &regionOther)
does FTRAN on two unpacked columns
virtual int * permute() const
Returns permute in.
CoinBigIndex maximumSpace_
Maximum length of iterating area.
int solveMode() const
Get solve mode e.g.
double CoinSimplexDouble
void setNumberSlacks(int value)
Sets number of slacks.
virtual int updateColumnFT(CoinIndexedVector &regionSparse)=0
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
virtual int * permuteBack() const
Returns permute back.
virtual int updateColumnFTPart1(CoinIndexedVector &regionSparse)
int status() const
Returns status.
CoinAbcDenseFactorization()
Default constructor.
double pivotTolerance() const
Pivot tolerance.
CoinFactorizationDouble * workArea_
Work area of numberRows_.
virtual void postProcess(const int *sequence, int *pivotVariable)
Does post processing on valid factorization - putting variables on correct rows.
This deals with Factorization and Updates This is a simple dense version so other people can write a ...
virtual int * pivotColumn() const
Returns pivotColumn or permute.
int numberGoodU_
Number factorized in U (not row singletons)
virtual CoinFactorizationDouble * workArea() const
Returns work area.
int checkPivot(double saveFromU, double oldPivot) const
Returns accuracy status of replaceColumn returns 0=OK, 1=Probably OK, 2=singular. ...
virtual void makeNonSingular(int *sequence)
Makes a non-singular basis by replacing variables.
int maximumPivots_
Maximum number of pivots before factorization.
virtual int * numberInColumn() const
Number of entries in each column.
virtual CoinAbcAnyFactorization * clone() const =0
Clone.
virtual void setUsefulInformation(const int *info, int whereFrom)
Useful information for factorization 0 - iteration number whereFrom is 0 for factorize and 1 for repl...
virtual int * numberInRow() const
Number of entries in each row.
virtual void updateColumnCpu(CoinIndexedVector &regionSparse, int whichCpu) const
Updates one column (FTRAN)
void setNumberRows(int value)
Set number of Rows after factorization.
virtual void updateFullColumn(CoinIndexedVector &regionSparse) const
This version does FTRAN on array when indices not set up.
void setStatus(int value)
Sets status.
virtual double checkReplacePart1(CoinIndexedVector *, CoinIndexedVector *, int)
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 int * indices() const =0
Returns array to put basis indices in.
int numberDense_
Number of dense rows in factorization.
CoinAbcAnyFactorization & operator=(const CoinAbcAnyFactorization &other)
= copy
virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const
Updates one column (BTRAN) from unpacked regionSparse.
virtual int updateColumn(CoinIndexedVector &regionSparse) const =0
This version has same effect as above with FTUpdate==false so number returned is always >=0...
virtual void checkReplacePart1a(CoinIndexedVector *, int)
virtual int numberElements() const =0
Total number of elements in factorization.
virtual int * indices() const
Returns array to put basis indices in.
virtual ~CoinAbcDenseFactorization()
Destructor.
void gutsOfCopy(const CoinAbcDenseFactorization &other)
The real work of copy.
int numberGoodColumns() const
Number of good columns in factorization.
virtual void postProcess(const int *sequence, int *pivotVariable)=0
Does post processing on valid factorization - putting variables on correct rows.
void setPivots(int value)
Sets number of pivots since factorization.
virtual void updateColumnFT(CoinIndexedVector &regionSparseFT, CoinIndexedVector &, int)
virtual void getAreas(int numberRows, int numberColumns, CoinBigIndex maximumL, CoinBigIndex maximumU)=0
Gets space for a factorization.
virtual void getAreas(int numberRows, int numberColumns, CoinBigIndex maximumL, CoinBigIndex maximumU)
Gets space for a factorization.
double zeroTolerance() const
Zero tolerance.
friend void CoinAbcDenseFactorizationUnitTest(const std::string &mpsDir)
virtual CoinBigIndex * starts() const
Returns array to put basis starts in.
virtual void updateWeights(CoinIndexedVector &regionSparse) const
Updates one column for dual steepest edge weights (FTRAN)
double minimumPivotTolerance() const
Minimum pivot tolerance.
virtual int * permute() const =0
Returns permute in.
virtual int updateColumnFT(CoinIndexedVector &regionSparse)
Updates one column (FTRAN) from unpacked regionSparse Tries to do FT update number returned is negati...
void relaxAccuracyCheck(double value)
Allows change of pivot accuracy check 1.0 == none >1.0 relaxed.
virtual double checkReplacePart1b(CoinIndexedVector *, int)
void clearArrays()
Get rid of all memory.
virtual void preProcess()=0
PreProcesses column ordered copy of basis.
virtual void updateWeights(CoinIndexedVector &regionSparse) const =0
Updates one column for dual steepest edge weights (FTRAN)
double pivotTolerance_
Pivot tolerance.
int pivots() const
Returns number of pivots since factorization.
virtual bool wantsTableauColumn() const
Returns true if wants tableauColumn in replaceColumn.
virtual void updateFullColumnTranspose(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)=0
Checks if can replace one Column to basis, returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots.
int CoinSimplexInt
void setSolveMode(int value)
Set solve mode e.g.
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.
int numberRows() const
Number of Rows after factorization.
CoinAbcDenseFactorization & operator=(const CoinAbcDenseFactorization &other)
= copy
double minimumPivotTolerance_
Minimum pivot tolerance.
void gutsOfDestructor()
The real work of desstructor.
int status_
Status of factorization.
virtual void clearArrays()
Get rid of all memory.
double zeroTolerance_
Zero tolerance.
double areaFactor() const
Area factor.
int maximumPivots() const
Maximum number of pivots between factorizations.
virtual int numberElements() const
Total number of elements in factorization.
virtual CoinFactorizationDouble * pivotRegion() const
virtual int * intWorkArea() const
Returns int work area.
virtual void goSparse()
Sees whether to go sparse.
virtual void updateColumnFTPart2(CoinIndexedVector &regionSparse)=0
CoinBigIndex factorElements_
Number of elements after factorization.
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.