source: trunk/Clp/src/CoinAbcDenseFactorization.hpp @ 2470

Last change on this file since 2470 was 2385, checked in by unxusr, 10 months ago

formatting

  • Property svn:keywords set to Id
File size: 18.1 KB
Line 
1/* $Id: CoinAbcDenseFactorization.hpp 2385 2019-01-06 19:43:06Z 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   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"
21class CoinPackedMatrix;
22/// Abstract base class which also has some scalars so can be used from Dense or Simp
23class CoinAbcAnyFactorization {
24
25public:
26  /**@name Constructors and destructor and copy */
27  //@{
28  /// Default constructor
29  CoinAbcAnyFactorization();
30  /// Copy constructor
31  CoinAbcAnyFactorization(const CoinAbcAnyFactorization &other);
32
33  /// Destructor
34  virtual ~CoinAbcAnyFactorization();
35  /// = copy
36  CoinAbcAnyFactorization &operator=(const CoinAbcAnyFactorization &other);
37
38  /// Clone
39  virtual CoinAbcAnyFactorization *clone() const = 0;
40  //@}
41
42  /**@name general stuff such as status */
43  //@{
44  /// Returns status
45  inline int status() const
46  {
47    return status_;
48  }
49  /// Sets status
50  inline void setStatus(int value)
51  {
52    status_ = value;
53  }
54  /// Returns number of pivots since factorization
55  inline int pivots() const
56  {
57    return numberPivots_;
58  }
59#if ABC_PARALLEL == 2
60  /// Says parallel
61  inline void setParallelMode(int value)
62  {
63    parallelMode_ = value;
64  };
65#endif
66  /// Sets number of pivots since factorization
67  inline void setPivots(int value)
68  {
69    numberPivots_ = value;
70  }
71  /// Returns number of slacks
72  inline int numberSlacks() const
73  {
74    return numberSlacks_;
75  }
76  /// Sets number of slacks
77  inline void setNumberSlacks(int value)
78  {
79    numberSlacks_ = value;
80  }
81  /// Set number of Rows after factorization
82  inline void setNumberRows(int value)
83  {
84    numberRows_ = value;
85  }
86  /// Number of Rows after factorization
87  inline int numberRows() const
88  {
89    return numberRows_;
90  }
91  /// Number of dense rows after factorization
92  inline CoinSimplexInt numberDense() const
93  {
94    return numberDense_;
95  }
96  /// Number of good columns in factorization
97  inline int numberGoodColumns() const
98  {
99    return numberGoodU_;
100  }
101  /// Allows change of pivot accuracy check 1.0 == none >1.0 relaxed
102  inline void relaxAccuracyCheck(double value)
103  {
104    relaxCheck_ = value;
105  }
106  inline double getAccuracyCheck() const
107  {
108    return relaxCheck_;
109  }
110  /// Maximum number of pivots between factorizations
111  inline int maximumPivots() const
112  {
113    return maximumPivots_;
114  }
115  /// Set maximum pivots
116  virtual void maximumPivots(int value);
117
118  /// Pivot tolerance
119  inline double pivotTolerance() const
120  {
121    return pivotTolerance_;
122  }
123  void pivotTolerance(double value);
124  /// Minimum pivot tolerance
125  inline double minimumPivotTolerance() const
126  {
127    return minimumPivotTolerance_;
128  }
129  void minimumPivotTolerance(double value);
130  virtual CoinFactorizationDouble *pivotRegion() const
131  {
132    return NULL;
133  }
134  /// Area factor
135  inline double areaFactor() const
136  {
137    return areaFactor_;
138  }
139  inline void areaFactor(CoinSimplexDouble value)
140  {
141    areaFactor_ = value;
142  }
143  /// Zero tolerance
144  inline double zeroTolerance() const
145  {
146    return zeroTolerance_;
147  }
148  void zeroTolerance(double value);
149  /// Returns array to put basis elements in
150  virtual CoinFactorizationDouble *elements() const;
151  /// Returns pivot row
152  virtual int *pivotRow() const;
153  /// Returns work area
154  virtual CoinFactorizationDouble *workArea() const;
155  /// Returns int work area
156  virtual int *intWorkArea() const;
157  /// Number of entries in each row
158  virtual int *numberInRow() const;
159  /// Number of entries in each column
160  virtual int *numberInColumn() const;
161  /// Returns array to put basis starts in
162  virtual CoinBigIndex *starts() const;
163  /// Returns permute back
164  virtual int *permuteBack() const;
165  /// Sees whether to go sparse
166  virtual void goSparse() {}
167#ifndef NDEBUG
168  virtual inline void checkMarkArrays() const
169  {
170  }
171#endif
172  /** Get solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
173      If 4 set then values pass
174      if 8 set then has iterated
175  */
176  inline int solveMode() const
177  {
178    return solveMode_;
179  }
180  /** Set solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
181      If 4 set then values pass
182      if 8 set then has iterated
183  */
184  inline void setSolveMode(int value)
185  {
186    solveMode_ = value;
187  }
188  /// Returns true if wants tableauColumn in replaceColumn
189  virtual bool wantsTableauColumn() const;
190  /** Useful information for factorization
191      0 - iteration number
192      whereFrom is 0 for factorize and 1 for replaceColumn
193  */
194  virtual void setUsefulInformation(const int *info, int whereFrom);
195  /// Get rid of all memory
196  virtual void clearArrays() {}
197  //@}
198  /**@name virtual general stuff such as permutation */
199  //@{
200  /// Returns array to put basis indices in
201  virtual int *indices() const = 0;
202  /// Returns permute in
203  virtual int *permute() const = 0;
204  /// Returns pivotColumn or permute
205  virtual int *pivotColumn() const;
206  /// Total number of elements in factorization
207  virtual int numberElements() const = 0;
208  //@}
209  /**@name Do factorization - public */
210  //@{
211  /// Gets space for a factorization
212  virtual void getAreas(int numberRows,
213    int numberColumns,
214    CoinBigIndex maximumL,
215    CoinBigIndex maximumU)
216    = 0;
217
218  /// PreProcesses column ordered copy of basis
219  virtual void preProcess() = 0;
220  /** Does most of factorization returning status
221      0 - OK
222      -99 - needs more memory
223      -1 - singular - use numberGoodColumns and redo
224  */
225  virtual int factor(AbcSimplex *model) = 0;
226#ifdef EARLY_FACTORIZE
227  /// Returns -2 if can't, -1 if singular, -99 memory, 0 OK
228  virtual int factorize(AbcSimplex * /*model*/, CoinIndexedVector & /*stuff*/)
229  {
230    return -2;
231  }
232#endif
233  /// Does post processing on valid factorization - putting variables on correct rows
234  virtual void postProcess(const int *sequence, int *pivotVariable) = 0;
235  /// Makes a non-singular basis by replacing variables
236  virtual void makeNonSingular(int *sequence) = 0;
237  //@}
238
239  /**@name rank one updates which do exist */
240  //@{
241#if 0
242  /** Checks if can replace one Column to basis,
243      returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots
244      Fills in region for use later
245      partial update already in U */
246  virtual int checkReplace ( CoinIndexedVector * /*regionSparse*/,
247                             int /*pivotRow*/,
248                             double & /*pivotCheck*/,
249                             double /*acceptablePivot = 1.0e-8*/)
250  {return 0;}
251  /** Replaces one Column to basis,
252   returns 0=OK, 1=Probably OK, 2=singular, 3=no room
253      If skipBtranU is false will do btran part
254   partial update already in U */
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  /// 0 success, -1 can't +1 accuracy problems
263  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  /// Clear all hidden arrays
272  virtual void clearHiddenArrays() {}
273#endif
274  /** Checks if can replace one Column to basis,
275      returns update alpha
276      Fills in region for use later
277      partial update already in U */
278  virtual
279#ifdef ABC_LONG_FACTORIZATION
280    long
281#endif
282    double
283    checkReplacePart1(CoinIndexedVector * /*regionSparse*/,
284      int /*pivotRow*/)
285  {
286    return 0.0;
287  }
288  virtual
289#ifdef ABC_LONG_FACTORIZATION
290    long
291#endif
292    double
293    checkReplacePart1(CoinIndexedVector * /*regionSparse*/,
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  }
308  /** Checks if can replace one Column to basis,
309      returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots */
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;
319  /** Replaces one Column to basis,
320      partial update already in U */
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;
330  /** Replaces one Column to basis,
331      partial update in vector */
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;
342  //@}
343
344  /**@name various uses of factorization (return code number elements)
345   which user may want to know about */
346  //@{
347  /** Updates one column (FTRAN) from unpacked regionSparse
348      Tries to do FT update
349      number returned is negative if no room
350  */
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;
358  /** This version has same effect as above with FTUpdate==false
359      so number returned is always >=0 */
360  virtual int updateColumn(CoinIndexedVector &regionSparse) const = 0;
361  /// does FTRAN on two unpacked columns
362  virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT,
363    CoinIndexedVector &regionOther)
364    = 0;
365  /** Updates one column (BTRAN) from unpacked regionSparse
366  */
367  virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const = 0;
368  /** This version does FTRAN on array when indices not set up */
369  virtual void updateFullColumn(CoinIndexedVector &regionSparse) const = 0;
370  /** Updates one column (BTRAN) from unpacked regionSparse
371  */
372  virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const = 0;
373  /** Updates one column for dual steepest edge weights (FTRAN) */
374  virtual void updateWeights(CoinIndexedVector &regionSparse) const = 0;
375  /** Updates one column (FTRAN) */
376  virtual void updateColumnCpu(CoinIndexedVector &regionSparse, int whichCpu) const;
377  /** Updates one column (BTRAN) */
378  virtual void updateColumnTransposeCpu(CoinIndexedVector &regionSparse, int whichCpu) const;
379  //@}
380
381  ////////////////// data //////////////////
382protected:
383  /**@name data */
384  //@{
385  /// Pivot tolerance
386  double pivotTolerance_;
387  /// Minimum pivot tolerance
388  double minimumPivotTolerance_;
389  /// Area factor
390  double areaFactor_;
391  /// Zero tolerance
392  double zeroTolerance_;
393  //#ifndef slackValue_
394#define slackValue2_ 1.0
395  //#endif
396  /// Relax check on accuracy in replaceColumn
397  double relaxCheck_;
398  /// Number of elements after factorization
399  CoinBigIndex factorElements_;
400  /// Number of Rows in factorization
401  int numberRows_;
402  /// Number of dense rows in factorization
403  int numberDense_;
404  /// Number factorized in U (not row singletons)
405  int numberGoodU_;
406  /// Maximum number of pivots before factorization
407  int maximumPivots_;
408  /// Number pivots since last factorization
409  int numberPivots_;
410  /// Number slacks
411  int numberSlacks_;
412  /// Status of factorization
413  int status_;
414  /// Maximum rows ever (i.e. use to copy arrays etc)
415  int maximumRows_;
416#if ABC_PARALLEL == 2
417  int parallelMode_;
418#endif
419  /// Pivot row
420  int *pivotRow_;
421  /** Elements of factorization and updates
422      length is maxR*maxR+maxSpace
423      will always be long enough so can have nR*nR ints in maxSpace
424  */
425  CoinFactorizationDouble *elements_;
426  /// Work area of numberRows_
427  CoinFactorizationDouble *workArea_;
428  /** Solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
429      If 4 set then values pass
430      if 8 set then has iterated
431  */
432  int solveMode_;
433  //@}
434};
435/** This deals with Factorization and Updates
436    This is a simple dense version so other people can write a better one
437
438    I am assuming that 32 bits is enough for number of rows or columns, but CoinBigIndex
439    may be redefined to get 64 bits.
440 */
441
442class CoinAbcDenseFactorization : public CoinAbcAnyFactorization {
443  friend void CoinAbcDenseFactorizationUnitTest(const std::string &mpsDir);
444
445public:
446  /**@name Constructors and destructor and copy */
447  //@{
448  /// Default constructor
449  CoinAbcDenseFactorization();
450  /// Copy constructor
451  CoinAbcDenseFactorization(const CoinAbcDenseFactorization &other);
452
453  /// Destructor
454  virtual ~CoinAbcDenseFactorization();
455  /// = copy
456  CoinAbcDenseFactorization &operator=(const CoinAbcDenseFactorization &other);
457  /// Clone
458  virtual CoinAbcAnyFactorization *clone() const;
459  //@}
460
461  /**@name Do factorization - public */
462  //@{
463  /// Gets space for a factorization
464  virtual void getAreas(int numberRows,
465    int numberColumns,
466    CoinBigIndex maximumL,
467    CoinBigIndex maximumU);
468
469  /// PreProcesses column ordered copy of basis
470  virtual void preProcess();
471  /** Does most of factorization returning status
472      0 - OK
473      -99 - needs more memory
474      -1 - singular - use numberGoodColumns and redo
475  */
476  virtual int factor(AbcSimplex *model);
477  /// Does post processing on valid factorization - putting variables on correct rows
478  virtual void postProcess(const int *sequence, int *pivotVariable);
479  /// Makes a non-singular basis by replacing variables
480  virtual void makeNonSingular(int *sequence);
481  //@}
482
483  /**@name general stuff such as number of elements */
484  //@{
485  /// Total number of elements in factorization
486  virtual inline int numberElements() const
487  {
488    return numberRows_ * (numberRows_ + numberPivots_);
489  }
490  /// Returns maximum absolute value in factorization
491  double maximumCoefficient() const;
492  //@}
493
494  /**@name rank one updates which do exist */
495  //@{
496
497  /** Replaces one Column to basis,
498   returns 0=OK, 1=Probably OK, 2=singular, 3=no room
499      If skipBtranU is false will do btran part
500   partial update already in U */
501  virtual int replaceColumn(CoinIndexedVector *regionSparse,
502    int pivotRow,
503    double pivotCheck,
504    bool skipBtranU = false,
505    double acceptablePivot = 1.0e-8);
506  /** Checks if can replace one Column to basis,
507      returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots */
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);
516  /** Replaces one Column to basis,
517      partial update already in U */
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);
526  /** Replaces one Column to basis,
527      partial update in vector */
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  }
540  //@}
541
542  /**@name various uses of factorization (return code number elements)
543   which user may want to know about */
544  //@{
545  /** Updates one column (FTRAN) from unpacked regionSparse
546      Tries to do FT update
547      number returned is negative if no room
548  */
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  }
564  /** This version has same effect as above with FTUpdate==false
565      so number returned is always >=0 */
566  virtual int updateColumn(CoinIndexedVector &regionSparse) const;
567  /// does FTRAN on two unpacked columns
568  virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT,
569    CoinIndexedVector &regionOther);
570  /** Updates one column (BTRAN) from unpacked regionSparse
571  */
572  virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const;
573  /** This version does FTRAN on array when indices not set up */
574  virtual void updateFullColumn(CoinIndexedVector &regionSparse) const
575  {
576    updateColumn(regionSparse);
577  }
578  /** Updates one column (BTRAN) from unpacked regionSparse
579  */
580  virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const
581  {
582    updateColumnTranspose(regionSparse);
583  }
584  /** Updates one column for dual steepest edge weights (FTRAN) */
585  virtual void updateWeights(CoinIndexedVector &regionSparse) const;
586  //@}
587  /// *** Below this user may not want to know about
588
589  /**@name various uses of factorization
590   which user may not want to know about (left over from my LP code) */
591  //@{
592  /// Get rid of all memory
593  inline void clearArrays()
594  {
595    gutsOfDestructor();
596  }
597  /// Returns array to put basis indices in
598  virtual inline int *indices() const
599  {
600    return reinterpret_cast< int * >(elements_ + numberRows_ * numberRows_);
601  }
602  /// Returns permute in
603  virtual inline int *permute() const
604  {
605    return NULL; /*pivotRow_*/
606    ;
607  }
608  //@}
609
610  /// The real work of desstructor
611  void gutsOfDestructor();
612  /// The real work of constructor
613  void gutsOfInitialize();
614  /// The real work of copy
615  void gutsOfCopy(const CoinAbcDenseFactorization &other);
616
617  //@}
618protected:
619  /** Returns accuracy status of replaceColumn
620      returns 0=OK, 1=Probably OK, 2=singular */
621  int checkPivot(double saveFromU, double oldPivot) const;
622  ////////////////// data //////////////////
623protected:
624  /// Maximum length of iterating area
625  CoinBigIndex maximumSpace_;
626  /// Use for array size to get multiple of 8
627  CoinSimplexInt maximumRowsAdjusted_;
628
629  /**@name data */
630  //@{
631  //@}
632};
633#endif
634
635/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
636*/
Note: See TracBrowser for help on using the repository browser.