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