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