00001
00002
00003
00004
00005
00006
00007
00008
00009
00010 #ifndef CoinFactorization_H
00011 #define CoinFactorization_H
00012
00013 #include <iostream>
00014 #include <string>
00015 #include <cassert>
00016 #include "CoinFinite.hpp"
00017 class CoinPackedMatrix;
00018 class CoinIndexedVector;
00045 class CoinFactorization {
00046 friend void CoinFactorizationUnitTest( const std::string & mpsDir );
00047
00048 public:
00049
00052
00053 CoinFactorization ( );
00055 CoinFactorization ( const CoinFactorization &other);
00056
00058 ~CoinFactorization ( );
00060 void show_self ( ) const;
00062 int saveFactorization (const char * file ) const;
00066 int restoreFactorization (const char * file , bool factor=false) ;
00068 void sort ( ) const;
00070 CoinFactorization & operator = ( const CoinFactorization & other );
00072
00082 int factorize ( const CoinPackedMatrix & matrix,
00083 int rowIsBasic[], int columnIsBasic[] ,
00084 double areaFactor = 0.0 );
00095 int factorize ( int numberRows,
00096 int numberColumns,
00097 CoinBigIndex numberElements,
00098 CoinBigIndex maximumL,
00099 CoinBigIndex maximumU,
00100 const int indicesRow[],
00101 const int indicesColumn[], const double elements[] ,
00102 int permutation[],
00103 double areaFactor = 0.0);
00108 int factorizePart1 ( int numberRows,
00109 int numberColumns,
00110 CoinBigIndex estimateNumberElements,
00111 int * indicesRow[],
00112 int * indicesColumn[],
00113 double * elements[],
00114 double areaFactor = 0.0);
00121 int factorizePart2 (int permutation[],int exactNumberElements);
00123
00126
00127 inline int status ( ) const {
00128 return status_;
00129 };
00131 inline int pivots ( ) const {
00132 return numberPivots_;
00133 };
00135 inline int *permute ( ) const {
00136 return permute_;
00137 };
00139 inline int *pivotColumn ( ) const {
00140 return pivotColumn_;
00141 };
00143 inline int *permuteBack ( ) const {
00144 return permuteBack_;
00145 };
00147 inline int *pivotColumnBack ( ) const {
00148 return pivotColumnBack_;
00149 };
00151 inline int numberRowsExtra ( ) const {
00152 return numberRowsExtra_;
00153 };
00155 inline int numberRows ( ) const {
00156 return numberRows_;
00157 };
00159 inline int maximumRowsExtra ( ) const {
00160 return maximumRowsExtra_;
00161 };
00163 inline int numberColumns ( ) const {
00164 return numberColumns_;
00165 };
00167 inline int numberElements ( ) const {
00168 return totalElements_;
00169 };
00171 inline int numberForrestTomlin ( ) const {
00172 return numberInColumn_[numberColumnsExtra_];
00173 };
00175 inline int numberGoodColumns ( ) const {
00176 return numberGoodU_;
00177 };
00179 inline double areaFactor ( ) const {
00180 return areaFactor_;
00181 };
00182 inline void areaFactor ( double value ) {
00183 areaFactor_=value;
00184 };
00186 double adjustedAreaFactor() const;
00188 inline void relaxAccuracyCheck(double value)
00189 { relaxCheck_ = value;};
00190 inline double getAccuracyCheck() const
00191 { return relaxCheck_;};
00193 inline bool increasingRows ( ) const
00194 { return true; };
00200 inline void increasingRows ( int value ) {};
00202 inline int messageLevel ( ) const {
00203 return messageLevel_ ;
00204 };
00205 void messageLevel ( int value );
00207 inline int maximumPivots ( ) const {
00208 return maximumPivots_ ;
00209 };
00210 void maximumPivots ( int value );
00211
00213 inline int denseThreshold() const
00214 { return denseThreshold_;};
00216 inline void setDenseThreshold(int value)
00217 { denseThreshold_ = value;};
00219 inline double pivotTolerance ( ) const {
00220 return pivotTolerance_ ;
00221 };
00222 void pivotTolerance ( double value );
00224 inline double zeroTolerance ( ) const {
00225 return zeroTolerance_ ;
00226 };
00227 void zeroTolerance ( double value );
00229 inline double slackValue ( ) const {
00230 return slackValue_ ;
00231 };
00232 void slackValue ( double value );
00234 double maximumCoefficient() const;
00236 inline bool forrestTomlin() const
00237 { return doForrestTomlin_;};
00238 inline void setForrestTomlin(bool value)
00239 { doForrestTomlin_=value;};
00241
00244
00246 inline int numberDense() const
00247 { return numberDense_;};
00248
00250 inline CoinBigIndex numberElementsU ( ) const {
00251 return lengthU_;
00252 };
00254 inline CoinBigIndex lengthAreaU ( ) const {
00255 return lengthAreaU_;
00256 };
00258 inline CoinBigIndex numberElementsL ( ) const {
00259 return lengthL_;
00260 };
00262 inline CoinBigIndex lengthAreaL ( ) const {
00263 return lengthAreaL_;
00264 };
00266 inline CoinBigIndex numberElementsR ( ) const {
00267 return lengthR_;
00268 };
00270 inline CoinBigIndex numberCompressions() const
00271 { return numberCompressions_;};
00275 inline int biasLU() const
00276 { return biasLU_;};
00277 inline void setBiasLU(int value)
00278 { biasLU_=value;};
00280
00283
00291 int replaceColumn ( CoinIndexedVector * regionSparse,
00292 int pivotRow,
00293 double pivotCheck ,
00294 bool checkBeforeModifying=false);
00296
00306 int updateColumnFT ( CoinIndexedVector * regionSparse,
00307 CoinIndexedVector * regionSparse2);
00310 int updateColumn ( CoinIndexedVector * regionSparse,
00311 CoinIndexedVector * regionSparse2,
00312 bool noPermute=false) const;
00317 int updateColumnTranspose ( CoinIndexedVector * regionSparse,
00318 CoinIndexedVector * regionSparse2) const;
00320 void goSparse();
00322 int sparseThreshold ( ) const;
00324 void sparseThreshold ( int value );
00326
00327
00331
00332 inline void clearArrays()
00333 { gutsOfDestructor();};
00335
00338
00341 int add ( CoinBigIndex numberElements,
00342 int indicesRow[],
00343 int indicesColumn[], double elements[] );
00344
00347 int addColumn ( CoinBigIndex numberElements,
00348 int indicesRow[], double elements[] );
00349
00352 int addRow ( CoinBigIndex numberElements,
00353 int indicesColumn[], double elements[] );
00354
00356 int deleteColumn ( int Row );
00358 int deleteRow ( int Row );
00359
00363 int replaceRow ( int whichRow, int numberElements,
00364 const int indicesColumn[], const double elements[] );
00366 void emptyRows(int numberToEmpty, const int which[]);
00368 protected:
00369
00371
00372 void getAreas ( int numberRows,
00373 int numberColumns,
00374 CoinBigIndex maximumL,
00375 CoinBigIndex maximumU );
00376
00379 void preProcess ( int state,
00380 int possibleDuplicates = -1 );
00382 int factor ( );
00385 int factorSparse ( );
00388 int factorDense ( );
00389
00391 bool pivotOneOtherRow ( int pivotRow,
00392 int pivotColumn );
00394 bool pivotRowSingleton ( int pivotRow,
00395 int pivotColumn );
00397 bool pivotColumnSingleton ( int pivotRow,
00398 int pivotColumn );
00399
00404 bool getColumnSpace ( int iColumn,
00405 int extraNeeded );
00406
00410 bool getColumnSpaceIterateR ( int iColumn, double value,
00411 int iRow);
00417 CoinBigIndex getColumnSpaceIterate ( int iColumn, double value,
00418 int iRow);
00422 bool getRowSpace ( int iRow, int extraNeeded );
00423
00427 bool getRowSpaceIterate ( int iRow,
00428 int extraNeeded );
00430 void checkConsistency ( );
00432 inline void addLink ( int index, int count ) {
00433 int next = firstCount_[count];
00434 lastCount_[index] = -2 - count;
00435 if ( next < 0 ) {
00436
00437 firstCount_[count] = index;
00438 nextCount_[index] = -1;
00439 } else {
00440 firstCount_[count] = index;
00441 nextCount_[index] = next;
00442 lastCount_[next] = index;
00443 }};
00445 inline void deleteLink ( int index ) {
00446 int next = nextCount_[index];
00447 int last = lastCount_[index];
00448 if ( last >= 0 ) {
00449 nextCount_[last] = next;
00450 } else {
00451 int count = -last - 2;
00452
00453 firstCount_[count] = next;
00454 }
00455 if ( next >= 0 ) {
00456 lastCount_[next] = last;
00457 }
00458 nextCount_[index] = -2;
00459 lastCount_[index] = -2;
00460 return;
00461 };
00463 void separateLinks(int count,bool rowsFirst);
00465 void cleanup ( );
00466
00468 void updateColumnL ( CoinIndexedVector * region, int * indexIn ) const;
00470 void updateColumnLDensish ( CoinIndexedVector * region, int * indexIn ) const;
00472 void updateColumnLSparse ( CoinIndexedVector * region, int * indexIn ) const;
00474 void updateColumnLSparsish ( CoinIndexedVector * region, int * indexIn ) const;
00475
00477 void updateColumnR ( CoinIndexedVector * region ) const;
00480 void updateColumnRFT ( CoinIndexedVector * region, int * indexIn );
00481
00483 void updateColumnU ( CoinIndexedVector * region, int * indexIn) const;
00484
00486 void updateColumnUSparse ( CoinIndexedVector * regionSparse,
00487 int * indexIn) const;
00489 void updateColumnUSparsish ( CoinIndexedVector * regionSparse,
00490 int * indexIn) const;
00492 void updateColumnUDensish ( CoinIndexedVector * regionSparse,
00493 int * indexIn) const;
00495 void updateColumnPFI ( CoinIndexedVector * regionSparse) const;
00497 void permuteBack ( CoinIndexedVector * regionSparse,
00498 CoinIndexedVector * outVector) const;
00499
00501 void updateColumnTransposePFI ( CoinIndexedVector * region) const;
00504 void updateColumnTransposeU ( CoinIndexedVector * region,
00505 int smallestIndex) const;
00508 void updateColumnTransposeUSparsish ( CoinIndexedVector * region,
00509 int smallestIndex) const;
00512 void updateColumnTransposeUDensish ( CoinIndexedVector * region,
00513 int smallestIndex) const;
00516 void updateColumnTransposeUSparse ( CoinIndexedVector * region) const;
00517
00519 void updateColumnTransposeR ( CoinIndexedVector * region ) const;
00521 void updateColumnTransposeRDensish ( CoinIndexedVector * region ) const;
00523 void updateColumnTransposeRSparse ( CoinIndexedVector * region ) const;
00524
00526 void updateColumnTransposeL ( CoinIndexedVector * region ) const;
00528 void updateColumnTransposeLDensish ( CoinIndexedVector * region ) const;
00530 void updateColumnTransposeLByRow ( CoinIndexedVector * region ) const;
00532 void updateColumnTransposeLSparsish ( CoinIndexedVector * region ) const;
00534 void updateColumnTransposeLSparse ( CoinIndexedVector * region ) const;
00539 int replaceColumnPFI ( CoinIndexedVector * regionSparse,
00540 int pivotRow, double alpha);
00541
00544 int checkPivot(double saveFromU, double oldPivot) const;
00546 void gutsOfDestructor();
00548 void gutsOfInitialize(int type);
00549 void gutsOfCopy(const CoinFactorization &other);
00550
00552 void resetStatistics();
00553
00554
00555 #ifdef INT_IS_8
00556 #define COINFACTORIZATION_BITS_PER_INT 64
00557 #define COINFACTORIZATION_SHIFT_PER_INT 6
00558 #define COINFACTORIZATION_MASK_PER_INT 0x3f
00559 #else
00560 #define COINFACTORIZATION_BITS_PER_INT 32
00561 #define COINFACTORIZATION_SHIFT_PER_INT 5
00562 #define COINFACTORIZATION_MASK_PER_INT 0x1f
00563 #endif
00564 template <class T> bool
00565 pivot ( int pivotRow,
00566 int pivotColumn,
00567 CoinBigIndex pivotRowPosition,
00568 CoinBigIndex pivotColumnPosition,
00569 double work[],
00570 unsigned int workArea2[],
00571 int increment,
00572 int increment2,
00573 T markRow[] ,
00574 int largeInteger)
00575 {
00576 int *indexColumnU = indexColumnU_;
00577 CoinBigIndex *startColumnU = startColumnU_;
00578 int *numberInColumn = numberInColumn_;
00579 double *elementU = elementU_;
00580 int *indexRowU = indexRowU_;
00581 CoinBigIndex *startRowU = startRowU_;
00582 int *numberInRow = numberInRow_;
00583 double *elementL = elementL_;
00584 int *indexRowL = indexRowL_;
00585 int *saveColumn = saveColumn_;
00586 int *nextRow = nextRow_;
00587 int *lastRow = lastRow_;
00588
00589
00590 int numberInPivotRow = numberInRow[pivotRow] - 1;
00591 CoinBigIndex startColumn = startColumnU[pivotColumn];
00592 int numberInPivotColumn = numberInColumn[pivotColumn] - 1;
00593 CoinBigIndex endColumn = startColumn + numberInPivotColumn + 1;
00594 int put = 0;
00595 CoinBigIndex startRow = startRowU[pivotRow];
00596 CoinBigIndex endRow = startRow + numberInPivotRow + 1;
00597
00598 if ( pivotColumnPosition < 0 ) {
00599 for ( pivotColumnPosition = startRow; pivotColumnPosition < endRow; pivotColumnPosition++ ) {
00600 int iColumn = indexColumnU[pivotColumnPosition];
00601 if ( iColumn != pivotColumn ) {
00602 saveColumn[put++] = iColumn;
00603 } else {
00604 break;
00605 }
00606 }
00607 } else {
00608 for (CoinBigIndex i = startRow ; i < pivotColumnPosition ; i++ ) {
00609 saveColumn[put++] = indexColumnU[i];
00610 }
00611 }
00612 assert (pivotColumnPosition<endRow);
00613 assert (indexColumnU[pivotColumnPosition]==pivotColumn);
00614 pivotColumnPosition++;
00615 for ( ; pivotColumnPosition < endRow; pivotColumnPosition++ ) {
00616 saveColumn[put++] = indexColumnU[pivotColumnPosition];
00617 }
00618
00619 int next = nextRow[pivotRow];
00620 int last = lastRow[pivotRow];
00621
00622 nextRow[last] = next;
00623 lastRow[next] = last;
00624 nextRow[pivotRow] = numberGoodU_;
00625 lastRow[pivotRow] = -2;
00626 numberInRow[pivotRow] = 0;
00627
00628 CoinBigIndex l = lengthL_;
00629
00630 if ( l + numberInPivotColumn > lengthAreaL_ ) {
00631
00632 printf("more memory needed in middle of invert\n");
00633 return false;
00634 }
00635
00636 CoinBigIndex lSave = l;
00637
00638 pivotRowL_[numberGoodL_] = pivotRow;
00639 startColumnL_[numberGoodL_] = l;
00640 numberGoodL_++;
00641 startColumnL_[numberGoodL_] = l + numberInPivotColumn;
00642 lengthL_ += numberInPivotColumn;
00643 if ( pivotRowPosition < 0 ) {
00644 for ( pivotRowPosition = startColumn; pivotRowPosition < endColumn; pivotRowPosition++ ) {
00645 int iRow = indexRowU[pivotRowPosition];
00646 if ( iRow != pivotRow ) {
00647 indexRowL[l] = iRow;
00648 elementL[l] = elementU[pivotRowPosition];
00649 markRow[iRow] = l - lSave;
00650 l++;
00651
00652 CoinBigIndex start = startRowU[iRow];
00653 CoinBigIndex end = start + numberInRow[iRow];
00654 CoinBigIndex where = start;
00655
00656 while ( indexColumnU[where] != pivotColumn ) {
00657 where++;
00658 }
00659 #if DEBUG_COIN
00660 if ( where >= end ) {
00661 abort ( );
00662 }
00663 #endif
00664 indexColumnU[where] = indexColumnU[end - 1];
00665 numberInRow[iRow]--;
00666 } else {
00667 break;
00668 }
00669 }
00670 } else {
00671 CoinBigIndex i;
00672
00673 for ( i = startColumn; i < pivotRowPosition; i++ ) {
00674 int iRow = indexRowU[i];
00675
00676 markRow[iRow] = l - lSave;
00677 indexRowL[l] = iRow;
00678 elementL[l] = elementU[i];
00679 l++;
00680
00681 CoinBigIndex start = startRowU[iRow];
00682 CoinBigIndex end = start + numberInRow[iRow];
00683 CoinBigIndex where = start;
00684
00685 while ( indexColumnU[where] != pivotColumn ) {
00686 where++;
00687 }
00688 #if DEBUG_COIN
00689 if ( where >= end ) {
00690 abort ( );
00691 }
00692 #endif
00693 indexColumnU[where] = indexColumnU[end - 1];
00694 numberInRow[iRow]--;
00695 assert (numberInRow[iRow]>=0);
00696 }
00697 }
00698 assert (pivotRowPosition<endColumn);
00699 assert (indexRowU[pivotRowPosition]==pivotRow);
00700 double pivotElement = elementU[pivotRowPosition];
00701 double pivotMultiplier = 1.0 / pivotElement;
00702
00703 pivotRegion_[numberGoodU_] = pivotMultiplier;
00704 pivotRowPosition++;
00705 for ( ; pivotRowPosition < endColumn; pivotRowPosition++ ) {
00706 int iRow = indexRowU[pivotRowPosition];
00707
00708 markRow[iRow] = l - lSave;
00709 indexRowL[l] = iRow;
00710 elementL[l] = elementU[pivotRowPosition];
00711 l++;
00712
00713 CoinBigIndex start = startRowU[iRow];
00714 CoinBigIndex end = start + numberInRow[iRow];
00715 CoinBigIndex where = start;
00716
00717 while ( indexColumnU[where] != pivotColumn ) {
00718 where++;
00719 }
00720 #if DEBUG_COIN
00721 if ( where >= end ) {
00722 abort ( );
00723 }
00724 #endif
00725 indexColumnU[where] = indexColumnU[end - 1];
00726 numberInRow[iRow]--;
00727 assert (numberInRow[iRow]>=0);
00728 }
00729 markRow[pivotRow] = largeInteger;
00730
00731 numberInColumn[pivotColumn] = 0;
00732
00733 int *indexL = &indexRowL[lSave];
00734 double *multipliersL = &elementL[lSave];
00735
00736
00737 int j;
00738
00739 for ( j = 0; j < numberInPivotColumn; j++ ) {
00740 multipliersL[j] *= pivotMultiplier;
00741 }
00742
00743 CoinBigIndex iErase;
00744 for ( iErase = 0; iErase < increment2 * numberInPivotRow;
00745 iErase++ ) {
00746 workArea2[iErase] = 0;
00747 }
00748 CoinBigIndex added = numberInPivotRow * numberInPivotColumn;
00749 unsigned int *temp2 = workArea2;
00750
00751
00752 int jColumn;
00753 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00754 int iColumn = saveColumn[jColumn];
00755 CoinBigIndex startColumn = startColumnU[iColumn];
00756 CoinBigIndex endColumn = startColumn + numberInColumn[iColumn];
00757 int iRow = indexRowU[startColumn];
00758 double value = elementU[startColumn];
00759 double largest;
00760 CoinBigIndex put = startColumn;
00761 CoinBigIndex positionLargest = -1;
00762 double thisPivotValue = 0.0;
00763
00764
00765 bool checkLargest;
00766 int mark = markRow[iRow];
00767
00768 if ( mark < 0 ) {
00769 largest = fabs ( value );
00770 positionLargest = put;
00771 put++;
00772 checkLargest = false;
00773 } else {
00774
00775 largest = 0.0;
00776 checkLargest = true;
00777 if ( mark != largeInteger ) {
00778
00779 work[mark] = value;
00780 int word = mark >> COINFACTORIZATION_SHIFT_PER_INT;
00781 int bit = mark & COINFACTORIZATION_MASK_PER_INT;
00782
00783 temp2[word] = temp2[word] | ( 1 << bit );
00784 added--;
00785 } else {
00786 thisPivotValue = value;
00787 }
00788 }
00789 CoinBigIndex i;
00790 for ( i = startColumn + 1; i < endColumn; i++ ) {
00791 iRow = indexRowU[i];
00792 value = elementU[i];
00793 int mark = markRow[iRow];
00794
00795 if ( mark < 0 ) {
00796
00797 indexRowU[put] = iRow;
00798 elementU[put] = value;;
00799 if ( checkLargest ) {
00800 double absValue = fabs ( value );
00801
00802 if ( absValue > largest ) {
00803 largest = absValue;
00804 positionLargest = put;
00805 }
00806 }
00807 put++;
00808 } else if ( mark != largeInteger ) {
00809
00810 work[mark] = value;;
00811 int word = mark >> COINFACTORIZATION_SHIFT_PER_INT;
00812 int bit = mark & COINFACTORIZATION_MASK_PER_INT;
00813
00814 temp2[word] = temp2[word] | ( 1 << bit );
00815 added--;
00816 } else {
00817 thisPivotValue = value;
00818 }
00819 }
00820
00821 elementU[put] = elementU[startColumn];
00822 indexRowU[put] = indexRowU[startColumn];
00823 if ( positionLargest == startColumn ) {
00824 positionLargest = put;
00825 }
00826 put++;
00827 elementU[startColumn] = thisPivotValue;
00828 indexRowU[startColumn] = pivotRow;
00829
00830 startColumn++;
00831 numberInColumn[iColumn] = put - startColumn;
00832 numberInColumnPlus_[iColumn]++;
00833 startColumnU[iColumn]++;
00834
00835 int next = nextColumn_[iColumn];
00836 CoinBigIndex space;
00837
00838 space = startColumnU[next] - put - numberInColumnPlus_[next];
00839
00840 if ( numberInPivotColumn > space ) {
00841
00842 if ( !getColumnSpace ( iColumn, numberInPivotColumn ) ) {
00843 return false;
00844 }
00845
00846 positionLargest = positionLargest + startColumnU[iColumn] - startColumn;
00847 startColumn = startColumnU[iColumn];
00848 put = startColumn + numberInColumn[iColumn];
00849 }
00850 double tolerance = zeroTolerance_;
00851
00852 for ( j = 0; j < numberInPivotColumn; j++ ) {
00853 value = work[j] - thisPivotValue * multipliersL[j];
00854 double absValue = fabs ( value );
00855
00856 if ( absValue > tolerance ) {
00857 work[j] = 0.0;
00858 elementU[put] = value;
00859 indexRowU[put] = indexL[j];
00860 if ( absValue > largest ) {
00861 largest = absValue;
00862 positionLargest = put;
00863 }
00864 put++;
00865 } else {
00866 work[j] = 0.0;
00867 added--;
00868 int word = j >> COINFACTORIZATION_SHIFT_PER_INT;
00869 int bit = j & COINFACTORIZATION_MASK_PER_INT;
00870
00871 if ( temp2[word] & ( 1 << bit ) ) {
00872
00873 iRow = indexL[j];
00874 CoinBigIndex start = startRowU[iRow];
00875 CoinBigIndex end = start + numberInRow[iRow];
00876 CoinBigIndex where = start;
00877
00878 while ( indexColumnU[where] != iColumn ) {
00879 where++;
00880 }
00881 #if DEBUG_COIN
00882 if ( where >= end ) {
00883 abort ( );
00884 }
00885 #endif
00886 indexColumnU[where] = indexColumnU[end - 1];
00887 numberInRow[iRow]--;
00888 } else {
00889
00890 int word = j >> COINFACTORIZATION_SHIFT_PER_INT;
00891 int bit = j & COINFACTORIZATION_MASK_PER_INT;
00892
00893 temp2[word] = temp2[word] | ( 1 << bit );
00894 }
00895 }
00896 }
00897 numberInColumn[iColumn] = put - startColumn;
00898
00899 if ( positionLargest >= 0 ) {
00900 value = elementU[positionLargest];
00901 iRow = indexRowU[positionLargest];
00902 elementU[positionLargest] = elementU[startColumn];
00903 indexRowU[positionLargest] = indexRowU[startColumn];
00904 elementU[startColumn] = value;
00905 indexRowU[startColumn] = iRow;
00906 }
00907
00908 if ( nextCount_[iColumn + numberRows_] != -2 ) {
00909
00910 deleteLink ( iColumn + numberRows_ );
00911 addLink ( iColumn + numberRows_, numberInColumn[iColumn] );
00912 }
00913 temp2 += increment2;
00914 }
00915
00916 unsigned int *putBase = workArea2;
00917 int bigLoops = numberInPivotColumn >> COINFACTORIZATION_SHIFT_PER_INT;
00918 int i = 0;
00919
00920
00921 while ( bigLoops ) {
00922 bigLoops--;
00923 int bit;
00924 for ( bit = 0; bit < COINFACTORIZATION_BITS_PER_INT; i++, bit++ ) {
00925 unsigned int *putThis = putBase;
00926 int iRow = indexL[i];
00927
00928
00929 int number = 0;
00930 int jColumn;
00931
00932 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00933 unsigned int test = *putThis;
00934
00935 putThis += increment2;
00936 test = 1 - ( ( test >> bit ) & 1 );
00937 number += test;
00938 }
00939 int next = nextRow[iRow];
00940 CoinBigIndex space;
00941
00942 space = startRowU[next] - startRowU[iRow];
00943 number += numberInRow[iRow];
00944 if ( space < number ) {
00945 if ( !getRowSpace ( iRow, number ) ) {
00946 return false;
00947 }
00948 }
00949
00950 putThis = putBase;
00951 next = nextRow[iRow];
00952 number = numberInRow[iRow];
00953 CoinBigIndex end = startRowU[iRow] + number;
00954 int saveIndex = indexColumnU[startRowU[next]];
00955
00956
00957 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00958 unsigned int test = *putThis;
00959
00960 putThis += increment2;
00961 test = 1 - ( ( test >> bit ) & 1 );
00962 indexColumnU[end] = saveColumn[jColumn];
00963 end += test;
00964 }
00965
00966 indexColumnU[startRowU[next]] = saveIndex;
00967 markRow[iRow] = -1;
00968 number = end - startRowU[iRow];
00969 numberInRow[iRow] = number;
00970 deleteLink ( iRow );
00971 addLink ( iRow, number );
00972 }
00973 putBase++;
00974 }
00975 int bit;
00976
00977 for ( bit = 0; i < numberInPivotColumn; i++, bit++ ) {
00978 unsigned int *putThis = putBase;
00979 int iRow = indexL[i];
00980
00981
00982 int number = 0;
00983 int jColumn;
00984
00985 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00986 unsigned int test = *putThis;
00987
00988 putThis += increment2;
00989 test = 1 - ( ( test >> bit ) & 1 );
00990 number += test;
00991 }
00992 int next = nextRow[iRow];
00993 CoinBigIndex space;
00994
00995 space = startRowU[next] - startRowU[iRow];
00996 number += numberInRow[iRow];
00997 if ( space < number ) {
00998 if ( !getRowSpace ( iRow, number ) ) {
00999 return false;
01000 }
01001 }
01002
01003 putThis = putBase;
01004 next = nextRow[iRow];
01005 number = numberInRow[iRow];
01006 CoinBigIndex end = startRowU[iRow] + number;
01007 int saveIndex;
01008
01009 saveIndex = indexColumnU[startRowU[next]];
01010
01011
01012 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
01013 unsigned int test = *putThis;
01014
01015 putThis += increment2;
01016 test = 1 - ( ( test >> bit ) & 1 );
01017
01018 indexColumnU[end] = saveColumn[jColumn];
01019 end += test;
01020 }
01021 indexColumnU[startRowU[next]] = saveIndex;
01022 markRow[iRow] = -1;
01023 number = end - startRowU[iRow];
01024 numberInRow[iRow] = number;
01025 deleteLink ( iRow );
01026 addLink ( iRow, number );
01027 }
01028 markRow[pivotRow] = -1;
01029
01030 deleteLink ( pivotRow );
01031 deleteLink ( pivotColumn + numberRows_ );
01032 totalElements_ += added;
01033 return true;
01034 }
01035
01036
01038
01039 protected:
01040
01043
01044 double pivotTolerance_;
01046 double zeroTolerance_;
01048 double slackValue_;
01050 double areaFactor_;
01052 double relaxCheck_;
01054 int numberRows_;
01056 int numberRowsExtra_;
01058 int maximumRowsExtra_;
01060 int numberColumns_;
01062 int numberColumnsExtra_;
01064 int maximumColumnsExtra_;
01066 int numberGoodU_;
01068 int numberGoodL_;
01070 int maximumPivots_;
01072 int numberPivots_;
01075 CoinBigIndex totalElements_;
01077 CoinBigIndex factorElements_;
01079 int *pivotColumn_;
01081 int *permute_;
01083 int *permuteBack_;
01085 int *pivotColumnBack_;
01087 int status_;
01088
01093
01094
01096 int messageLevel_;
01097
01099 int numberTrials_;
01101 CoinBigIndex *startRowU_;
01102
01104 int *numberInRow_;
01105
01107 int *numberInColumn_;
01108
01110 int *numberInColumnPlus_;
01111
01114 int *firstCount_;
01115
01117 int *nextCount_;
01118
01120 int *lastCount_;
01121
01123 int *nextColumn_;
01124
01126 int *lastColumn_;
01127
01129 int *nextRow_;
01130
01132 int *lastRow_;
01133
01135 int *saveColumn_;
01136
01138 int *markRow_;
01139
01141 int biggerDimension_;
01142
01144 int *indexColumnU_;
01145
01147 int *pivotRowL_;
01148
01150 double *pivotRegion_;
01151
01153 int numberSlacks_;
01154
01156 int numberU_;
01157
01159 CoinBigIndex maximumU_;
01160
01162
01163
01165 CoinBigIndex lengthU_;
01166
01168 CoinBigIndex lengthAreaU_;
01169
01171 double *elementU_;
01172
01174 int *indexRowU_;
01175
01177 CoinBigIndex *startColumnU_;
01178
01180 CoinBigIndex *convertRowToColumnU_;
01181
01183 int numberL_;
01184
01186 int baseL_;
01187
01189 CoinBigIndex lengthL_;
01190
01192 CoinBigIndex lengthAreaL_;
01193
01195 double *elementL_;
01196
01198 int *indexRowL_;
01199
01201 CoinBigIndex *startColumnL_;
01202
01204 int numberR_;
01205
01207 CoinBigIndex lengthR_;
01208
01210 CoinBigIndex lengthAreaR_;
01211
01213 double *elementR_;
01214
01216 int *indexRowR_;
01217
01219 CoinBigIndex *startColumnR_;
01220
01222 double * denseArea_;
01223
01225 int * densePermute_;
01226
01228 int numberDense_;
01229
01231 int denseThreshold_;
01232
01234 CoinBigIndex numberCompressions_;
01235
01237 bool doForrestTomlin_;
01238
01240 mutable bool collectStatistics_;
01241
01243 mutable double ftranCountInput_;
01244 mutable double ftranCountAfterL_;
01245 mutable double ftranCountAfterR_;
01246 mutable double ftranCountAfterU_;
01247 mutable double btranCountInput_;
01248 mutable double btranCountAfterU_;
01249 mutable double btranCountAfterR_;
01250 mutable double btranCountAfterL_;
01251
01253 mutable int numberFtranCounts_;
01254 mutable int numberBtranCounts_;
01255
01257 double ftranAverageAfterL_;
01258 double ftranAverageAfterR_;
01259 double ftranAverageAfterU_;
01260 double btranAverageAfterU_;
01261 double btranAverageAfterR_;
01262 double btranAverageAfterL_;
01263
01265 int sparseThreshold_;
01266
01268 int sparseThreshold2_;
01269
01271 CoinBigIndex * startRowL_;
01272
01274 int * indexColumnL_;
01275
01277 double * elementByRowL_;
01278
01280 mutable int * sparse_;
01284 int biasLU_;
01286 };
01287
01288 #ifdef COIN_HAS_DENSE
01289 #define DENSE_CODE 1
01290 #endif
01291 #endif