1/* $Id: CoinOslFactorization.hpp 1448 2011-06-19 15:34:41Z stefan $ */
2// Copyright (C) 1987, 2009, 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 CoinOslFactorization_H
13#define CoinOslFactorization_H
14#include <iostream>
15#include <string>
16#include <cassert>
17#include "CoinTypes.hpp"
18#include "CoinIndexedVector.hpp"
19#include "CoinDenseFactorization.hpp"
20class CoinPackedMatrix;
21/** This deals with Factorization and Updates
22 This is ripped off from OSL!!!!!!!!!
23
24 I am assuming that 32 bits is enough for number of rows or columns, but CoinBigIndex
25 may be redefined to get 64 bits.
26 */
27
28typedef struct {int suc, pre;} EKKHlink;
29typedef struct _EKKfactinfo {
30 double drtpiv;
31 double demark;
32 double zpivlu;
33 double zeroTolerance;
34 double areaFactor;
35 int *xrsadr;
36 int *xcsadr;
37 int *xrnadr;
38 int *xcnadr;
39 int *krpadr;
40 int *kcpadr;
41 int *mpermu;
42 int *bitArray;
43 int * back;
44 char * nonzero;
45 double * trueStart;
46 mutable double *kadrpm;
47 int *R_etas_index;
48 int *R_etas_start;
49 double *R_etas_element;
50
51 int *xecadr;
52 int *xeradr;
53 double *xeeadr;
54 double *xe2adr;
55 EKKHlink * kp1adr;
56 EKKHlink * kp2adr;
57 double * kw1adr;
58 double * kw2adr;
59 double * kw3adr;
60 int * hpivcoR;
61 int nrow;
62 int nrowmx;
63 int firstDoRow;
64 int firstLRow;
65 int maxinv;
66 int nnetas;
67 int iterin;
68 int iter0;
69 int invok;
70 int nbfinv;
71 int num_resets;
72 int nnentl;
73 int nnentu;
74#ifdef CLP_REUSE_ETAS
75 int save_nnentu;
76#endif
77 int ndenuc;
78 int npivots; /* use as xpivsq in factorization */
79 int kmxeta;
80 int xnetal;
81 int first_dense;
82 int last_dense;
83 int iterno;
84 int numberSlacks;
85 int lastSlack;
86 int firstNonSlack;
87 int xnetalval;
88 int lstart;
89 int if_sparse_update;
90 mutable int packedMode;
91 int switch_off_sparse_update;
92 int nuspike;
93 bool rows_ok; /* replaces test using mrstrt[1] */
94#ifdef CLP_REUSE_ETAS
95 mutable int reintro;
96#endif
97 int nR_etas;
98 int sortedEta; /* if vector for F-T is sorted */
99 int lastEtaCount;
100 int ifvsol;
101 int eta_size;
102 int last_eta_size;
103 int maxNNetas;
104} EKKfactinfo;
105
106class CoinOslFactorization : public CoinOtherFactorization {
107 friend void CoinOslFactorizationUnitTest( const std::string & mpsDir );
108
109public:
110
111 /**@name Constructors and destructor and copy */
112 //@{
113 /// Default constructor
114 CoinOslFactorization ( );
115 /// Copy constructor
116 CoinOslFactorization ( const CoinOslFactorization &other);
117
118 /// Destructor
119 virtual ~CoinOslFactorization ( );
120 /// = copy
121 CoinOslFactorization & operator = ( const CoinOslFactorization & other );
122 /// Clone
123 virtual CoinOtherFactorization * clone() const override ;
124 //@}
125
126 /**@name Do factorization - public */
127 //@{
128 /// Gets space for a factorization
129 virtual void getAreas ( int numberRows,
130 int numberColumns,
131 CoinBigIndex maximumL,
132 CoinBigIndex maximumU ) override;
133
134 /// PreProcesses column ordered copy of basis
135 virtual void preProcess ( ) override;
136 /** Does most of factorization returning status
137 0 - OK
138 -99 - needs more memory
139 -1 - singular - use numberGoodColumns and redo
140 */
141 virtual int factor ( ) override;
142 /// Does post processing on valid factorization - putting variables on correct rows
143 virtual void postProcess(const int * sequence, int * pivotVariable) override;
144 /// Makes a non-singular basis by replacing variables
145 virtual void makeNonSingular(int * sequence, int numberColumns) override;
146 /** When part of LP - given by basic variables.
147 Actually does factorization.
148 Arrays passed in have non negative value to say basic.
149 If status is okay, basic variables have pivot row - this is only needed
150 If status is singular, then basic variables have pivot row
151 and ones thrown out have -1
152 returns 0 -okay, -1 singular, -2 too many in basis, -99 memory */
153 int factorize ( const CoinPackedMatrix & matrix,
154 int rowIsBasic[], int columnIsBasic[] ,
155 double areaFactor = 0.0 );
156 //@}
157
158 /**@name general stuff such as number of elements */
159 //@{
160 /// Total number of elements in factorization
161 virtual inline int numberElements ( ) const override {
162 return numberRows_*(numberColumns_+numberPivots_);
163 }
164 /// Returns array to put basis elements in
165 virtual CoinFactorizationDouble * elements() const override;
166 /// Returns pivot row
167 virtual int * pivotRow() const override;
168 /// Returns work area
169 virtual CoinFactorizationDouble * workArea() const override;
170 /// Returns int work area
171 virtual int * intWorkArea() const override;
172 /// Number of entries in each row
173 virtual int * numberInRow() const override;
174 /// Number of entries in each column
175 virtual int * numberInColumn() const override;
176 /// Returns array to put basis starts in
177 virtual CoinBigIndex * starts() const override;
178 /// Returns permute back
179 virtual int * permuteBack() const override;
180 /// Returns true if wants tableauColumn in replaceColumn
181 virtual bool wantsTableauColumn() const override;
182 /** Useful information for factorization
183 0 - iteration number
184 whereFrom is 0 for factorize and 1 for replaceColumn
185 */
186 virtual void setUsefulInformation(const int * info,int whereFrom) override;
187 /// Set maximum pivots
188 virtual void maximumPivots ( int value ) override;
189
190 /// Returns maximum absolute value in factorization
191 double maximumCoefficient() const;
192 /// Condition number - product of pivots after factorization
193 double conditionNumber() const;
194 /// Get rid of all memory
195 virtual void clearArrays() override;
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) override;
213 //@}
214
215 /**@name various uses of factorization (return code number elements)
216 which user may want to know about */
217 //@{
218 /** Updates one column (FTRAN) from regionSparse2
219 Tries to do FT update
220 number returned is negative if no room
221 regionSparse starts as zero and is zero at end.
222 Note - if regionSparse2 packed on input - will be packed on output
223 */
224 virtual int updateColumnFT ( CoinIndexedVector * regionSparse,
225 CoinIndexedVector * regionSparse2,
226 bool noPermute=false) override;
227 /** This version has same effect as above with FTUpdate==false
228 so number returned is always >=0 */
229 virtual int updateColumn ( CoinIndexedVector * regionSparse,
230 CoinIndexedVector * regionSparse2,
231 bool noPermute=false) const override;
232 /// does FTRAN on two columns
233 virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1,
234 CoinIndexedVector * regionSparse2,
235 CoinIndexedVector * regionSparse3,
236 bool noPermute=false) override;
237 /** Updates one column (BTRAN) from regionSparse2
238 regionSparse starts as zero and is zero at end
239 Note - if regionSparse2 packed on input - will be packed on output
240 */
241 virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse,
242 CoinIndexedVector * regionSparse2) const override;
243 //@}
244 /// *** Below this user may not want to know about
245
246 /**@name various uses of factorization
247 which user may not want to know about (left over from my LP code) */
248 //@{
249 /// Get rid of all memory
250 //inline void clearArrays()
251 //{ gutsOfDestructor();}
252 /// Returns array to put basis indices in
253 virtual int * indices() const override;
254 /// Returns permute in
255 virtual inline int * permute() const override
256 { return nullptr;/*pivotRow_*/;}
257 //@}
258
259 /// The real work of desstructor
260 void gutsOfDestructor(bool clearFact=true);
261 /// The real work of constructor
262 void gutsOfInitialize(bool zapFact=true);
263 /// The real work of copy
264 void gutsOfCopy(const CoinOslFactorization &other);
265
266 //@}
267protected:
268 /** Returns accuracy status of replaceColumn
269 returns 0=OK, 1=Probably OK, 2=singular */
270 int checkPivot(double saveFromU, double oldPivot) const;
271////////////////// data //////////////////
272protected:
273
274 /**@name data */
275 //@{
276 /// Osl factorization data
277 EKKfactinfo factInfo_;
278 //@}
279};
280#endif
281