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

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

formatting

  • Property svn:keywords set to Id
File size: 18.1 KB
RevLine 
[1910]1/* $Id: CoinAbcDenseFactorization.hpp 2385 2019-01-06 19:43:06Z stefan $ */
[1878]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
[2385]29  CoinAbcAnyFactorization();
30  /// Copy constructor
31  CoinAbcAnyFactorization(const CoinAbcAnyFactorization &other);
32
[1878]33  /// Destructor
[2385]34  virtual ~CoinAbcAnyFactorization();
[1878]35  /// = copy
[2385]36  CoinAbcAnyFactorization &operator=(const CoinAbcAnyFactorization &other);
37
[1878]38  /// Clone
[2385]39  virtual CoinAbcAnyFactorization *clone() const = 0;
[1878]40  //@}
41
42  /**@name general stuff such as status */
[2385]43  //@{
[1878]44  /// Returns status
[2385]45  inline int status() const
46  {
[1878]47    return status_;
48  }
49  /// Sets status
[2385]50  inline void setStatus(int value)
51  {
52    status_ = value;
53  }
[1878]54  /// Returns number of pivots since factorization
[2385]55  inline int pivots() const
56  {
[1878]57    return numberPivots_;
58  }
[2385]59#if ABC_PARALLEL == 2
[1878]60  /// Says parallel
61  inline void setParallelMode(int value)
[2385]62  {
63    parallelMode_ = value;
64  };
[1878]65#endif
66  /// Sets number of pivots since factorization
[2385]67  inline void setPivots(int value)
68  {
69    numberPivots_ = value;
70  }
[1878]71  /// Returns number of slacks
[2385]72  inline int numberSlacks() const
73  {
[1878]74    return numberSlacks_;
75  }
76  /// Sets number of slacks
[2385]77  inline void setNumberSlacks(int value)
78  {
79    numberSlacks_ = value;
80  }
[1878]81  /// Set number of Rows after factorization
82  inline void setNumberRows(int value)
[2385]83  {
84    numberRows_ = value;
85  }
[1878]86  /// Number of Rows after factorization
[2385]87  inline int numberRows() const
88  {
[1878]89    return numberRows_;
90  }
91  /// Number of dense rows after factorization
[2385]92  inline CoinSimplexInt numberDense() const
93  {
[1878]94    return numberDense_;
95  }
96  /// Number of good columns in factorization
[2385]97  inline int numberGoodColumns() const
98  {
[1878]99    return numberGoodU_;
100  }
101  /// Allows change of pivot accuracy check 1.0 == none >1.0 relaxed
102  inline void relaxAccuracyCheck(double value)
[2385]103  {
104    relaxCheck_ = value;
105  }
[1878]106  inline double getAccuracyCheck() const
[2385]107  {
108    return relaxCheck_;
109  }
[1878]110  /// Maximum number of pivots between factorizations
[2385]111  inline int maximumPivots() const
112  {
113    return maximumPivots_;
[1878]114  }
115  /// Set maximum pivots
[2385]116  virtual void maximumPivots(int value);
[1878]117
118  /// Pivot tolerance
[2385]119  inline double pivotTolerance() const
120  {
121    return pivotTolerance_;
[1878]122  }
[2385]123  void pivotTolerance(double value);
[1878]124  /// Minimum pivot tolerance
[2385]125  inline double minimumPivotTolerance() const
126  {
127    return minimumPivotTolerance_;
[1878]128  }
[2385]129  void minimumPivotTolerance(double value);
130  virtual CoinFactorizationDouble *pivotRegion() const
131  {
132    return NULL;
133  }
[1878]134  /// Area factor
[2385]135  inline double areaFactor() const
136  {
137    return areaFactor_;
[1878]138  }
[2385]139  inline void areaFactor(CoinSimplexDouble value)
140  {
141    areaFactor_ = value;
[1878]142  }
143  /// Zero tolerance
[2385]144  inline double zeroTolerance() const
145  {
146    return zeroTolerance_;
[1878]147  }
[2385]148  void zeroTolerance(double value);
[1878]149  /// Returns array to put basis elements in
[2385]150  virtual CoinFactorizationDouble *elements() const;
151  /// Returns pivot row
152  virtual int *pivotRow() const;
[1878]153  /// Returns work area
[2385]154  virtual CoinFactorizationDouble *workArea() const;
[1878]155  /// Returns int work area
[2385]156  virtual int *intWorkArea() const;
[1878]157  /// Number of entries in each row
[2385]158  virtual int *numberInRow() const;
[1878]159  /// Number of entries in each column
[2385]160  virtual int *numberInColumn() const;
[1878]161  /// Returns array to put basis starts in
[2385]162  virtual CoinBigIndex *starts() const;
[1878]163  /// Returns permute back
[2385]164  virtual int *permuteBack() const;
[1878]165  /// Sees whether to go sparse
166  virtual void goSparse() {}
167#ifndef NDEBUG
[2385]168  virtual inline void checkMarkArrays() const
169  {
170  }
[1878]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
[2385]177  {
178    return solveMode_;
179  }
[1878]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)
[2385]185  {
186    solveMode_ = value;
187  }
[1878]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  */
[2385]194  virtual void setUsefulInformation(const int *info, int whereFrom);
[1878]195  /// Get rid of all memory
196  virtual void clearArrays() {}
197  //@}
198  /**@name virtual general stuff such as permutation */
[2385]199  //@{
[1878]200  /// Returns array to put basis indices in
[2385]201  virtual int *indices() const = 0;
[1878]202  /// Returns permute in
[2385]203  virtual int *permute() const = 0;
[1878]204  /// Returns pivotColumn or permute
[2385]205  virtual int *pivotColumn() const;
[1878]206  /// Total number of elements in factorization
[2385]207  virtual int numberElements() const = 0;
[1878]208  //@}
209  /**@name Do factorization - public */
210  //@{
211  /// Gets space for a factorization
[2385]212  virtual void getAreas(int numberRows,
213    int numberColumns,
214    CoinBigIndex maximumL,
215    CoinBigIndex maximumU)
216    = 0;
217
[1878]218  /// PreProcesses column ordered copy of basis
[2385]219  virtual void preProcess() = 0;
[1878]220  /** Does most of factorization returning status
221      0 - OK
222      -99 - needs more memory
223      -1 - singular - use numberGoodColumns and redo
224  */
[2385]225  virtual int factor(AbcSimplex *model) = 0;
[1878]226#ifdef EARLY_FACTORIZE
227  /// Returns -2 if can't, -1 if singular, -99 memory, 0 OK
[2385]228  virtual int factorize(AbcSimplex * /*model*/, CoinIndexedVector & /*stuff*/)
229  {
230    return -2;
231  }
[1878]232#endif
233  /// Does post processing on valid factorization - putting variables on correct rows
[2385]234  virtual void postProcess(const int *sequence, int *pivotVariable) = 0;
[1878]235  /// Makes a non-singular basis by replacing variables
[2385]236  virtual void makeNonSingular(int *sequence) = 0;
[1878]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
[2385]263  virtual int replaceColumns(const AbcSimplex * /*model*/,
264    CoinIndexedVector & /*stuff*/,
265    int /*firstPivot*/, int /*lastPivot*/, bool /*cleanUp*/)
266  {
267    return -1;
268  }
[1878]269#endif
[2385]270#ifdef ABC_LONG_FACTORIZATION
[1878]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 */
[2385]278  virtual
279#ifdef ABC_LONG_FACTORIZATION
280    long
[1878]281#endif
[2385]282    double
283    checkReplacePart1(CoinIndexedVector * /*regionSparse*/,
284      int /*pivotRow*/)
285  {
286    return 0.0;
287  }
288  virtual
289#ifdef ABC_LONG_FACTORIZATION
290    long
[1878]291#endif
[2385]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  }
[1878]308  /** Checks if can replace one Column to basis,
309      returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots */
[2385]310  virtual int checkReplacePart2(int pivotRow,
311    double btranAlpha,
312    double ftranAlpha,
313#ifdef ABC_LONG_FACTORIZATION
314    long
[1878]315#endif
[2385]316    double ftAlpha,
317    double acceptablePivot = 1.0e-8)
318    = 0;
[1878]319  /** Replaces one Column to basis,
320      partial update already in U */
[2385]321  virtual void replaceColumnPart3(const AbcSimplex *model,
322    CoinIndexedVector *regionSparse,
323    CoinIndexedVector *tableauColumn,
324    int pivotRow,
325#ifdef ABC_LONG_FACTORIZATION
326    long
[1878]327#endif
[2385]328    double alpha)
329    = 0;
[1878]330  /** Replaces one Column to basis,
331      partial update in vector */
[2385]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
[1878]339#endif
[2385]340    double alpha)
341    = 0;
[1878]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  */
[2385]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;
[1878]358  /** This version has same effect as above with FTUpdate==false
359      so number returned is always >=0 */
[2385]360  virtual int updateColumn(CoinIndexedVector &regionSparse) const = 0;
[1878]361  /// does FTRAN on two unpacked columns
[2385]362  virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT,
363    CoinIndexedVector &regionOther)
364    = 0;
[1878]365  /** Updates one column (BTRAN) from unpacked regionSparse
366  */
[2385]367  virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const = 0;
[1878]368  /** This version does FTRAN on array when indices not set up */
[2385]369  virtual void updateFullColumn(CoinIndexedVector &regionSparse) const = 0;
[1878]370  /** Updates one column (BTRAN) from unpacked regionSparse
371  */
[2385]372  virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const = 0;
[1878]373  /** Updates one column for dual steepest edge weights (FTRAN) */
[2385]374  virtual void updateWeights(CoinIndexedVector &regionSparse) const = 0;
[1878]375  /** Updates one column (FTRAN) */
[2385]376  virtual void updateColumnCpu(CoinIndexedVector &regionSparse, int whichCpu) const;
[1878]377  /** Updates one column (BTRAN) */
[2385]378  virtual void updateColumnTransposeCpu(CoinIndexedVector &regionSparse, int whichCpu) const;
[1878]379  //@}
380
[2385]381  ////////////////// data //////////////////
[1878]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_;
[2385]393  //#ifndef slackValue_
[1878]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_;
[2385]416#if ABC_PARALLEL == 2
[1878]417  int parallelMode_;
418#endif
[2385]419  /// Pivot row
420  int *pivotRow_;
[1878]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  */
[2385]425  CoinFactorizationDouble *elements_;
426  /// Work area of numberRows_
427  CoinFactorizationDouble *workArea_;
[1878]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 {
[2385]443  friend void CoinAbcDenseFactorizationUnitTest(const std::string &mpsDir);
[1878]444
445public:
446  /**@name Constructors and destructor and copy */
447  //@{
448  /// Default constructor
[2385]449  CoinAbcDenseFactorization();
450  /// Copy constructor
451  CoinAbcDenseFactorization(const CoinAbcDenseFactorization &other);
452
[1878]453  /// Destructor
[2385]454  virtual ~CoinAbcDenseFactorization();
[1878]455  /// = copy
[2385]456  CoinAbcDenseFactorization &operator=(const CoinAbcDenseFactorization &other);
[1878]457  /// Clone
[2385]458  virtual CoinAbcAnyFactorization *clone() const;
[1878]459  //@}
460
461  /**@name Do factorization - public */
462  //@{
463  /// Gets space for a factorization
[2385]464  virtual void getAreas(int numberRows,
465    int numberColumns,
466    CoinBigIndex maximumL,
467    CoinBigIndex maximumU);
468
[1878]469  /// PreProcesses column ordered copy of basis
[2385]470  virtual void preProcess();
[1878]471  /** Does most of factorization returning status
472      0 - OK
473      -99 - needs more memory
474      -1 - singular - use numberGoodColumns and redo
475  */
[2385]476  virtual int factor(AbcSimplex *model);
[1878]477  /// Does post processing on valid factorization - putting variables on correct rows
[2385]478  virtual void postProcess(const int *sequence, int *pivotVariable);
[1878]479  /// Makes a non-singular basis by replacing variables
[2385]480  virtual void makeNonSingular(int *sequence);
[1878]481  //@}
482
483  /**@name general stuff such as number of elements */
[2385]484  //@{
[1878]485  /// Total number of elements in factorization
[2385]486  virtual inline int numberElements() const
487  {
488    return numberRows_ * (numberRows_ + numberPivots_);
[1878]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 */
[2385]501  virtual int replaceColumn(CoinIndexedVector *regionSparse,
502    int pivotRow,
503    double pivotCheck,
504    bool skipBtranU = false,
505    double acceptablePivot = 1.0e-8);
[1878]506  /** Checks if can replace one Column to basis,
507      returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots */
[2385]508  virtual int checkReplacePart2(int pivotRow,
509    double btranAlpha,
510    double ftranAlpha,
511#ifdef ABC_LONG_FACTORIZATION
512    long
[1878]513#endif
[2385]514    double ftAlpha,
515    double acceptablePivot = 1.0e-8);
[1878]516  /** Replaces one Column to basis,
517      partial update already in U */
[2385]518  virtual void replaceColumnPart3(const AbcSimplex *model,
519    CoinIndexedVector *regionSparse,
520    CoinIndexedVector *tableauColumn,
521    int pivotRow,
522#ifdef ABC_LONG_FACTORIZATION
523    long
[1878]524#endif
[2385]525    double alpha);
[1878]526  /** Replaces one Column to basis,
527      partial update in vector */
[2385]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
[1878]535#endif
[2385]536    double alpha)
537  {
538    replaceColumnPart3(model, regionSparse, tableauColumn, pivotRow, alpha);
539  }
[1878]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  */
[2385]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  }
[1878]564  /** This version has same effect as above with FTUpdate==false
565      so number returned is always >=0 */
[2385]566  virtual int updateColumn(CoinIndexedVector &regionSparse) const;
[1878]567  /// does FTRAN on two unpacked columns
[2385]568  virtual int updateTwoColumnsFT(CoinIndexedVector &regionFT,
569    CoinIndexedVector &regionOther);
[1878]570  /** Updates one column (BTRAN) from unpacked regionSparse
571  */
[2385]572  virtual int updateColumnTranspose(CoinIndexedVector &regionSparse) const;
[1878]573  /** This version does FTRAN on array when indices not set up */
[2385]574  virtual void updateFullColumn(CoinIndexedVector &regionSparse) const
575  {
576    updateColumn(regionSparse);
577  }
[1878]578  /** Updates one column (BTRAN) from unpacked regionSparse
579  */
[2385]580  virtual void updateFullColumnTranspose(CoinIndexedVector &regionSparse) const
581  {
582    updateColumnTranspose(regionSparse);
583  }
[1878]584  /** Updates one column for dual steepest edge weights (FTRAN) */
[2385]585  virtual void updateWeights(CoinIndexedVector &regionSparse) const;
[1878]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()
[2385]594  {
595    gutsOfDestructor();
596  }
[1878]597  /// Returns array to put basis indices in
[2385]598  virtual inline int *indices() const
599  {
600    return reinterpret_cast< int * >(elements_ + numberRows_ * numberRows_);
601  }
[1878]602  /// Returns permute in
[2385]603  virtual inline int *permute() const
604  {
605    return NULL; /*pivotRow_*/
606    ;
607  }
[1878]608  //@}
609
[2385]610  /// The real work of desstructor
[1878]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;
[2385]622  ////////////////// data //////////////////
[1878]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
[2385]634
635/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
636*/
Note: See TracBrowser for help on using the repository browser.