1 /* $Id: CoinDenseFactorization.hpp 2083 2019-01-06 19:38:09Z unxusr $ */
2 // Copyright (C) 2008, International Business Machines
3 // Corporation and others.  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 CoinDenseFactorization_H
13 #define CoinDenseFactorization_H
14 
15 #include <iostream>
16 #include <string>
17 #include <cassert>
18 #include "CoinTypes.hpp"
19 #include "CoinIndexedVector.hpp"
20 #include "CoinFactorization.hpp"
21 #if COIN_FACTORIZATION_DENSE_CODE == 2
22 #undef COIN_FACTORIZATION_DENSE_CODE
23 #endif
24 class CoinPackedMatrix;
25 /// Abstract base class which also has some scalars so can be used from Dense or Simp
26 class CoinOtherFactorization {
27 
28 public:
29   /**@name Constructors and destructor and copy */
30   //@{
31   /// Default constructor
32   CoinOtherFactorization();
33   /// Copy constructor
34   CoinOtherFactorization(const CoinOtherFactorization &other);
35 
36   /// Destructor
37   virtual ~CoinOtherFactorization();
38   /// = copy
39   CoinOtherFactorization &operator=(const CoinOtherFactorization &other);
40 
41   /// Clone
42   virtual CoinOtherFactorization *clone() const = 0;
43   //@}
44 
45   /**@name general stuff such as status */
46   //@{
47   /// Returns status
status() const48   inline int status() const
49   {
50     return status_;
51   }
52   /// Sets status
setStatus(int value)53   inline void setStatus(int value)
54   {
55     status_ = value;
56   }
57   /// Returns number of pivots since factorization
pivots() const58   inline int pivots() const
59   {
60     return numberPivots_;
61   }
62   /// Sets number of pivots since factorization
setPivots(int value)63   inline void setPivots(int value)
64   {
65     numberPivots_ = value;
66   }
67   /// Set number of Rows after factorization
setNumberRows(int value)68   inline void setNumberRows(int value)
69   {
70     numberRows_ = value;
71   }
72   /// Number of Rows after factorization
numberRows() const73   inline int numberRows() const
74   {
75     return numberRows_;
76   }
77   /// Total number of columns in factorization
numberColumns() const78   inline int numberColumns() const
79   {
80     return numberColumns_;
81   }
82   /// Number of good columns in factorization
numberGoodColumns() const83   inline int numberGoodColumns() const
84   {
85     return numberGoodU_;
86   }
87   /// Allows change of pivot accuracy check 1.0 == none >1.0 relaxed
relaxAccuracyCheck(double value)88   inline void relaxAccuracyCheck(double value)
89   {
90     relaxCheck_ = value;
91   }
getAccuracyCheck() const92   inline double getAccuracyCheck() const
93   {
94     return relaxCheck_;
95   }
96   /// Maximum number of pivots between factorizations
maximumPivots() const97   inline int maximumPivots() const
98   {
99     return maximumPivots_;
100   }
101   /// Set maximum pivots
102   virtual void maximumPivots(int value);
103 
104   /// Pivot tolerance
pivotTolerance() const105   inline double pivotTolerance() const
106   {
107     return pivotTolerance_;
108   }
109   void pivotTolerance(double value);
110   /// Zero tolerance
zeroTolerance() const111   inline double zeroTolerance() const
112   {
113     return zeroTolerance_;
114   }
115   void zeroTolerance(double value);
116 #ifndef COIN_FAST_CODE
117   /// Whether slack value is +1 or -1
slackValue() const118   inline double slackValue() const
119   {
120     return slackValue_;
121   }
122   void slackValue(double value);
123 #endif
124   /// Returns array to put basis elements in
125   virtual CoinFactorizationDouble *elements() const;
126   /// Returns pivot row
127   virtual int *pivotRow() const;
128   /// Returns work area
129   virtual CoinFactorizationDouble *workArea() const;
130   /// Returns int work area
131   virtual int *intWorkArea() const;
132   /// Number of entries in each row
133   virtual int *numberInRow() const;
134   /// Number of entries in each column
135   virtual int *numberInColumn() const;
136   /// Returns array to put basis starts in
137   virtual int *starts() const;
138   /// Returns permute back
139   virtual int *permuteBack() const;
140   /** Get solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
141       If 4 set then values pass
142       if 8 set then has iterated
143   */
solveMode() const144   inline int solveMode() const
145   {
146     return solveMode_;
147   }
148   /** Set solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
149       If 4 set then values pass
150       if 8 set then has iterated
151   */
setSolveMode(int value)152   inline void setSolveMode(int value)
153   {
154     solveMode_ = value;
155   }
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
clearArrays()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   /// Total number of elements in factorization
173   virtual int numberElements() const = 0;
174   //@}
175   /**@name Do factorization - public */
176   //@{
177   /// Gets space for a factorization
178   virtual void getAreas(int numberRows,
179     int numberColumns,
180     int maximumL,
181     int maximumU)
182     = 0;
183 
184   /// PreProcesses column ordered copy of basis
185   virtual void preProcess() = 0;
186   /** Does most of factorization returning status
187       0 - OK
188       -99 - needs more memory
189       -1 - singular - use numberGoodColumns and redo
190   */
191   virtual int factor() = 0;
192   /// Does post processing on valid factorization - putting variables on correct rows
193   virtual void postProcess(const int *sequence, int *pivotVariable) = 0;
194   /// Makes a non-singular basis by replacing variables
195   virtual void makeNonSingular(int *sequence, int numberColumns) = 0;
196   //@}
197 
198   /**@name rank one updates which do exist */
199   //@{
200 
201   /** Replaces one Column to basis,
202    returns 0=OK, 1=Probably OK, 2=singular, 3=no room
203       If checkBeforeModifying is true will do all accuracy checks
204       before modifying factorization.  Whether to set this depends on
205       speed considerations.  You could just do this on first iteration
206       after factorization and thereafter re-factorize
207    partial update already in U */
208   virtual int replaceColumn(CoinIndexedVector *regionSparse,
209     int pivotRow,
210     double pivotCheck,
211     bool checkBeforeModifying = false,
212     double acceptablePivot = 1.0e-8)
213     = 0;
214   //@}
215 
216   /**@name various uses of factorization (return code number elements)
217    which user may want to know about */
218   //@{
219   /** Updates one column (FTRAN) from regionSparse2
220       Tries to do FT update
221       number returned is negative if no room
222       regionSparse starts as zero and is zero at end.
223       Note - if regionSparse2 packed on input - will be packed on output
224   */
225   virtual int updateColumnFT(CoinIndexedVector *regionSparse,
226     CoinIndexedVector *regionSparse2,
227     bool noPermute = false)
228     = 0;
229   /** This version has same effect as above with FTUpdate==false
230       so number returned is always >=0 */
231   virtual int updateColumn(CoinIndexedVector *regionSparse,
232     CoinIndexedVector *regionSparse2,
233     bool noPermute = false) const = 0;
234   /// does FTRAN on two columns
235   virtual int updateTwoColumnsFT(CoinIndexedVector *regionSparse1,
236     CoinIndexedVector *regionSparse2,
237     CoinIndexedVector *regionSparse3,
238     bool noPermute = false)
239     = 0;
240   /** Updates one column (BTRAN) from regionSparse2
241       regionSparse starts as zero and is zero at end
242       Note - if regionSparse2 packed on input - will be packed on output
243   */
244   virtual int updateColumnTranspose(CoinIndexedVector *regionSparse,
245     CoinIndexedVector *regionSparse2) const = 0;
246   //@}
247 
248   ////////////////// data //////////////////
249 protected:
250   /**@name data */
251   //@{
252   /// Pivot tolerance
253   double pivotTolerance_;
254   /// Zero tolerance
255   double zeroTolerance_;
256 #ifndef COIN_FAST_CODE
257   /// Whether slack value is  +1 or -1
258   double slackValue_;
259 #else
260 #ifndef slackValue_
261 #define slackValue_ -1.0
262 #endif
263 #endif
264   /// Relax check on accuracy in replaceColumn
265   double relaxCheck_;
266   /// Number of elements after factorization
267   int factorElements_;
268   /// Number of Rows in factorization
269   int numberRows_;
270   /// Number of Columns in factorization
271   int numberColumns_;
272   /// Number factorized in U (not row singletons)
273   int numberGoodU_;
274   /// Maximum number of pivots before factorization
275   int maximumPivots_;
276   /// Number pivots since last factorization
277   int numberPivots_;
278   /// Status of factorization
279   int status_;
280   /// Maximum rows ever (i.e. use to copy arrays etc)
281   int maximumRows_;
282   /// Maximum length of iterating area
283   int maximumSpace_;
284   /// Pivot row
285   int *pivotRow_;
286   /** Elements of factorization and updates
287       length is maxR*maxR+maxSpace
288       will always be long enough so can have nR*nR ints in maxSpace
289   */
290   CoinFactorizationDouble *elements_;
291   /// Work area of numberRows_
292   CoinFactorizationDouble *workArea_;
293   /** Solve mode e.g. 0 C++ code, 1 Lapack, 2 choose
294       If 4 set then values pass
295       if 8 set then has iterated
296   */
297   int solveMode_;
298   //@}
299 };
300 /** This deals with Factorization and Updates
301     This is a simple dense version so other people can write a better one
302 
303     I am assuming that 32 bits is enough for number of rows or columns, but CoinBigIndex
304     may be redefined to get 64 bits.
305  */
306 
307 class CoinDenseFactorization : public CoinOtherFactorization {
308   friend void CoinDenseFactorizationUnitTest(const std::string &mpsDir);
309 
310 public:
311   /**@name Constructors and destructor and copy */
312   //@{
313   /// Default constructor
314   CoinDenseFactorization();
315   /// Copy constructor
316   CoinDenseFactorization(const CoinDenseFactorization &other);
317 
318   /// Destructor
319   virtual ~CoinDenseFactorization();
320   /// = copy
321   CoinDenseFactorization &operator=(const CoinDenseFactorization &other);
322   /// Clone
323   virtual CoinOtherFactorization *clone() const;
324   //@}
325 
326   /**@name Do factorization - public */
327   //@{
328   /// Gets space for a factorization
329   virtual void getAreas(int numberRows,
330     int numberColumns,
331     int maximumL,
332     int maximumU);
333 
334   /// PreProcesses column ordered copy of basis
335   virtual void preProcess();
336   /** Does most of factorization returning status
337       0 - OK
338       -99 - needs more memory
339       -1 - singular - use numberGoodColumns and redo
340   */
341   virtual int factor();
342   /// Does post processing on valid factorization - putting variables on correct rows
343   virtual void postProcess(const int *sequence, int *pivotVariable);
344   /// Makes a non-singular basis by replacing variables
345   virtual void makeNonSingular(int *sequence, int numberColumns);
346   //@}
347 
348   /**@name general stuff such as number of elements */
349   //@{
350   /// Total number of elements in factorization
numberElements() const351   virtual inline int numberElements() const
352   {
353     return numberRows_ * (numberColumns_ + numberPivots_);
354   }
355   /// Returns maximum absolute value in factorization
356   double maximumCoefficient() const;
357   //@}
358 
359   /**@name rank one updates which do exist */
360   //@{
361 
362   /** Replaces one Column to basis,
363    returns 0=OK, 1=Probably OK, 2=singular, 3=no room
364       If checkBeforeModifying is true will do all accuracy checks
365       before modifying factorization.  Whether to set this depends on
366       speed considerations.  You could just do this on first iteration
367       after factorization and thereafter re-factorize
368    partial update already in U */
369   virtual int replaceColumn(CoinIndexedVector *regionSparse,
370     int pivotRow,
371     double pivotCheck,
372     bool checkBeforeModifying = false,
373     double acceptablePivot = 1.0e-8);
374   //@}
375 
376   /**@name various uses of factorization (return code number elements)
377    which user may want to know about */
378   //@{
379   /** Updates one column (FTRAN) from regionSparse2
380       Tries to do FT update
381       number returned is negative if no room
382       regionSparse starts as zero and is zero at end.
383       Note - if regionSparse2 packed on input - will be packed on output
384   */
updateColumnFT(CoinIndexedVector * regionSparse,CoinIndexedVector * regionSparse2,bool=false)385   virtual inline int updateColumnFT(CoinIndexedVector *regionSparse,
386     CoinIndexedVector *regionSparse2,
387     bool = false)
388   {
389     return updateColumn(regionSparse, regionSparse2);
390   }
391   /** This version has same effect as above with FTUpdate==false
392       so number returned is always >=0 */
393   virtual int updateColumn(CoinIndexedVector *regionSparse,
394     CoinIndexedVector *regionSparse2,
395     bool noPermute = false) const;
396   /// does FTRAN on two columns
397   virtual int updateTwoColumnsFT(CoinIndexedVector *regionSparse1,
398     CoinIndexedVector *regionSparse2,
399     CoinIndexedVector *regionSparse3,
400     bool noPermute = false);
401   /** Updates one column (BTRAN) from regionSparse2
402       regionSparse starts as zero and is zero at end
403       Note - if regionSparse2 packed on input - will be packed on output
404   */
405   virtual int updateColumnTranspose(CoinIndexedVector *regionSparse,
406     CoinIndexedVector *regionSparse2) const;
407   //@}
408   /// *** Below this user may not want to know about
409 
410   /**@name various uses of factorization
411    which user may not want to know about (left over from my LP code) */
412   //@{
413   /// Get rid of all memory
clearArrays()414   inline void clearArrays()
415   {
416     gutsOfDestructor();
417   }
418   /// Returns array to put basis indices in
indices() const419   virtual inline int *indices() const
420   {
421     return reinterpret_cast< int * >(elements_ + numberRows_ * numberRows_);
422   }
423   /// Returns permute in
permute() const424   virtual inline int *permute() const
425   {
426     return NULL; /*pivotRow_*/
427     ;
428   }
429   //@}
430 
431   /// The real work of desstructor
432   void gutsOfDestructor();
433   /// The real work of constructor
434   void gutsOfInitialize();
435   /// The real work of copy
436   void gutsOfCopy(const CoinDenseFactorization &other);
437 
438   //@}
439 protected:
440   /** Returns accuracy status of replaceColumn
441       returns 0=OK, 1=Probably OK, 2=singular */
442   int checkPivot(double saveFromU, double oldPivot) const;
443   ////////////////// data //////////////////
444 protected:
445   /**@name data */
446   //@{
447   //@}
448 };
449 #endif
450 
451 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
452 */
453