/home/coin/SVN-release/Cbc-1.1.1/CoinUtils/src/CoinFactorization.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2002, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 
00004 /* 
00005    Authors
00006    
00007    John Forrest
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       //first with that count
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   /********************************* START LARGE TEMPLATE ********/
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   //store pivot columns (so can easily compress)
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   //take out this bit of indexColumnU
00619   int next = nextRow[pivotRow];
00620   int last = lastRow[pivotRow];
00621 
00622   nextRow[last] = next;
00623   lastRow[next] = last;
00624   nextRow[pivotRow] = numberGoodU_;     //use for permute
00625   lastRow[pivotRow] = -2;
00626   numberInRow[pivotRow] = 0;
00627   //store column in L, compress in U and take column out
00628   CoinBigIndex l = lengthL_;
00629 
00630   if ( l + numberInPivotColumn > lengthAreaL_ ) {
00631     //need more memory
00632     printf("more memory needed in middle of invert\n");
00633     return false;
00634   }
00635   //l+=currentAreaL_->elementByColumn-elementL;
00636   CoinBigIndex lSave = l;
00637 
00638   pivotRowL_[numberGoodL_] = pivotRow;
00639   startColumnL_[numberGoodL_] = l;      //for luck and first time
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         //take out of row list
00652         CoinBigIndex start = startRowU[iRow];
00653         CoinBigIndex end = start + numberInRow[iRow];
00654         CoinBigIndex where = start;
00655 
00656         while ( indexColumnU[where] != pivotColumn ) {
00657           where++;
00658         }                       /* endwhile */
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       //take out of row list
00681       CoinBigIndex start = startRowU[iRow];
00682       CoinBigIndex end = start + numberInRow[iRow];
00683       CoinBigIndex where = start;
00684 
00685       while ( indexColumnU[where] != pivotColumn ) {
00686         where++;
00687       }                         /* endwhile */
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     //take out of row list
00713     CoinBigIndex start = startRowU[iRow];
00714     CoinBigIndex end = start + numberInRow[iRow];
00715     CoinBigIndex where = start;
00716     
00717     while ( indexColumnU[where] != pivotColumn ) {
00718       where++;
00719     }                           /* endwhile */
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   //compress pivot column (move pivot to front including saved)
00731   numberInColumn[pivotColumn] = 0;
00732   //use end of L for temporary space
00733   int *indexL = &indexRowL[lSave];
00734   double *multipliersL = &elementL[lSave];
00735 
00736   //adjust
00737   int j;
00738 
00739   for ( j = 0; j < numberInPivotColumn; j++ ) {
00740     multipliersL[j] *= pivotMultiplier;
00741   }
00742   //zero out fill
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   //pack down and move to work
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     //compress column and find largest not updated
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       //need to find largest
00775       largest = 0.0;
00776       checkLargest = true;
00777       if ( mark != largeInteger ) {
00778         //will be updated
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 );       //say already in counts
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         //keep
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         //will be updated
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 );       //say already in counts
00815         added--;
00816       } else {
00817         thisPivotValue = value;
00818       }
00819     }
00820     //slot in pivot
00821     elementU[put] = elementU[startColumn];
00822     indexRowU[put] = indexRowU[startColumn];
00823     if ( positionLargest == startColumn ) {
00824       positionLargest = put;    //follow if was largest
00825     }
00826     put++;
00827     elementU[startColumn] = thisPivotValue;
00828     indexRowU[startColumn] = pivotRow;
00829     //clean up counts
00830     startColumn++;
00831     numberInColumn[iColumn] = put - startColumn;
00832     numberInColumnPlus_[iColumn]++;
00833     startColumnU[iColumn]++;
00834     //how much space have we got
00835     int next = nextColumn_[iColumn];
00836     CoinBigIndex space;
00837 
00838     space = startColumnU[next] - put - numberInColumnPlus_[next];
00839     //assume no zero elements
00840     if ( numberInPivotColumn > space ) {
00841       //getColumnSpace also moves fixed part
00842       if ( !getColumnSpace ( iColumn, numberInPivotColumn ) ) {
00843         return false;
00844       }
00845       //redo starts
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           //take out of row list
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           }                     /* endwhile */
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           //make sure won't be added
00890           int word = j >> COINFACTORIZATION_SHIFT_PER_INT;
00891           int bit = j & COINFACTORIZATION_MASK_PER_INT;
00892 
00893           temp2[word] = temp2[word] | ( 1 << bit );     //say already in counts
00894         }
00895       }
00896     }
00897     numberInColumn[iColumn] = put - startColumn;
00898     //move largest
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     //linked list for column
00908     if ( nextCount_[iColumn + numberRows_] != -2 ) {
00909       //modify linked list
00910       deleteLink ( iColumn + numberRows_ );
00911       addLink ( iColumn + numberRows_, numberInColumn[iColumn] );
00912     }
00913     temp2 += increment2;
00914   }
00915   //get space for row list
00916   unsigned int *putBase = workArea2;
00917   int bigLoops = numberInPivotColumn >> COINFACTORIZATION_SHIFT_PER_INT;
00918   int i = 0;
00919 
00920   // do linked lists and update counts
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       //get space
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       // now do
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       //add in
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       //put back next one in case zapped
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   }                             /* endwhile */
00975   int bit;
00976 
00977   for ( bit = 0; i < numberInPivotColumn; i++, bit++ ) {
00978     unsigned int *putThis = putBase;
00979     int iRow = indexL[i];
00980 
00981     //get space
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     // now do
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     //add in
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   //modify linked list for pivots
01030   deleteLink ( pivotRow );
01031   deleteLink ( pivotColumn + numberRows_ );
01032   totalElements_ += added;
01033   return true;
01034 }
01035 
01036   /********************************* END LARGE TEMPLATE ********/
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   //int increasingRows_;
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   //int baseU_;
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 // Dense coding
01288 #ifdef COIN_HAS_DENSE
01289 #define DENSE_CODE 1
01290 #endif
01291 #endif

Generated on Thu May 15 21:59:05 2008 by  doxygen 1.4.7