1 /* $Id: AbcSimplexFactorization.hpp 2385 2019-01-06 19:43:06Z unxusr $ */ 2 // Copyright (C) 2002, International Business Machines 3 // Corporation and others, Copyright (C) 2012, FasterCoin. All Rights Reserved. 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 6 #ifndef AbcSimplexFactorization_H 7 #define AbcSimplexFactorization_H 8 9 #include "CoinPragma.hpp" 10 11 #include "CoinAbcCommon.hpp" 12 #include "CoinAbcFactorization.hpp" 13 #include "AbcMatrix.hpp" 14 //#include "CoinAbcAnyFactorization.hpp" 15 #include "AbcSimplex.hpp" 16 #ifndef ABC_USE_COIN_FACTORIZATION 17 class ClpFactorization; 18 class CoinFactorization; 19 #else 20 #include "ClpFactorization.hpp" 21 #include "CoinFactorization.hpp" 22 #endif 23 /** This just implements AbcFactorization when an AbcMatrix object 24 is passed. 25 */ 26 class AbcSimplexFactorization { 27 28 public: 29 /**@name factorization */ 30 //@{ 31 /** When part of LP - given by basic variables. 32 Actually does factorization. 33 Arrays passed in have non negative value to say basic. 34 If status is okay, basic variables have pivot row - this is only needed 35 if increasingRows_ >1. 36 Allows scaling 37 If status is singular, then basic variables have pivot row 38 and ones thrown out have -1 39 returns 0 -okay, -1 singular, -2 too many in basis, -99 memory */ 40 int factorize(AbcSimplex *model, int solveType, bool valuesPass); 41 #ifdef EARLY_FACTORIZE 42 /// Returns -2 if can't, -1 if singular, -99 memory, 0 OK factorize(AbcSimplex * model,CoinIndexedVector & stuff)43 inline int factorize(AbcSimplex *model, CoinIndexedVector &stuff) 44 { 45 return coinAbcFactorization_->factorize(model, stuff); 46 } 47 #endif 48 //@} 49 50 /**@name Constructors, destructor */ 51 //@{ 52 /** Default constructor. */ 53 AbcSimplexFactorization(int numberRows = 0); 54 /** Destructor */ 55 ~AbcSimplexFactorization(); 56 //@} 57 58 /**@name Copy method */ 59 //@{ 60 /** The copy constructor. */ 61 AbcSimplexFactorization(const AbcSimplexFactorization &, int denseIfSmaller = 0); 62 AbcSimplexFactorization &operator=(const AbcSimplexFactorization &); 63 /// Sets factorization 64 void setFactorization(AbcSimplexFactorization &rhs); 65 //@} 66 67 /* **** below here is so can use networkish basis */ 68 /**@name rank one updates which do exist */ 69 //@{ 70 71 /** Checks if can replace one Column to basis, 72 returns update alpha 73 Fills in region for use later 74 partial update already in U */ 75 inline 76 #ifdef ABC_LONG_FACTORIZATION 77 long 78 #endif 79 double checkReplacePart1(CoinIndexedVector * regionSparse,int pivotRow)80 checkReplacePart1(CoinIndexedVector *regionSparse, 81 int pivotRow) 82 { 83 return coinAbcFactorization_->checkReplacePart1(regionSparse, pivotRow); 84 } 85 /** Checks if can replace one Column to basis, 86 returns update alpha 87 Fills in region for use later 88 partial update in vector */ 89 inline 90 #ifdef ABC_LONG_FACTORIZATION 91 long 92 #endif 93 double checkReplacePart1(CoinIndexedVector * regionSparse,CoinIndexedVector * partialUpdate,int pivotRow)94 checkReplacePart1(CoinIndexedVector *regionSparse, 95 CoinIndexedVector *partialUpdate, 96 int pivotRow) 97 { 98 return coinAbcFactorization_->checkReplacePart1(regionSparse, partialUpdate, pivotRow); 99 } 100 #ifdef MOVE_REPLACE_PART1A 101 /** Checks if can replace one Column to basis, 102 returns update alpha 103 Fills in region for use later 104 partial update already in U */ checkReplacePart1a(CoinIndexedVector * regionSparse,int pivotRow)105 inline void checkReplacePart1a(CoinIndexedVector *regionSparse, 106 int pivotRow) 107 { 108 coinAbcFactorization_->checkReplacePart1a(regionSparse, pivotRow); 109 } checkReplacePart1b(CoinIndexedVector * regionSparse,int pivotRow)110 inline double checkReplacePart1b(CoinIndexedVector *regionSparse, 111 int pivotRow) 112 { 113 return coinAbcFactorization_->checkReplacePart1b(regionSparse, pivotRow); 114 } 115 #endif 116 /** Checks if can replace one Column to basis, 117 returns 0=OK, 1=Probably OK, 2=singular, 3=no room, 5 max pivots */ checkReplacePart2(int pivotRow,double btranAlpha,double ftranAlpha,long double ftAlpha)118 inline int checkReplacePart2(int pivotRow, 119 double btranAlpha, 120 double ftranAlpha, 121 #ifdef ABC_LONG_FACTORIZATION 122 long 123 #endif 124 double ftAlpha) 125 { 126 return coinAbcFactorization_->checkReplacePart2(pivotRow, btranAlpha, ftranAlpha, ftAlpha); 127 } 128 #ifdef ABC_LONG_FACTORIZATION 129 /// Clear all hidden arrays clearHiddenArrays()130 inline void clearHiddenArrays() 131 { 132 coinAbcFactorization_->clearHiddenArrays(); 133 } 134 #endif 135 /** Replaces one Column to basis, 136 partial update already in U */ 137 void replaceColumnPart3(const AbcSimplex *model, 138 CoinIndexedVector *regionSparse, 139 CoinIndexedVector *tableauColumn, 140 int pivotRow, 141 #ifdef ABC_LONG_FACTORIZATION 142 long 143 #endif 144 double alpha); 145 /** Replaces one Column to basis, 146 partial update in vector */ 147 void replaceColumnPart3(const AbcSimplex *model, 148 CoinIndexedVector *regionSparse, 149 CoinIndexedVector *tableauColumn, 150 CoinIndexedVector *partialUpdate, 151 int pivotRow, 152 #ifdef ABC_LONG_FACTORIZATION 153 long 154 #endif 155 double alpha); 156 #ifdef EARLY_FACTORIZE 157 /// 0 success, -1 can't +1 accuracy problems replaceColumns(const AbcSimplex * model,CoinIndexedVector & stuff,int firstPivot,int lastPivot,bool cleanUp)158 inline int replaceColumns(const AbcSimplex *model, 159 CoinIndexedVector &stuff, 160 int firstPivot, int lastPivot, bool cleanUp) 161 { 162 return coinAbcFactorization_->replaceColumns(model, stuff, firstPivot, lastPivot, cleanUp); 163 } 164 #endif 165 //@} 166 167 /**@name various uses of factorization (return code number elements) 168 which user may want to know about */ 169 //@{ 170 #if 0 171 /** Updates one column (FTRAN) from region2 172 Tries to do FT update 173 number returned is negative if no room 174 region1 starts as zero and is zero at end */ 175 int updateColumnFT ( CoinIndexedVector * regionSparse, 176 CoinIndexedVector * regionSparse2); 177 /** Updates one column (FTRAN) from region2 178 region1 starts as zero and is zero at end */ 179 int updateColumn ( CoinIndexedVector * regionSparse, 180 CoinIndexedVector * regionSparse2) const; 181 /** Updates one column (FTRAN) from region2 182 Tries to do FT update 183 number returned is negative if no room. 184 Also updates region3 185 region1 starts as zero and is zero at end */ 186 int updateTwoColumnsFT ( CoinIndexedVector * regionSparse1, 187 CoinIndexedVector * regionSparse2, 188 CoinIndexedVector * regionSparse3) ; 189 /** Updates one column (BTRAN) from region2 190 region1 starts as zero and is zero at end */ 191 int updateColumnTranspose ( CoinIndexedVector * regionSparse, 192 CoinIndexedVector * regionSparse2) const; 193 #endif 194 /** Updates one column (FTRAN) 195 Tries to do FT update 196 number returned is negative if no room */ updateColumnFT(CoinIndexedVector & regionSparseFT)197 inline int updateColumnFT(CoinIndexedVector ®ionSparseFT) 198 { 199 return coinAbcFactorization_->updateColumnFT(regionSparseFT); 200 } updateColumnFTPart1(CoinIndexedVector & regionSparseFT)201 inline int updateColumnFTPart1(CoinIndexedVector ®ionSparseFT) 202 { 203 return coinAbcFactorization_->updateColumnFTPart1(regionSparseFT); 204 } updateColumnFTPart2(CoinIndexedVector & regionSparseFT)205 inline void updateColumnFTPart2(CoinIndexedVector ®ionSparseFT) 206 { 207 coinAbcFactorization_->updateColumnFTPart2(regionSparseFT); 208 } 209 /** Updates one column (FTRAN) 210 Tries to do FT update 211 puts partial update in vector */ updateColumnFT(CoinIndexedVector & regionSparseFT,CoinIndexedVector & partialUpdate,int which)212 inline void updateColumnFT(CoinIndexedVector ®ionSparseFT, 213 CoinIndexedVector &partialUpdate, 214 int which) 215 { 216 coinAbcFactorization_->updateColumnFT(regionSparseFT, partialUpdate, which); 217 } 218 /** Updates one column (FTRAN) */ updateColumn(CoinIndexedVector & regionSparse) const219 inline int updateColumn(CoinIndexedVector ®ionSparse) const 220 { 221 return coinAbcFactorization_->updateColumn(regionSparse); 222 } 223 /** Updates one column (FTRAN) from regionFT 224 Tries to do FT update 225 number returned is negative if no room. 226 Also updates regionOther */ updateTwoColumnsFT(CoinIndexedVector & regionSparseFT,CoinIndexedVector & regionSparseOther)227 inline int updateTwoColumnsFT(CoinIndexedVector ®ionSparseFT, 228 CoinIndexedVector ®ionSparseOther) 229 { 230 return coinAbcFactorization_->updateTwoColumnsFT(regionSparseFT, regionSparseOther); 231 } 232 /** Updates one column (BTRAN) */ updateColumnTranspose(CoinIndexedVector & regionSparse) const233 inline int updateColumnTranspose(CoinIndexedVector ®ionSparse) const 234 { 235 return coinAbcFactorization_->updateColumnTranspose(regionSparse); 236 } 237 /** Updates one column (FTRAN) */ updateColumnCpu(CoinIndexedVector & regionSparse,int whichCpu) const238 inline void updateColumnCpu(CoinIndexedVector ®ionSparse, int whichCpu) const 239 #ifndef ABC_USE_COIN_FACTORIZATION 240 { 241 coinAbcFactorization_->updateColumnCpu(regionSparse, whichCpu); 242 } 243 #else 244 { 245 coinAbcFactorization_->updateColumn(regionSparse); 246 } 247 #endif 248 /** Updates one column (BTRAN) */ updateColumnTransposeCpu(CoinIndexedVector & regionSparse,int whichCpu) const249 inline void updateColumnTransposeCpu(CoinIndexedVector ®ionSparse, int whichCpu) const 250 #ifndef ABC_USE_COIN_FACTORIZATION 251 { 252 coinAbcFactorization_->updateColumnTransposeCpu(regionSparse, whichCpu); 253 } 254 #else 255 { 256 coinAbcFactorization_->updateColumnTranspose(regionSparse); 257 } 258 #endif 259 /** Updates one full column (FTRAN) */ updateFullColumn(CoinIndexedVector & regionSparse) const260 inline void updateFullColumn(CoinIndexedVector ®ionSparse) const 261 { 262 coinAbcFactorization_->updateFullColumn(regionSparse); 263 } 264 /** Updates one full column (BTRAN) */ updateFullColumnTranspose(CoinIndexedVector & regionSparse) const265 inline void updateFullColumnTranspose(CoinIndexedVector ®ionSparse) const 266 { 267 coinAbcFactorization_->updateFullColumnTranspose(regionSparse); 268 } 269 /** Updates one column for dual steepest edge weights (FTRAN) */ updateWeights(CoinIndexedVector & regionSparse) const270 void updateWeights(CoinIndexedVector ®ionSparse) const 271 #ifndef ABC_USE_COIN_FACTORIZATION 272 { 273 coinAbcFactorization_->updateWeights(regionSparse); 274 } 275 #else 276 { 277 coinAbcFactorization_->updateColumn(regionSparse); 278 } 279 #endif 280 //@} 281 /**@name Lifted from CoinFactorization */ 282 //@{ 283 /// Total number of elements in factorization numberElements() const284 inline int numberElements() const 285 { 286 return coinAbcFactorization_->numberElements(); 287 } 288 /// Maximum number of pivots between factorizations maximumPivots() const289 inline int maximumPivots() const 290 { 291 return coinAbcFactorization_->maximumPivots(); 292 } 293 /// Set maximum number of pivots between factorizations maximumPivots(int value)294 inline void maximumPivots(int value) 295 { 296 coinAbcFactorization_->maximumPivots(value); 297 } 298 /// Returns true if doing FT usingFT() const299 inline bool usingFT() const 300 { 301 return !coinAbcFactorization_->wantsTableauColumn(); 302 } 303 /// Returns number of pivots since factorization pivots() const304 inline int pivots() const 305 { 306 return coinAbcFactorization_->pivots(); 307 } 308 /// Sets model setModel(AbcSimplex * model)309 inline void setModel(AbcSimplex *model) 310 { 311 model_ = model; 312 } 313 /// Sets number of pivots since factorization setPivots(int value) const314 inline void setPivots(int value) const 315 { 316 coinAbcFactorization_->setPivots(value); 317 } 318 /// Whether larger areas needed areaFactor() const319 inline double areaFactor() const 320 { 321 return coinAbcFactorization_->areaFactor(); 322 } 323 /// Set whether larger areas needed areaFactor(double value)324 inline void areaFactor(double value) 325 { 326 coinAbcFactorization_->areaFactor(value); 327 } 328 /// Zero tolerance zeroTolerance() const329 inline double zeroTolerance() const 330 { 331 return coinAbcFactorization_->zeroTolerance(); 332 } 333 /// Set zero tolerance zeroTolerance(double value)334 inline void zeroTolerance(double value) 335 { 336 coinAbcFactorization_->zeroTolerance(value); 337 } 338 /// Set tolerances to safer of existing and given 339 void saferTolerances(double zeroTolerance, double pivotTolerance); 340 /// Returns status status() const341 inline int status() const 342 { 343 return coinAbcFactorization_->status(); 344 } 345 /// Sets status setStatus(int value)346 inline void setStatus(int value) 347 { 348 coinAbcFactorization_->setStatus(value); 349 } 350 #if ABC_PARALLEL == 2 351 /// Says parallel setParallelMode(int value)352 inline void setParallelMode(int value) 353 { 354 coinAbcFactorization_->setParallelMode(value); 355 }; 356 #endif 357 /// Returns number of dense rows numberDense() const358 inline int numberDense() const 359 { 360 return coinAbcFactorization_->numberDense(); 361 } 362 bool timeToRefactorize() const; 363 #if CLP_FACTORIZATION_NEW_TIMING > 1 364 void statsRefactor(char when) const; 365 #endif 366 /// Get rid of all memory clearArrays()367 inline void clearArrays() 368 { 369 coinAbcFactorization_->clearArrays(); 370 } 371 /// Number of Rows after factorization numberRows() const372 inline int numberRows() const 373 { 374 return coinAbcFactorization_->numberRows(); 375 } 376 /// Number of slacks at last factorization numberSlacks() const377 inline int numberSlacks() const 378 { 379 return numberSlacks_; 380 } 381 /// Pivot tolerance pivotTolerance() const382 inline double pivotTolerance() const 383 { 384 return coinAbcFactorization_->pivotTolerance(); 385 } 386 /// Set pivot tolerance pivotTolerance(double value)387 inline void pivotTolerance(double value) 388 { 389 coinAbcFactorization_->pivotTolerance(value); 390 } 391 /// Minimum pivot tolerance minimumPivotTolerance() const392 inline double minimumPivotTolerance() const 393 { 394 return coinAbcFactorization_->minimumPivotTolerance(); 395 } 396 /// Set minimum pivot tolerance minimumPivotTolerance(double value)397 inline void minimumPivotTolerance(double value) 398 { 399 coinAbcFactorization_->minimumPivotTolerance(value); 400 } 401 /// pivot region pivotRegion() const402 inline double *pivotRegion() const 403 { 404 return coinAbcFactorization_->pivotRegion(); 405 } 406 /// Allows change of pivot accuracy check 1.0 == none >1.0 relaxed 407 //inline void relaxAccuracyCheck(double /*value*/) { 408 //abort(); 409 //} 410 /// Delete all stuff (leaves as after CoinFactorization()) almostDestructor()411 inline void almostDestructor() 412 { 413 coinAbcFactorization_->clearArrays(); 414 } 415 /// So we can temporarily switch off dense 416 void setDenseThreshold(int number); 417 int getDenseThreshold() const; 418 /// If nonzero force use of 1,dense 2,small 3,long 419 void forceOtherFactorization(int which); 420 /// Go over to dense code 421 void goDenseOrSmall(int numberRows); 422 /// Get switch to dense if number rows <= this goDenseThreshold() const423 inline int goDenseThreshold() const 424 { 425 return goDenseThreshold_; 426 } 427 /// Set switch to dense if number rows <= this setGoDenseThreshold(int value)428 inline void setGoDenseThreshold(int value) 429 { 430 goDenseThreshold_ = value; 431 } 432 /// Get switch to small if number rows <= this goSmallThreshold() const433 inline int goSmallThreshold() const 434 { 435 return goSmallThreshold_; 436 } 437 /// Set switch to small if number rows <= this setGoSmallThreshold(int value)438 inline void setGoSmallThreshold(int value) 439 { 440 goSmallThreshold_ = value; 441 } 442 /// Get switch to long/ordered if number rows >= this goLongThreshold() const443 inline int goLongThreshold() const 444 { 445 return goLongThreshold_; 446 } 447 /// Set switch to long/ordered if number rows >= this setGoLongThreshold(int value)448 inline void setGoLongThreshold(int value) 449 { 450 goLongThreshold_ = value; 451 } 452 /// Returns type typeOfFactorization() const453 inline int typeOfFactorization() const 454 { 455 return forceB_; 456 } 457 /// Synchronize stuff 458 void synchronize(const ClpFactorization *otherFactorization, const AbcSimplex *model); 459 //@} 460 461 /**@name other stuff */ 462 //@{ 463 /** makes a row copy of L for speed and to allow very sparse problems */ 464 void goSparse(); 465 #ifndef NDEBUG 466 #ifndef ABC_USE_COIN_FACTORIZATION checkMarkArrays() const467 inline void checkMarkArrays() const 468 { 469 coinAbcFactorization_->checkMarkArrays(); 470 } 471 #else checkMarkArrays() const472 inline void checkMarkArrays() const 473 { 474 } 475 #endif 476 #endif 477 /// Says whether to redo pivot order needToReorder() const478 inline bool needToReorder() const 479 { 480 abort(); 481 return true; 482 } 483 /// Pointer to factorization 484 #ifndef ABC_USE_COIN_FACTORIZATION factorization() const485 CoinAbcAnyFactorization *factorization() const 486 { 487 return coinAbcFactorization_; 488 } 489 #else factorization() const490 CoinFactorization *factorization() const 491 { 492 return coinAbcFactorization_; 493 } 494 #endif 495 //@} 496 497 ////////////////// data ////////////////// 498 private: 499 /**@name data */ 500 //@{ 501 /// Pointer to model 502 AbcSimplex *model_; 503 /// Pointer to factorization 504 #ifndef ABC_USE_COIN_FACTORIZATION 505 CoinAbcAnyFactorization *coinAbcFactorization_; 506 #else 507 CoinFactorization *coinAbcFactorization_; 508 #endif 509 #ifdef CLP_FACTORIZATION_NEW_TIMING 510 /// For guessing when to re-factorize 511 mutable double shortestAverage_; 512 mutable double totalInR_; 513 mutable double totalInIncreasingU_; 514 mutable int endLengthU_; 515 mutable int lastNumberPivots_; 516 mutable int effectiveStartNumberU_; 517 #endif 518 /// If nonzero force use of 1,dense 2,small 3,long 519 int forceB_; 520 /// Switch to dense if number rows <= this 521 int goDenseThreshold_; 522 /// Switch to small if number rows <= this 523 int goSmallThreshold_; 524 /// Switch to long/ordered if number rows >= this 525 int goLongThreshold_; 526 /// Number of slacks at last factorization 527 int numberSlacks_; 528 //@} 529 }; 530 531 #endif 532 533 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 534 */ 535