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