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
00016 class CoinPackedMatrix;
00017 class CoinIndexedVector;
00045 #ifndef COIN_BIG_INDEX
00046 typedef int CoinBigIndex;
00047 #else
00048 typedef long CoinBigIndex;
00049 #endif
00050
00051
00052 class CoinFactorization {
00053 friend void CoinFactorizationUnitTest( const std::string & mpsDir );
00054
00055 public:
00056
00059
00060 CoinFactorization ( );
00062 CoinFactorization ( const CoinFactorization &other);
00063
00065 ~CoinFactorization ( );
00067 void show_self ( ) const;
00069 void sort ( ) const;
00071 CoinFactorization & operator = ( const CoinFactorization & other );
00073
00083 int factorize ( const CoinPackedMatrix & matrix,
00084 int rowIsBasic[], int columnIsBasic[] ,
00085 double areaFactor = 0.0 );
00096 int factorize ( int numberRows,
00097 int numberColumns,
00098 CoinBigIndex numberElements,
00099 CoinBigIndex maximumL,
00100 CoinBigIndex maximumU,
00101 const int indicesRow[],
00102 const int indicesColumn[], const double elements[] ,
00103 int permutation[],
00104 double areaFactor = 0.0);
00109 int factorizePart1 ( int numberRows,
00110 int numberColumns,
00111 CoinBigIndex estimateNumberElements,
00112 int * indicesRow[],
00113 int * indicesColumn[],
00114 double * elements[],
00115 double areaFactor = 0.0);
00122 int factorizePart2 (int permutation[],int exactNumberElements);
00124
00127
00128 inline int status ( ) const {
00129 return status_;
00130 };
00132 inline int pivots ( ) const {
00133 return numberPivots_;
00134 };
00136 inline int *permute ( ) const {
00137 return permute_;
00138 };
00140 inline int *pivotColumn ( ) const {
00141 return pivotColumn_;
00142 };
00144 inline int *permuteBack ( ) const {
00145 return permuteBack_;
00146 };
00148 inline int *pivotColumnBack ( ) const {
00149 return pivotColumnBack_;
00150 };
00152 inline int numberRowsExtra ( ) const {
00153 return numberRowsExtra_;
00154 };
00156 inline int numberRows ( ) const {
00157 return numberRows_;
00158 };
00160 inline int maximumRowsExtra ( ) const {
00161 return maximumRowsExtra_;
00162 };
00164 inline int numberColumns ( ) const {
00165 return numberColumns_;
00166 };
00168 inline int numberElements ( ) const {
00169 return totalElements_;
00170 };
00172 inline int numberForrestTomlin ( ) const {
00173 return numberInColumn_[numberColumnsExtra_];
00174 };
00176 inline int numberGoodColumns ( ) const {
00177 return numberGoodU_;
00178 };
00180 inline double areaFactor ( ) const {
00181 return areaFactor_;
00182 };
00183 inline void areaFactor ( double value ) {
00184 areaFactor_=value;
00185 };
00187 inline void relaxAccuracyCheck(double value)
00188 { relaxCheck_ = value;};
00189 inline double getAccuracyCheck() const
00190 { return relaxCheck_;};
00192 inline bool increasingRows ( ) const
00193 { return true; };
00199 inline void increasingRows ( int value ) {};
00201 inline int messageLevel ( ) const {
00202 return messageLevel_ ;
00203 };
00204 void messageLevel ( int value );
00206 inline int maximumPivots ( ) const {
00207 return maximumPivots_ ;
00208 };
00209 void maximumPivots ( int value );
00210
00212 inline int denseThreshold() const
00213 { return denseThreshold_;};
00215 inline void setDenseThreshold(int value)
00216 { denseThreshold_ = value;};
00218 inline double pivotTolerance ( ) const {
00219 return pivotTolerance_ ;
00220 };
00221 void pivotTolerance ( double value );
00223 inline double zeroTolerance ( ) const {
00224 return zeroTolerance_ ;
00225 };
00226 void zeroTolerance ( double value );
00228 inline double slackValue ( ) const {
00229 return slackValue_ ;
00230 };
00231 void slackValue ( double value );
00233 double maximumCoefficient() const;
00235
00238
00240 inline CoinBigIndex numberElementsU ( ) const {
00241 return lengthU_;
00242 };
00244 inline CoinBigIndex lengthAreaU ( ) const {
00245 return lengthAreaU_;
00246 };
00248 inline CoinBigIndex numberElementsL ( ) const {
00249 return lengthL_;
00250 };
00252 inline CoinBigIndex lengthAreaL ( ) const {
00253 return lengthAreaL_;
00254 };
00256 inline CoinBigIndex numberCompressions() const
00257 { return numberCompressions_;};
00261 inline int biasLU() const
00262 { return biasLU_;};
00263 inline void setBiasLU(int value)
00264 { biasLU_=value;};
00266
00269
00277 int replaceColumn ( CoinIndexedVector * regionSparse,
00278 int pivotRow,
00279 double pivotCheck ,
00280 bool checkBeforeModifying=false);
00282
00292 int updateColumnFT ( CoinIndexedVector * regionSparse,
00293 CoinIndexedVector * regionSparse2);
00296 int updateColumn ( CoinIndexedVector * regionSparse,
00297 CoinIndexedVector * regionSparse2,
00298 bool noPermute=false) const;
00303 int updateColumnTranspose ( CoinIndexedVector * regionSparse,
00304 CoinIndexedVector * regionSparse2) const;
00306 void goSparse();
00308 int sparseThreshold ( ) const;
00310 void sparseThreshold ( int value );
00312 void getWeights(int * weights) const;
00314
00315
00319
00320 inline void clearArrays()
00321 { gutsOfDestructor();};
00323
00326
00329 int add ( CoinBigIndex numberElements,
00330 int indicesRow[],
00331 int indicesColumn[], double elements[] );
00332
00335 int addColumn ( CoinBigIndex numberElements,
00336 int indicesRow[], double elements[] );
00337
00340 int addRow ( CoinBigIndex numberElements,
00341 int indicesColumn[], double elements[] );
00342
00344 int deleteColumn ( int Row );
00346 int deleteRow ( int Row );
00347
00351 int replaceRow ( int whichRow, int numberElements,
00352 const int indicesColumn[], const double elements[] );
00354 void emptyRows(int numberToEmpty, const int which[]);
00356 protected:
00357
00359
00360 void getAreas ( int numberRows,
00361 int numberColumns,
00362 CoinBigIndex maximumL,
00363 CoinBigIndex maximumU );
00364
00367 void preProcess ( int state,
00368 int possibleDuplicates = -1 );
00370 int factor ( );
00373 int factorSparse ( );
00376 int factorDense ( );
00377
00379 bool pivotOneOtherRow ( int pivotRow,
00380 int pivotColumn );
00382 bool pivotRowSingleton ( int pivotRow,
00383 int pivotColumn );
00385 bool pivotColumnSingleton ( int pivotRow,
00386 int pivotColumn );
00387
00392 bool getColumnSpace ( int iColumn,
00393 int extraNeeded );
00394
00398 bool getColumnSpaceIterateR ( int iColumn, double value,
00399 int iRow);
00405 CoinBigIndex getColumnSpaceIterate ( int iColumn, double value,
00406 int iRow);
00410 bool getRowSpace ( int iRow, int extraNeeded );
00411
00415 bool getRowSpaceIterate ( int iRow,
00416 int extraNeeded );
00418 void checkConsistency ( );
00420 inline void addLink ( int index, int count ) {
00421 int next = firstCount_[count];
00422 lastCount_[index] = -2 - count;
00423 if ( next < 0 ) {
00424
00425 firstCount_[count] = index;
00426 nextCount_[index] = -1;
00427 } else {
00428 firstCount_[count] = index;
00429 nextCount_[index] = next;
00430 lastCount_[next] = index;
00431 }};
00433 inline void deleteLink ( int index ) {
00434 int next = nextCount_[index];
00435 int last = lastCount_[index];
00436 if ( last >= 0 ) {
00437 nextCount_[last] = next;
00438 } else {
00439 int count = -last - 2;
00440
00441 firstCount_[count] = next;
00442 }
00443 if ( next >= 0 ) {
00444 lastCount_[next] = last;
00445 }
00446 nextCount_[index] = -2;
00447 lastCount_[index] = -2;
00448 return;
00449 };
00451 void separateLinks(int count,bool rowsFirst);
00453 void cleanup ( );
00454
00456 void updateColumnL ( CoinIndexedVector * region, int * indexIn ) const;
00458 void updateColumnLDensish ( CoinIndexedVector * region, int * indexIn ) const;
00460 void updateColumnLSparse ( CoinIndexedVector * region, int * indexIn ) const;
00462 void updateColumnLSparsish ( CoinIndexedVector * region, int * indexIn ) const;
00463
00465 void updateColumnR ( CoinIndexedVector * region ) const;
00468 void updateColumnRFT ( CoinIndexedVector * region, int * indexIn );
00469
00471 void updateColumnU ( CoinIndexedVector * region, int * indexIn) const;
00472
00474 void updateColumnUSparse ( CoinIndexedVector * regionSparse,
00475 int * indexIn) const;
00477 void updateColumnUSparsish ( CoinIndexedVector * regionSparse,
00478 int * indexIn) const;
00480 void updateColumnUDensish ( CoinIndexedVector * regionSparse,
00481 int * indexIn) const;
00483 void permuteBack ( CoinIndexedVector * regionSparse,
00484 CoinIndexedVector * outVector) const;
00485
00488 void updateColumnTransposeU ( CoinIndexedVector * region,
00489 int smallestIndex) const;
00492 void updateColumnTransposeUSparsish ( CoinIndexedVector * region,
00493 int smallestIndex) const;
00496 void updateColumnTransposeUDensish ( CoinIndexedVector * region,
00497 int smallestIndex) const;
00500 void updateColumnTransposeUSparse ( CoinIndexedVector * region) const;
00501
00503 void updateColumnTransposeR ( CoinIndexedVector * region ) const;
00505 void updateColumnTransposeRDensish ( CoinIndexedVector * region ) const;
00507 void updateColumnTransposeRSparse ( CoinIndexedVector * region ) const;
00508
00510 void updateColumnTransposeL ( CoinIndexedVector * region ) const;
00512 void updateColumnTransposeLDensish ( CoinIndexedVector * region ) const;
00514 void updateColumnTransposeLByRow ( CoinIndexedVector * region ) const;
00516 void updateColumnTransposeLSparsish ( CoinIndexedVector * region ) const;
00518 void updateColumnTransposeLSparse ( CoinIndexedVector * region ) const;
00519
00522 int checkPivot(double saveFromU, double oldPivot) const;
00524 void gutsOfDestructor();
00526 void gutsOfInitialize(int type);
00527 void gutsOfCopy(const CoinFactorization &other);
00528
00530 void resetStatistics();
00531
00532
00533 #ifdef INT_IS_8
00534 #define COINFACTORIZATION_BITS_PER_INT 64
00535 #define COINFACTORIZATION_SHIFT_PER_INT 6
00536 #define COINFACTORIZATION_MASK_PER_INT 0x3f
00537 #else
00538 #define COINFACTORIZATION_BITS_PER_INT 32
00539 #define COINFACTORIZATION_SHIFT_PER_INT 5
00540 #define COINFACTORIZATION_MASK_PER_INT 0x1f
00541 #endif
00542 template <class T> bool
00543 pivot ( int pivotRow,
00544 int pivotColumn,
00545 int pivotRowPosition,
00546 int pivotColumnPosition,
00547 double work[],
00548 unsigned int workArea2[],
00549 int increment,
00550 int increment2,
00551 T markRow[] ,
00552 int largeInteger)
00553 {
00554 int *indexColumnU = indexColumnU_;
00555 CoinBigIndex *startColumnU = startColumnU_;
00556 int *numberInColumn = numberInColumn_;
00557 double *elementU = elementU_;
00558 int *indexRowU = indexRowU_;
00559 CoinBigIndex *startRowU = startRowU_;
00560 int *numberInRow = numberInRow_;
00561 double *elementL = elementL_;
00562 int *indexRowL = indexRowL_;
00563 int *saveColumn = saveColumn_;
00564 int *nextRow = nextRow_;
00565 int *lastRow = lastRow_;
00566
00567
00568 int numberInPivotRow = numberInRow[pivotRow] - 1;
00569 CoinBigIndex startColumn = startColumnU[pivotColumn];
00570 int numberInPivotColumn = numberInColumn[pivotColumn] - 1;
00571 CoinBigIndex endColumn = startColumn + numberInPivotColumn + 1;
00572 int put = 0;
00573 CoinBigIndex startRow = startRowU[pivotRow];
00574 CoinBigIndex endRow = startRow + numberInPivotRow + 1;
00575
00576 if ( pivotColumnPosition < 0 ) {
00577 CoinBigIndex i;
00578 for ( i = startRow; i < endRow; i++ ) {
00579 int iColumn = indexColumnU[i];
00580
00581 if ( iColumn != pivotColumn ) {
00582 saveColumn[put] = iColumn;
00583 put++;
00584 } else {
00585 pivotColumnPosition = i;
00586 }
00587 }
00588 } else {
00589 CoinBigIndex i;
00590
00591 for ( i = startRow; i < pivotColumnPosition; i++ ) {
00592 int iColumn = indexColumnU[i];
00593
00594 saveColumn[put] = iColumn;
00595 put++;
00596 }
00597 for ( i = pivotColumnPosition + 1; i < endRow; i++ ) {
00598 int iColumn = indexColumnU[i];
00599
00600 saveColumn[put] = iColumn;
00601 put++;
00602 }
00603 }
00604
00605 int next = nextRow[pivotRow];
00606 int last = lastRow[pivotRow];
00607
00608 nextRow[last] = next;
00609 lastRow[next] = last;
00610 nextRow[pivotRow] = numberGoodU_;
00611 lastRow[pivotRow] = -2;
00612 numberInRow[pivotRow] = 0;
00613
00614 CoinBigIndex l = lengthL_;
00615
00616 if ( l + numberInPivotColumn > lengthAreaL_ ) {
00617
00618 std::cout << "more memory needed in middle of invert" << std::endl;
00619 return false;
00620 }
00621
00622 CoinBigIndex lSave = l;
00623
00624 pivotRowL_[numberGoodL_] = pivotRow;
00625 startColumnL_[numberGoodL_] = l;
00626 numberGoodL_++;
00627 startColumnL_[numberGoodL_] = l + numberInPivotColumn;
00628 lengthL_ += numberInPivotColumn;
00629 if ( pivotRowPosition < 0 ) {
00630 CoinBigIndex i;
00631 for ( i = startColumn; i < endColumn; i++ ) {
00632 int iRow = indexRowU[i];
00633 if ( iRow != pivotRow ) {
00634 indexRowL[l] = iRow;
00635 elementL[l] = elementU[i];
00636 markRow[iRow] = l - lSave;
00637 l++;
00638
00639 CoinBigIndex start = startRowU[iRow];
00640 CoinBigIndex end = start + numberInRow[iRow];
00641 CoinBigIndex where = start;
00642
00643 while ( indexColumnU[where] != pivotColumn ) {
00644 where++;
00645 }
00646 #if DEBUG_COIN
00647 if ( where >= end ) {
00648 abort ( );
00649 }
00650 #endif
00651 indexColumnU[where] = indexColumnU[end - 1];
00652 numberInRow[iRow]--;
00653 } else {
00654 pivotRowPosition = i;
00655 }
00656 }
00657 } else {
00658 CoinBigIndex i;
00659
00660 for ( i = startColumn; i < pivotRowPosition; i++ ) {
00661 int iRow = indexRowU[i];
00662
00663 markRow[iRow] = l - lSave;
00664 indexRowL[l] = iRow;
00665 elementL[l] = elementU[i];
00666 l++;
00667
00668 CoinBigIndex start = startRowU[iRow];
00669 CoinBigIndex end = start + numberInRow[iRow];
00670 CoinBigIndex where = start;
00671
00672 while ( indexColumnU[where] != pivotColumn ) {
00673 where++;
00674 }
00675 #if DEBUG_COIN
00676 if ( where >= end ) {
00677 abort ( );
00678 }
00679 #endif
00680 indexColumnU[where] = indexColumnU[end - 1];
00681 numberInRow[iRow]--;
00682 assert (numberInRow[iRow]>=0);
00683 }
00684 for ( i = pivotRowPosition + 1; i < endColumn; i++ ) {
00685 int iRow = indexRowU[i];
00686
00687 markRow[iRow] = l - lSave;
00688 indexRowL[l] = iRow;
00689 elementL[l] = elementU[i];
00690 l++;
00691
00692 CoinBigIndex start = startRowU[iRow];
00693 CoinBigIndex end = start + numberInRow[iRow];
00694 CoinBigIndex where = start;
00695
00696 while ( indexColumnU[where] != pivotColumn ) {
00697 where++;
00698 }
00699 #if DEBUG_COIN
00700 if ( where >= end ) {
00701 abort ( );
00702 }
00703 #endif
00704 indexColumnU[where] = indexColumnU[end - 1];
00705 numberInRow[iRow]--;
00706 assert (numberInRow[iRow]>=0);
00707 }
00708 }
00709 markRow[pivotRow] = largeInteger;
00710
00711 double pivotElement = elementU[pivotRowPosition];
00712 double pivotMultiplier = 1.0 / pivotElement;
00713
00714 pivotRegion_[numberGoodU_] = pivotMultiplier;
00715 numberInColumn[pivotColumn] = 0;
00716
00717 int *indexL = &indexRowL[lSave];
00718 double *multipliersL = &elementL[lSave];
00719
00720
00721 int j;
00722
00723 for ( j = 0; j < numberInPivotColumn; j++ ) {
00724 multipliersL[j] = pivotMultiplier * multipliersL[j];
00725 }
00726
00727 CoinBigIndex iErase;
00728 for ( iErase = 0; iErase < increment2 * numberInPivotRow;
00729 iErase++ ) {
00730 workArea2[iErase] = 0;
00731 }
00732 CoinBigIndex added = numberInPivotRow * numberInPivotColumn;
00733 unsigned int *temp2 = workArea2;
00734
00735
00736 int jColumn;
00737 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00738 int iColumn = saveColumn[jColumn];
00739 CoinBigIndex startColumn = startColumnU[iColumn];
00740 CoinBigIndex endColumn = startColumn + numberInColumn[iColumn];
00741 int iRow = indexRowU[startColumn];
00742 double value = elementU[startColumn];
00743 double largest;
00744 CoinBigIndex put = startColumn;
00745 CoinBigIndex positionLargest = -1;
00746 double thisPivotValue = 0.0;
00747
00748
00749 bool checkLargest;
00750 int mark = markRow[iRow];
00751
00752 if ( mark < 0 ) {
00753 largest = fabs ( value );
00754 positionLargest = put;
00755 put++;
00756 checkLargest = false;
00757 } else {
00758
00759 largest = 0.0;
00760 checkLargest = true;
00761 if ( mark != largeInteger ) {
00762
00763 work[mark] = value;
00764 int word = mark >> COINFACTORIZATION_SHIFT_PER_INT;
00765 int bit = mark & COINFACTORIZATION_MASK_PER_INT;
00766
00767 temp2[word] = temp2[word] | ( 1 << bit );
00768 added--;
00769 } else {
00770 thisPivotValue = value;
00771 }
00772 }
00773 CoinBigIndex i;
00774 for ( i = startColumn + 1; i < endColumn; i++ ) {
00775 iRow = indexRowU[i];
00776 value = elementU[i];
00777 int mark = markRow[iRow];
00778
00779 if ( mark < 0 ) {
00780
00781 indexRowU[put] = iRow;
00782 elementU[put] = value;;
00783 if ( checkLargest ) {
00784 double absValue = fabs ( value );
00785
00786 if ( absValue > largest ) {
00787 largest = absValue;
00788 positionLargest = put;
00789 }
00790 }
00791 put++;
00792 } else if ( mark != largeInteger ) {
00793
00794 work[mark] = value;;
00795 int word = mark >> COINFACTORIZATION_SHIFT_PER_INT;
00796 int bit = mark & COINFACTORIZATION_MASK_PER_INT;
00797
00798 temp2[word] = temp2[word] | ( 1 << bit );
00799 added--;
00800 } else {
00801 thisPivotValue = value;
00802 }
00803 }
00804
00805 elementU[put] = elementU[startColumn];
00806 indexRowU[put] = indexRowU[startColumn];
00807 if ( positionLargest == startColumn ) {
00808 positionLargest = put;
00809 }
00810 put++;
00811 elementU[startColumn] = thisPivotValue;
00812 indexRowU[startColumn] = pivotRow;
00813
00814 startColumn++;
00815 numberInColumn[iColumn] = put - startColumn;
00816 numberInColumnPlus_[iColumn]++;
00817 startColumnU[iColumn]++;
00818
00819 int next = nextColumn_[iColumn];
00820 CoinBigIndex space;
00821
00822 space = startColumnU[next] - put - numberInColumnPlus_[next];
00823
00824 if ( numberInPivotColumn > space ) {
00825
00826 if ( !getColumnSpace ( iColumn, numberInPivotColumn ) ) {
00827 return false;
00828 }
00829
00830 positionLargest = positionLargest + startColumnU[iColumn] - startColumn;
00831 startColumn = startColumnU[iColumn];
00832 put = startColumn + numberInColumn[iColumn];
00833 }
00834 double tolerance = zeroTolerance_;
00835
00836 for ( j = 0; j < numberInPivotColumn; j++ ) {
00837 value = work[j] - thisPivotValue * multipliersL[j];
00838 double absValue = fabs ( value );
00839
00840 if ( absValue > tolerance ) {
00841 work[j] = 0.0;
00842 elementU[put] = value;
00843 indexRowU[put] = indexL[j];
00844 if ( absValue > largest ) {
00845 largest = absValue;
00846 positionLargest = put;
00847 }
00848 put++;
00849 } else {
00850 work[j] = 0.0;
00851 added--;
00852 int word = j >> COINFACTORIZATION_SHIFT_PER_INT;
00853 int bit = j & COINFACTORIZATION_MASK_PER_INT;
00854
00855 if ( temp2[word] & ( 1 << bit ) ) {
00856
00857 iRow = indexL[j];
00858 CoinBigIndex start = startRowU[iRow];
00859 CoinBigIndex end = start + numberInRow[iRow];
00860 CoinBigIndex where = start;
00861
00862 while ( indexColumnU[where] != iColumn ) {
00863 where++;
00864 }
00865 #if DEBUG_COIN
00866 if ( where >= end ) {
00867 abort ( );
00868 }
00869 #endif
00870 indexColumnU[where] = indexColumnU[end - 1];
00871 numberInRow[iRow]--;
00872 } else {
00873
00874 int word = j >> COINFACTORIZATION_SHIFT_PER_INT;
00875 int bit = j & COINFACTORIZATION_MASK_PER_INT;
00876
00877 temp2[word] = temp2[word] | ( 1 << bit );
00878 }
00879 }
00880 }
00881 numberInColumn[iColumn] = put - startColumn;
00882
00883 if ( positionLargest >= 0 ) {
00884 value = elementU[positionLargest];
00885 iRow = indexRowU[positionLargest];
00886 elementU[positionLargest] = elementU[startColumn];
00887 indexRowU[positionLargest] = indexRowU[startColumn];
00888 elementU[startColumn] = value;
00889 indexRowU[startColumn] = iRow;
00890 }
00891
00892 if ( nextCount_[iColumn + numberRows_] != -2 ) {
00893
00894 deleteLink ( iColumn + numberRows_ );
00895 addLink ( iColumn + numberRows_, numberInColumn[iColumn] );
00896 }
00897 temp2 += increment2;
00898 }
00899
00900 unsigned int *putBase = workArea2;
00901 int bigLoops = numberInPivotColumn >> COINFACTORIZATION_SHIFT_PER_INT;
00902 int i = 0;
00903
00904
00905 while ( bigLoops ) {
00906 bigLoops--;
00907 int bit;
00908 for ( bit = 0; bit < COINFACTORIZATION_BITS_PER_INT; i++, bit++ ) {
00909 unsigned int *putThis = putBase;
00910 int iRow = indexL[i];
00911
00912
00913 int number = 0;
00914 int jColumn;
00915
00916 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00917 unsigned int test = *putThis;
00918
00919 putThis += increment2;
00920 test = 1 - ( ( test >> bit ) & 1 );
00921 number += test;
00922 }
00923 int next = nextRow[iRow];
00924 CoinBigIndex space;
00925
00926 space = startRowU[next] - startRowU[iRow];
00927 number += numberInRow[iRow];
00928 if ( space < number ) {
00929 if ( !getRowSpace ( iRow, number ) ) {
00930 return false;
00931 }
00932 }
00933
00934 putThis = putBase;
00935 next = nextRow[iRow];
00936 number = numberInRow[iRow];
00937 CoinBigIndex end = startRowU[iRow] + number;
00938 int saveIndex = indexColumnU[startRowU[next]];
00939
00940
00941 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00942 unsigned int test = *putThis;
00943
00944 putThis += increment2;
00945 test = 1 - ( ( test >> bit ) & 1 );
00946 indexColumnU[end] = saveColumn[jColumn];
00947 end += test;
00948 }
00949
00950 indexColumnU[startRowU[next]] = saveIndex;
00951 markRow[iRow] = -1;
00952 number = end - startRowU[iRow];
00953 numberInRow[iRow] = number;
00954 deleteLink ( iRow );
00955 addLink ( iRow, number );
00956 }
00957 putBase++;
00958 }
00959 int bit;
00960
00961 for ( bit = 0; i < numberInPivotColumn; i++, bit++ ) {
00962 unsigned int *putThis = putBase;
00963 int iRow = indexL[i];
00964
00965
00966 int number = 0;
00967 int jColumn;
00968
00969 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00970 unsigned int test = *putThis;
00971
00972 putThis += increment2;
00973 test = 1 - ( ( test >> bit ) & 1 );
00974 number += test;
00975 }
00976 int next = nextRow[iRow];
00977 CoinBigIndex space;
00978
00979 space = startRowU[next] - startRowU[iRow];
00980 number += numberInRow[iRow];
00981 if ( space < number ) {
00982 if ( !getRowSpace ( iRow, number ) ) {
00983 return false;
00984 }
00985 }
00986
00987 putThis = putBase;
00988 next = nextRow[iRow];
00989 number = numberInRow[iRow];
00990 CoinBigIndex end = startRowU[iRow] + number;
00991 int saveIndex;
00992
00993 saveIndex = indexColumnU[startRowU[next]];
00994
00995
00996 for ( jColumn = 0; jColumn < numberInPivotRow; jColumn++ ) {
00997 unsigned int test = *putThis;
00998
00999 putThis += increment2;
01000 test = 1 - ( ( test >> bit ) & 1 );
01001
01002 indexColumnU[end] = saveColumn[jColumn];
01003 end += test;
01004 }
01005 indexColumnU[startRowU[next]] = saveIndex;
01006 markRow[iRow] = -1;
01007 number = end - startRowU[iRow];
01008 numberInRow[iRow] = number;
01009 deleteLink ( iRow );
01010 addLink ( iRow, number );
01011 }
01012 markRow[pivotRow] = -1;
01013
01014 deleteLink ( pivotRow );
01015 deleteLink ( pivotColumn + numberRows_ );
01016 totalElements_ += added;
01017 return true;
01018 }
01019
01020
01022
01023 protected:
01024
01027
01028 double pivotTolerance_;
01030 double zeroTolerance_;
01032 double slackValue_;
01034 double areaFactor_;
01036 double relaxCheck_;
01038 int numberRows_;
01040 int numberRowsExtra_;
01042 int maximumRowsExtra_;
01044 int numberColumns_;
01046 int numberColumnsExtra_;
01048 int maximumColumnsExtra_;
01050 int numberGoodU_;
01052 int numberGoodL_;
01054 int maximumPivots_;
01056 int numberPivots_;
01059 CoinBigIndex totalElements_;
01061 CoinBigIndex factorElements_;
01063 int *pivotColumn_;
01065 int *permute_;
01067 int *permuteBack_;
01069 int *pivotColumnBack_;
01071 int status_;
01072
01077
01078
01080 int messageLevel_;
01081
01083 int numberTrials_;
01085 CoinBigIndex *startRowU_;
01086
01088 int *numberInRow_;
01089
01091 int *numberInColumn_;
01092
01094 int *numberInColumnPlus_;
01095
01098 int *firstCount_;
01099
01101 int *nextCount_;
01102
01104 int *lastCount_;
01105
01107 int *nextColumn_;
01108
01110 int *lastColumn_;
01111
01113 int *nextRow_;
01114
01116 int *lastRow_;
01117
01119 int *saveColumn_;
01120
01122 int *markRow_;
01123
01125 int biggerDimension_;
01126
01128 int *indexColumnU_;
01129
01131 int *pivotRowL_;
01132
01134 double *pivotRegion_;
01135
01137 int numberSlacks_;
01138
01140 int numberU_;
01141
01143
01144
01146 CoinBigIndex lengthU_;
01147
01149 CoinBigIndex lengthAreaU_;
01150
01152 double *elementU_;
01153
01155 int *indexRowU_;
01156
01158 CoinBigIndex *startColumnU_;
01159
01161 CoinBigIndex *convertRowToColumnU_;
01162
01164 int numberL_;
01165
01167 int baseL_;
01168
01170 CoinBigIndex lengthL_;
01171
01173 CoinBigIndex lengthAreaL_;
01174
01176 double *elementL_;
01177
01179 int *indexRowL_;
01180
01182 CoinBigIndex *startColumnL_;
01183
01185 int numberR_;
01186
01188 CoinBigIndex lengthR_;
01189
01191 CoinBigIndex lengthAreaR_;
01192
01194 double *elementR_;
01195
01197 int *indexRowR_;
01198
01200 CoinBigIndex *startColumnR_;
01201
01203 double * denseArea_;
01204
01206 int * densePermute_;
01207
01209 int numberDense_;
01210
01212 int denseThreshold_;
01213
01215 CoinBigIndex numberCompressions_;
01216
01218 bool doForrestTomlin_;
01219
01221 mutable bool collectStatistics_;
01222
01224 mutable double ftranCountInput_;
01225 mutable double ftranCountAfterL_;
01226 mutable double ftranCountAfterR_;
01227 mutable double ftranCountAfterU_;
01228 mutable double btranCountInput_;
01229 mutable double btranCountAfterU_;
01230 mutable double btranCountAfterR_;
01231 mutable double btranCountAfterL_;
01232
01234 mutable int numberFtranCounts_;
01235 mutable int numberBtranCounts_;
01236
01238 double ftranAverageAfterL_;
01239 double ftranAverageAfterR_;
01240 double ftranAverageAfterU_;
01241 double btranAverageAfterU_;
01242 double btranAverageAfterR_;
01243 double btranAverageAfterL_;
01244
01246 int sparseThreshold_;
01247
01249 int sparseThreshold2_;
01250
01252 CoinBigIndex * startRowL_;
01253
01255 int * indexColumnL_;
01256
01258 double * elementByRowL_;
01259
01261 mutable int * sparse_;
01265 int biasLU_;
01267 };
01268
01269 #ifdef COIN_USE_DENSE
01270 #define DENSE_CODE 1
01271 #endif
01272 #endif