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

Last change on this file since 1910 was 1910, checked in by stefan, 7 years ago
  • add configure option --enable-aboca={1,2,3,4,yes,no}
  • compile Aboca source only if --enable-aboca set (instead of compiling empty source files)
  • fix svn properties
  • Property svn:keywords set to Id
File size: 18.2 KB
Line 
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"
22class CoinPackedMatrix;
23/// Abstract base class which also has some scalars so can be used from Dense or Simp
24class CoinAbcAnyFactorization {
25
26public:
27
28  /**@name Constructors and destructor and copy */
29  //@{
30  /// Default constructor
31  CoinAbcAnyFactorization (  );
32  /// Copy constructor
33  CoinAbcAnyFactorization ( const CoinAbcAnyFactorization &other);
34 
35  /// Destructor
36  virtual ~CoinAbcAnyFactorization (  );
37  /// = copy
38  CoinAbcAnyFactorization & operator = ( const CoinAbcAnyFactorization & other );
39 
40  /// Clone
41  virtual CoinAbcAnyFactorization * clone() const = 0;
42  //@}
43
44  /**@name general stuff such as status */
45  //@{
46  /// Returns status
47  inline int status (  ) const {
48    return status_;
49  }
50  /// Sets status
51  inline void setStatus (  int value)
52  {  status_=value;  }
53  /// Returns number of pivots since factorization
54  inline int pivots (  ) const {
55    return numberPivots_;
56  }
57#if ABC_PARALLEL==2
58  /// Says parallel
59  inline void setParallelMode(int value)
60  {parallelMode_=value;};
61#endif
62  /// Sets number of pivots since factorization
63  inline void setPivots (  int value ) 
64  { numberPivots_=value; }
65  /// Returns number of slacks
66  inline int numberSlacks (  ) const {
67    return numberSlacks_;
68  }
69  /// Sets number of slacks
70  inline void setNumberSlacks (  int value ) 
71  { numberSlacks_=value; }
72  /// Set number of Rows after factorization
73  inline void setNumberRows(int value)
74  { numberRows_ = value; }
75  /// Number of Rows after factorization
76  inline int numberRows (  ) const {
77    return numberRows_;
78  }
79  /// Number of dense rows after factorization
80  inline CoinSimplexInt numberDense (  ) const {
81    return numberDense_;
82  }
83  /// Number of good columns in factorization
84  inline int numberGoodColumns (  ) const {
85    return numberGoodU_;
86  }
87  /// Allows change of pivot accuracy check 1.0 == none >1.0 relaxed
88  inline void relaxAccuracyCheck(double value)
89  { relaxCheck_ = value;}
90  inline double getAccuracyCheck() const
91  { return relaxCheck_;}
92  /// Maximum number of pivots between factorizations
93  inline int maximumPivots (  ) const {
94    return maximumPivots_ ;
95  }
96  /// Set maximum pivots
97  virtual void maximumPivots (  int value );
98
99  /// Pivot tolerance
100  inline double pivotTolerance (  ) const {
101    return pivotTolerance_ ;
102  }
103  void pivotTolerance (  double value );
104  /// Minimum pivot tolerance
105  inline double minimumPivotTolerance (  ) const {
106    return minimumPivotTolerance_ ;
107  }
108  void minimumPivotTolerance (  double value );
109  virtual CoinFactorizationDouble * pivotRegion() const
110  { return NULL;}
111  /// Area factor
112  inline double areaFactor (  ) const {
113    return areaFactor_ ;
114  }
115  inline void areaFactor ( CoinSimplexDouble value ) {
116    areaFactor_=value;
117  }
118  /// Zero tolerance
119  inline double zeroTolerance (  ) const {
120    return zeroTolerance_ ;
121  }
122  void zeroTolerance (  double value );
123  /// Returns array to put basis elements in
124  virtual CoinFactorizationDouble * elements() const;
125  /// Returns pivot row
126  virtual int * pivotRow() const;
127  /// Returns work area
128  virtual CoinFactorizationDouble * workArea() const;
129  /// Returns int work area
130  virtual int * intWorkArea() const;
131  /// Number of entries in each row
132  virtual int * numberInRow() const;
133  /// Number of entries in each column
134  virtual int * numberInColumn() const;
135  /// Returns array to put basis starts in
136  virtual CoinBigIndex * starts() const;
137  /// Returns permute back
138  virtual int * permuteBack() const;
139  /// Sees whether to go sparse
140  virtual void goSparse() {}
141#ifndef NDEBUG
142  virtual inline void checkMarkArrays() const {}
143#endif
144  /** Get solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
145      If 4 set then values pass
146      if 8 set then has iterated
147  */
148  inline int solveMode() const
149  { return solveMode_ ;}
150  /** Set solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
151      If 4 set then values pass
152      if 8 set then has iterated
153  */
154  inline void setSolveMode(int value)
155  { solveMode_ = value;}
156  /// Returns true if wants tableauColumn in replaceColumn
157  virtual bool wantsTableauColumn() const;
158  /** Useful information for factorization
159      0 - iteration number
160      whereFrom is 0 for factorize and 1 for replaceColumn
161  */
162  virtual void setUsefulInformation(const int * info,int whereFrom);
163  /// Get rid of all memory
164  virtual void clearArrays() {}
165  //@}
166  /**@name virtual general stuff such as permutation */
167  //@{
168  /// Returns array to put basis indices in
169  virtual int * indices() const  = 0;
170  /// Returns permute in
171  virtual int * permute() const = 0;
172  /// Returns pivotColumn or permute
173  virtual int * pivotColumn() const;
174  /// Total number of elements in factorization
175  virtual int numberElements (  ) const = 0;
176  //@}
177  /**@name Do factorization - public */
178  //@{
179  /// Gets space for a factorization
180  virtual void getAreas ( int numberRows,
181                  int numberColumns,
182                  CoinBigIndex maximumL,
183                  CoinBigIndex maximumU ) = 0;
184 
185  /// PreProcesses column ordered copy of basis
186  virtual void preProcess ( ) = 0;
187  /** Does most of factorization returning status
188      0 - OK
189      -99 - needs more memory
190      -1 - singular - use numberGoodColumns and redo
191  */
192  virtual int factor (AbcSimplex * model) = 0;
193#ifdef EARLY_FACTORIZE
194  /// Returns -2 if can't, -1 if singular, -99 memory, 0 OK
195  virtual int factorize (AbcSimplex * /*model*/, CoinIndexedVector & /*stuff*/)
196  { return -2;}
197#endif
198  /// Does post processing on valid factorization - putting variables on correct rows
199  virtual void postProcess(const int * sequence, int * pivotVariable) = 0;
200  /// Makes a non-singular basis by replacing variables
201  virtual void makeNonSingular(int * sequence) = 0;
202  //@}
203
204  /**@name rank one updates which do exist */
205  //@{
206#if 0
207  /** Checks if can replace one Column to basis,
208      returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots
209      Fills in region for use later
210      partial update already in U */
211  virtual int checkReplace ( CoinIndexedVector * /*regionSparse*/,
212                             int /*pivotRow*/,
213                             double & /*pivotCheck*/,
214                             double /*acceptablePivot = 1.0e-8*/)
215  {return 0;}
216  /** Replaces one Column to basis,
217   returns 0=OK, 1=Probably OK, 2=singular, 3=no room
218      If skipBtranU is false will do btran part
219   partial update already in U */
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  /// 0 success, -1 can't +1 accuracy problems
228  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  /// Clear all hidden arrays
235  virtual void clearHiddenArrays() {}
236#endif
237  /** Checks if can replace one Column to basis,
238      returns update alpha
239      Fills in region for use later
240      partial update already in U */
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;}
262  /** Checks if can replace one Column to basis,
263      returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots */
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;
272  /** Replaces one Column to basis,
273      partial update already in U */
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;
282  /** Replaces one Column to basis,
283      partial update in vector */
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;
293  //@}
294
295  /**@name various uses of factorization (return code number elements)
296   which user may want to know about */
297  //@{
298  /** Updates one column (FTRAN) from unpacked regionSparse
299      Tries to do FT update
300      number returned is negative if no room
301  */
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;
308  /** This version has same effect as above with FTUpdate==false
309      so number returned is always >=0 */
310  virtual int updateColumn ( CoinIndexedVector & regionSparse) const = 0;
311  /// does FTRAN on two unpacked columns
312  virtual int updateTwoColumnsFT(CoinIndexedVector & regionFT,
313                                    CoinIndexedVector & regionOther) = 0;
314  /** Updates one column (BTRAN) from unpacked regionSparse
315  */
316  virtual int updateColumnTranspose ( CoinIndexedVector & regionSparse) const = 0;
317  /** This version does FTRAN on array when indices not set up */
318  virtual void updateFullColumn ( CoinIndexedVector & regionSparse) const = 0;
319  /** Updates one column (BTRAN) from unpacked regionSparse
320  */
321  virtual void updateFullColumnTranspose ( CoinIndexedVector & regionSparse) const = 0;
322  /** Updates one column for dual steepest edge weights (FTRAN) */
323  virtual void updateWeights ( CoinIndexedVector & regionSparse) const=0;
324  /** Updates one column (FTRAN) */
325  virtual void updateColumnCpu ( CoinIndexedVector & regionSparse,int whichCpu) const;
326  /** Updates one column (BTRAN) */
327  virtual void updateColumnTransposeCpu ( CoinIndexedVector & regionSparse,int whichCpu) const;
328  //@}
329
330////////////////// data //////////////////
331protected:
332
333  /**@name data */
334  //@{
335  /// Pivot tolerance
336  double pivotTolerance_;
337  /// Minimum pivot tolerance
338  double minimumPivotTolerance_;
339  /// Area factor
340  double areaFactor_;
341  /// Zero tolerance
342  double zeroTolerance_;
343  //#ifndef slackValue_
344#define slackValue2_ 1.0
345  //#endif
346  /// Relax check on accuracy in replaceColumn
347  double relaxCheck_;
348  /// Number of elements after factorization
349  CoinBigIndex factorElements_;
350  /// Number of Rows in factorization
351  int numberRows_;
352  /// Number of dense rows in factorization
353  int numberDense_;
354  /// Number factorized in U (not row singletons)
355  int numberGoodU_;
356  /// Maximum number of pivots before factorization
357  int maximumPivots_;
358  /// Number pivots since last factorization
359  int numberPivots_;
360  /// Number slacks
361  int numberSlacks_;
362  /// Status of factorization
363  int status_;
364  /// Maximum rows ever (i.e. use to copy arrays etc)
365  int maximumRows_;
366#if ABC_PARALLEL==2
367  int parallelMode_;
368#endif
369  /// Pivot row
370  int * pivotRow_;
371  /** Elements of factorization and updates
372      length is maxR*maxR+maxSpace
373      will always be long enough so can have nR*nR ints in maxSpace
374  */
375  CoinFactorizationDouble * elements_;
376  /// Work area of numberRows_
377  CoinFactorizationDouble * workArea_;
378  /** Solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
379      If 4 set then values pass
380      if 8 set then has iterated
381  */
382  int solveMode_;
383  //@}
384};
385/** This deals with Factorization and Updates
386    This is a simple dense version so other people can write a better one
387
388    I am assuming that 32 bits is enough for number of rows or columns, but CoinBigIndex
389    may be redefined to get 64 bits.
390 */
391
392
393
394class CoinAbcDenseFactorization : public CoinAbcAnyFactorization {
395   friend void CoinAbcDenseFactorizationUnitTest( const std::string & mpsDir );
396
397public:
398
399  /**@name Constructors and destructor and copy */
400  //@{
401  /// Default constructor
402  CoinAbcDenseFactorization (  );
403  /// Copy constructor
404  CoinAbcDenseFactorization ( const CoinAbcDenseFactorization &other);
405 
406  /// Destructor
407  virtual ~CoinAbcDenseFactorization (  );
408  /// = copy
409  CoinAbcDenseFactorization & operator = ( const CoinAbcDenseFactorization & other );
410  /// Clone
411  virtual CoinAbcAnyFactorization * clone() const ;
412  //@}
413
414  /**@name Do factorization - public */
415  //@{
416  /// Gets space for a factorization
417  virtual void getAreas ( int numberRows,
418                  int numberColumns,
419                  CoinBigIndex maximumL,
420                  CoinBigIndex maximumU );
421 
422  /// PreProcesses column ordered copy of basis
423  virtual void preProcess ( );
424  /** Does most of factorization returning status
425      0 - OK
426      -99 - needs more memory
427      -1 - singular - use numberGoodColumns and redo
428  */
429  virtual int factor (AbcSimplex * model);
430  /// Does post processing on valid factorization - putting variables on correct rows
431  virtual void postProcess(const int * sequence, int * pivotVariable);
432  /// Makes a non-singular basis by replacing variables
433  virtual void makeNonSingular(int * sequence);
434  //@}
435
436  /**@name general stuff such as number of elements */
437  //@{
438  /// Total number of elements in factorization
439  virtual inline int numberElements (  ) const {
440    return numberRows_*(numberRows_+numberPivots_);
441  }
442  /// Returns maximum absolute value in factorization
443  double maximumCoefficient() const;
444  //@}
445
446  /**@name rank one updates which do exist */
447  //@{
448
449  /** Replaces one Column to basis,
450   returns 0=OK, 1=Probably OK, 2=singular, 3=no room
451      If skipBtranU is false will do btran part
452   partial update already in U */
453  virtual int replaceColumn ( CoinIndexedVector * regionSparse,
454                      int pivotRow,
455                      double pivotCheck ,
456                              bool skipBtranU=false,
457                              double acceptablePivot=1.0e-8);
458  /** Checks if can replace one Column to basis,
459      returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots */
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) ;
468  /** Replaces one Column to basis,
469      partial update already in U */
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 );
478  /** Replaces one Column to basis,
479      partial update in vector */
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);}
490  //@}
491
492  /**@name various uses of factorization (return code number elements)
493   which user may want to know about */
494  //@{
495  /** Updates one column (FTRAN) from unpacked regionSparse
496      Tries to do FT update
497      number returned is negative if no room
498  */
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);}
507  /** This version has same effect as above with FTUpdate==false
508      so number returned is always >=0 */
509  virtual int updateColumn ( CoinIndexedVector & regionSparse) const;
510  /// does FTRAN on two unpacked columns
511  virtual int updateTwoColumnsFT(CoinIndexedVector & regionFT,
512                                    CoinIndexedVector & regionOther);
513  /** Updates one column (BTRAN) from unpacked regionSparse
514  */
515  virtual int updateColumnTranspose ( CoinIndexedVector & regionSparse) const;
516  /** This version does FTRAN on array when indices not set up */
517  virtual void updateFullColumn ( CoinIndexedVector & regionSparse) const
518  {updateColumn(regionSparse);}
519  /** Updates one column (BTRAN) from unpacked regionSparse
520  */
521  virtual void updateFullColumnTranspose ( CoinIndexedVector & regionSparse) const
522  {updateColumnTranspose(regionSparse);}
523  /** Updates one column for dual steepest edge weights (FTRAN) */
524  virtual void updateWeights ( CoinIndexedVector & regionSparse) const;
525  //@}
526  /// *** Below this user may not want to know about
527
528  /**@name various uses of factorization
529   which user may not want to know about (left over from my LP code) */
530  //@{
531  /// Get rid of all memory
532  inline void clearArrays()
533  { gutsOfDestructor();}
534  /// Returns array to put basis indices in
535  virtual inline int * indices() const
536  { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
537  /// Returns permute in
538  virtual inline int * permute() const
539  { return NULL;/*pivotRow_*/;}
540  //@}
541
542  /// The real work of desstructor
543  void gutsOfDestructor();
544  /// The real work of constructor
545  void gutsOfInitialize();
546  /// The real work of copy
547  void gutsOfCopy(const CoinAbcDenseFactorization &other);
548
549  //@}
550protected:
551  /** Returns accuracy status of replaceColumn
552      returns 0=OK, 1=Probably OK, 2=singular */
553  int checkPivot(double saveFromU, double oldPivot) const;
554////////////////// data //////////////////
555protected:
556  /// Maximum length of iterating area
557  CoinBigIndex maximumSpace_;
558  /// Use for array size to get multiple of 8
559  CoinSimplexInt maximumRowsAdjusted_;
560
561  /**@name data */
562  //@{
563  //@}
564};
565#endif
Note: See TracBrowser for help on using the repository browser.