- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Bcps-0.91.0/CoinUtils/src/CoinPresolveMatrix.hpp

Go to the documentation of this file.

    00001 // Copyright (C) 2002, International Business Machines
    00002 // Corporation and others.  All Rights Reserved.
    00003 #ifndef CoinPresolveMatrix_H
    00004 #define CoinPresolveMatrix_H
    00005
    00006 #include "CoinPragma.hpp"
    00007 #include "CoinPackedMatrix.hpp"
    00008 #include "CoinMessage.hpp"
    00009 #include "CoinTime.hpp"
    00010
    00011 #include <cmath>
    00012 #include <cassert>
    00013 #include <cfloat>
    00014 #include <cassert>
    00015
    00024 #if defined(_MSC_VER)
    00025 // Avoid MS Compiler problem in recognizing type to delete
    00026 // by casting to type.
    00027 #define deleteAction(array,type) delete [] ((type) array)
    00028 #else
    00029 #define deleteAction(array,type) delete [] array
    00030 #endif
    00031
    00036 const double ZTOLDP      = 1e-12;
    00037 // But use a different one if we are doing doubletons etc
    00038 const double ZTOLDP2      = 1e-10;
    00039 //#define PRESOLVE_DEBUG 1
    00040 // Debugging macros/functions
    00041
    00042 #if PRESOLVE_DEBUG || PRESOLVE_CONSISTENCY
    00043 #define PRESOLVE_STMT(s)        s
    00044 #define PRESOLVEASSERT(x) \
    00045   ((x) ? 1 : \
    00046         ((std::cerr << "FAILED ASSERTION at line " \
    00047                     << __LINE__ << ":  " #x "\n"), abort(), 0))
    00048
    00049 inline void DIE(const char *s)  { std::cout<<s; abort(); }
    00050
    00051 // This code is used in [cr]done for columns and rows that are present in
    00052 // the presolved system.
    00053 #define PRESENT_IN_REDUCED      '\377'
    00054
    00055 #else
    00056
    00057 #define PRESOLVEASSERT(x)
    00058 #define PRESOLVE_STMT(s)
    00059
    00060 inline void DIE(const char *s)  {}
    00061
    00062 #endif
    00063
    00064 inline int ALIGN(int n, int m)  { return (((n + m - 1) / m) * m); }
    00065 inline int ALIGN_DOUBLE(int n)  { return ALIGN(n,sizeof(double)); }
    00066
    00067 // Plus infinity
    00068 #ifndef COIN_DBL_MAX
    00069 #define COIN_DBL_MAX DBL_MAX
    00070 #endif
    00071 #define PRESOLVE_INF COIN_DBL_MAX
    00072
    00073 class CoinPostsolveMatrix;
    00074
    00075 // Note 77
    00076 // "Members and bases are constructed in order of declaration
    00077 //  in the class and destroyed in the reverse order."  C++PL 3d Ed. p. 307
    00078 //
    00079 // That's why I put integer members (such as ncols) before the array members;
    00080 // I like to use those integer values during initialization.
    00081 // NOT ANYMORE
    00082
    00132 class CoinPresolveAction
    00133 {
    00134  public:
    00141   static void throwCoinError(const char *error, const char *ps_routine)
    00142   { throw CoinError(error, ps_routine, "CoinPresolve"); }
    00143
    00144
    00149   const CoinPresolveAction *next;
    00150
    00156   CoinPresolveAction(const CoinPresolveAction *next) : next(next) {}
    00158   inline void setNext(const CoinPresolveAction *nextAction)
    00159   { next = nextAction;}
    00160
    00165   virtual const char *name() const = 0;
    00166
    00170   virtual void postsolve(CoinPostsolveMatrix *prob) const = 0;
    00171
    00173   virtual ~CoinPresolveAction() {}
    00174 };
    00175
    00176 /*
    00177   These are needed for OSI-aware constructors associated with
    00178   CoinPrePostsolveMatrix, CoinPresolveMatrix, and CoinPostsolveMatrix.
    00179 */
    00180   class ClpSimplex;
    00181   class OsiSolverInterface;
    00182
    00183 /*
    00184   CoinWarmStartBasis is required for methods in CoinPrePostsolveMatrix
    00185   that accept/return a CoinWarmStartBasis object.
    00186 */
    00187   class CoinWarmStartBasis ;
    00188
    00239 class CoinPrePostsolveMatrix
    00240 {
    00241  public:
    00242
    00252   CoinPrePostsolveMatrix(int ncols_alloc, int nrows_alloc,
    00253                          CoinBigIndex nelems_alloc) ;
    00254
    00259   CoinPrePostsolveMatrix(const OsiSolverInterface * si,
    00260                         int ncols_,
    00261                         int nrows_,
    00262                         CoinBigIndex nelems_);
    00263
    00268   CoinPrePostsolveMatrix(const ClpSimplex * si,
    00269                         int ncols_,
    00270                         int nrows_,
    00271                         CoinBigIndex nelems_,
    00272                          double bulkRatio);
    00273
    00275   ~CoinPrePostsolveMatrix();
    00277
    00287   enum Status {
    00288     isFree = 0x00,
    00289     basic = 0x01,
    00290     atUpperBound = 0x02,
    00291     atLowerBound = 0x03,
    00292     superBasic = 0x04
    00293   };
    00294
    00301
    00303   inline void setRowStatus(int sequence, Status status)
    00304   {
    00305     unsigned char & st_byte = rowstat_[sequence];
    00306     st_byte = static_cast<unsigned char>(st_byte & (~7)) ;
    00307     st_byte = static_cast<unsigned char>(st_byte | status) ;
    00308   }
    00310   inline Status getRowStatus(int sequence) const
    00311   {return static_cast<Status> (rowstat_[sequence]&7);}
    00313   inline bool rowIsBasic(int sequence) const
    00314   {return (static_cast<Status> (rowstat_[sequence]&7)==basic);}
    00316   inline void setColumnStatus(int sequence, Status status)
    00317   {
    00318     unsigned char & st_byte = colstat_[sequence];
    00319     st_byte = static_cast<unsigned char>(st_byte & (~7)) ;
    00320     st_byte = static_cast<unsigned char>(st_byte | status) ;
    00321
    00322 #   ifdef PRESOLVE_DEBUG
    00323     switch (status)
    00324     { case isFree:
    00325       { if (clo_[sequence] > -PRESOLVE_INF || cup_[sequence] < PRESOLVE_INF)
    00326         { std::cout << "Bad status: Var " << sequence
    00327                     << " isFree, lb = " << clo_[sequence]
    00328                     << ", ub = " << cup_[sequence] << std::endl ; }
    00329         break ; }
    00330       case basic:
    00331       { break ; }
    00332       case atUpperBound:
    00333       { if (cup_[sequence] >= PRESOLVE_INF)
    00334         { std::cout << "Bad status: Var " << sequence
    00335                     << " atUpperBound, lb = " << clo_[sequence]
    00336                     << ", ub = " << cup_[sequence] << std::endl ; }
    00337         break ; }
    00338       case atLowerBound:
    00339       { if (clo_[sequence] <= -PRESOLVE_INF)
    00340         { std::cout << "Bad status: Var " << sequence
    00341                     << " atLowerBound, lb = " << clo_[sequence]
    00342                     << ", ub = " << cup_[sequence] << std::endl ; }
    00343         break ; }
    00344       case superBasic:
    00345       { if (clo_[sequence] <= -PRESOLVE_INF && cup_[sequence] >= PRESOLVE_INF)
    00346         { std::cout << "Bad status: Var " << sequence
    00347                     << " superBasic, lb = " << clo_[sequence]
    00348                     << ", ub = " << cup_[sequence] << std::endl ; }
    00349         break ; }
    00350       default:
    00351       { assert(false) ;
    00352         break ; } }
    00353 #   endif
    00354   }
    00356   inline Status getColumnStatus(int sequence) const
    00357   {return static_cast<Status> (colstat_[sequence]&7);}
    00359   inline bool columnIsBasic(int sequence) const
    00360   {return (static_cast<Status> (colstat_[sequence]&7)==basic);}
    00364   void setRowStatusUsingValue(int iRow);
    00368   void setColumnStatusUsingValue(int iColumn);
    00370   void setStructuralStatus(const char *strucStatus, int lenParam) ;
    00372   void setArtificialStatus(const char *artifStatus, int lenParam) ;
    00374   void setStatus(const CoinWarmStartBasis *basis) ;
    00376   CoinWarmStartBasis *getStatus() ;
    00380   const char *columnStatusString(int j) const ;
    00384   const char *rowStatusString(int i) const ;
    00386
    00394
    00395   void setObjOffset(double offset) ;
    00400   void setObjSense(double objSense) ;
    00402   void setPrimalTolerance(double primTol) ;
    00404   void setDualTolerance(double dualTol) ;
    00406   void setColLower(const double *colLower, int lenParam) ;
    00408   void setColUpper(const double *colUpper, int lenParam) ;
    00410   void setColSolution(const double *colSol, int lenParam) ;
    00412   void setCost(const double *cost, int lenParam) ;
    00414   void setReducedCost(const double *redCost, int lenParam) ;
    00416   void setRowLower(const double *rowLower, int lenParam) ;
    00418   void setRowUpper(const double *rowUpper, int lenParam) ;
    00420   void setRowPrice(const double *rowSol, int lenParam) ;
    00422   void setRowActivity(const double *rowAct, int lenParam) ;
    00424
    00427
    00428   inline int getNumCols()
    00429   { return (ncols_) ; }
    00431   inline int getNumRows()
    00432   { return (nrows_) ; }
    00434   inline int getNumElems()
    00435   { return (nelems_) ; }
    00437   inline const CoinBigIndex *getColStarts() const
    00438   { return (mcstrt_) ; }
    00440   inline const int *getColLengths() const
    00441   { return (hincol_) ; }
    00443   inline const int *getRowIndicesByCol() const
    00444   { return (hrow_) ; }
    00446   inline const double *getElementsByCol() const
    00447   { return (colels_) ; }
    00449   inline const double *getColLower() const
    00450   { return (clo_) ; }
    00452   inline const double *getColUpper() const
    00453   { return (cup_) ; }
    00455   inline const double *getCost() const
    00456   { return (cost_) ; }
    00458   inline const double *getRowLower() const
    00459   { return (rlo_) ; }
    00461   inline const double *getRowUpper() const
    00462   { return (rup_) ; }
    00464   inline const double *getColSolution() const
    00465   { return (sol_) ; }
    00467   inline const double *getRowActivity() const
    00468   { return (acts_) ; }
    00470   inline const double *getRowPrice() const
    00471   { return (rowduals_) ; }
    00473   inline const double *getReducedCost() const
    00474   { return (rcosts_) ; }
    00476   inline int countEmptyCols()
    00477   { int empty = 0 ;
    00478     for (int i = 0 ; i < ncols_ ; i++) if (hincol_[i] == 0) empty++ ;
    00479     return (empty) ; }
    00481
    00482
    00485
    00486   inline CoinMessageHandler *messageHandler() const
    00487   { return handler_; }
    00493   inline void setMessageHandler(CoinMessageHandler *handler)
    00494   { if (defaultHandler_ == true)
    00495     { delete handler_ ;
    00496       defaultHandler_ = false ; }
    00497     handler_ = handler ; }
    00499   inline CoinMessages messages() const
    00500   { return messages_; }
    00502
    00512
    00514   int ncols_;
    00516   int nrows_;
    00518   CoinBigIndex nelems_;
    00519
    00521   int ncols0_;
    00523   int nrows0_ ;
    00525   CoinBigIndex nelems0_ ;
    00534   CoinBigIndex bulk0_ ;
    00536   double bulkRatio_;
    00538
    00547
    00548   CoinBigIndex *mcstrt_;
    00550   int *hincol_;
    00552   int *hrow_;
    00554   double *colels_;
    00555
    00557   double *cost_;
    00559   double originalOffset_;
    00560
    00562   double *clo_;
    00564   double *cup_;
    00565
    00567   double *rlo_;
    00569   double *rup_;
    00570
    00572   int * originalColumn_;
    00574   int * originalRow_;
    00575
    00577   double ztolzb_;
    00579   double ztoldj_;
    00580
    00582   double maxmin_;
    00584
    00605   double *sol_;
    00611   double *rowduals_;
    00617   double *acts_;
    00623   double *rcosts_;
    00624
    00631   unsigned char *colstat_;
    00632
    00639   unsigned char *rowstat_;
    00641
    00650
    00651   CoinMessageHandler *handler_;
    00653   bool defaultHandler_;
    00655   CoinMessage messages_;
    00657
    00658 };
    00659
    00660
    00685 class presolvehlink
    00686 { public:
    00687   int pre, suc;
    00688 } ;
    00689
    00690 #define NO_LINK -66666666
    00691
    00697 inline void PRESOLVE_REMOVE_LINK(presolvehlink *link, int i)
    00698 {
    00699   int ipre = link[i].pre;
    00700   int isuc = link[i].suc;
    00701   if (ipre >= 0) {
    00702     link[ipre].suc = isuc;
    00703   }
    00704   if (isuc >= 0) {
    00705     link[isuc].pre = ipre;
    00706   }
    00707   link[i].pre = NO_LINK, link[i].suc = NO_LINK;
    00708 }
    00709
    00715 inline void PRESOLVE_INSERT_LINK(presolvehlink *link, int i, int j)
    00716 {
    00717   int isuc = link[j].suc;
    00718   link[j].suc = i;
    00719   link[i].pre = j;
    00720   if (isuc >= 0) {
    00721     link[isuc].pre = i;
    00722   }
    00723   link[i].suc = isuc;
    00724 }
    00725
    00737 inline void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j)
    00738 {
    00739   int ipre = link[i].pre;
    00740   int isuc = link[i].suc;
    00741   if (ipre >= 0) {
    00742     link[ipre].suc = j;
    00743   }
    00744   if (isuc >= 0) {
    00745     link[isuc].pre = j;
    00746   }
    00747   link[i].pre = NO_LINK, link[i].suc = NO_LINK;
    00748 }
    00749
    00750
    00772 class CoinPresolveMatrix : public CoinPrePostsolveMatrix
    00773 {
    00774  public:
    00775
    00782   CoinPresolveMatrix(int ncols_alloc, int nrows_alloc,
    00783                      CoinBigIndex nelems_alloc) ;
    00784
    00789   CoinPresolveMatrix(int ncols0,
    00790                     double maxmin,
    00791                     // end prepost members
    00792
    00793                     ClpSimplex * si,
    00794
    00795                     // rowrep
    00796                     int nrows,
    00797                     CoinBigIndex nelems,
    00798                  bool doStatus,
    00799                  double nonLinearVariable,
    00800                      double bulkRatio);
    00801
    00803   void update_model(ClpSimplex * si,
    00804                             int nrows0,
    00805                             int ncols0,
    00806                             CoinBigIndex nelems0);
    00811   CoinPresolveMatrix(int ncols0,
    00812                      double maxmin,
    00813                      // end prepost members
    00814                      OsiSolverInterface * si,
    00815                      // rowrep
    00816                      int nrows,
    00817                      CoinBigIndex nelems,
    00818                      bool doStatus,
    00819                      double nonLinearVariable,
    00820                      const char * prohibited,
    00821                      const char * rowProhibited=NULL);
    00822
    00824   void update_model(OsiSolverInterface * si,
    00825                             int nrows0,
    00826                             int ncols0,
    00827                             CoinBigIndex nelems0);
    00828
    00830   ~CoinPresolveMatrix();
    00831
    00837   friend void assignPresolveToPostsolve (CoinPresolveMatrix *&preObj) ;
    00838
    00847   void setMatrix(const CoinPackedMatrix *mtx) ;
    00848
    00850   inline int countEmptyRows()
    00851   { int empty = 0 ;
    00852     for (int i = 0 ; i < nrows_ ; i++) if (hinrow_[i] == 0) empty++ ;
    00853     return (empty) ; }
    00854
    00860   inline void setVariableType(int i, int variableType)
    00861   { if (integerType_ == 0) integerType_ = new unsigned char [ncols0_] ;
    00862     integerType_[i] = static_cast<unsigned char>(variableType) ; }
    00863
    00869   void setVariableType(const unsigned char *variableType, int lenParam) ;
    00870
    00876   void setVariableType (bool allIntegers, int lenParam) ;
    00877
    00879   inline void setAnyInteger (bool anyInteger = true)
    00880   { anyInteger_ = anyInteger ; }
    00882
    00886
    00888   inline const CoinBigIndex *getRowStarts() const
    00889   { return (mrstrt_) ; }
    00891   inline const int *getColIndicesByRow() const
    00892   { return (hcol_) ; }
    00894   inline const double *getElementsByRow() const
    00895   { return (rowels_) ; }
    00896
    00902   inline bool isInteger (int i) const
    00903   { if (integerType_ == 0)
    00904     { return (anyInteger_) ; }
    00905     else
    00906     if (integerType_[i] == 1)
    00907     { return (true) ; }
    00908     else
    00909     { return (false) ; } }
    00910
    00915   inline bool anyInteger () const
    00916   { return (anyInteger_) ; }
    00918   inline int presolveOptions() const
    00919   { return presolveOptions_;}
    00921   inline void setPresolveOptions(int value)
    00922   { presolveOptions_=value;}
    00924
    00932
    00933   presolvehlink *clink_;
    00935   presolvehlink *rlink_;
    00937
    00939   double dobias_;
    00940
    00942   inline void change_bias(double change_amount)
    00943   {
    00944     dobias_ += change_amount;
    00945   #if PRESOLVE_DEBUG
    00946     assert(fabs(change_amount)<1.0e50);
    00947   #endif
    00948     if (change_amount)
    00949       PRESOLVE_STMT(printf("changing bias by %g to %g\n",
    00950                       change_amount, dobias_));
    00951   }
    00952
    00961
    00962   CoinBigIndex *mrstrt_;
    00964   int *hinrow_;
    00966   double *rowels_;
    00968   int *hcol_;
    00970
    00972   unsigned char *integerType_;
    00978   bool anyInteger_ ;
    00980   bool tuning_;
    00982   void statistics();
    00984   double startTime_;
    00985
    00987   double feasibilityTolerance_;
    00989   inline double feasibilityTolerance()
    00990   { return (feasibilityTolerance_) ; }
    00992   inline void setFeasibilityTolerance (double val)
    00993   { feasibilityTolerance_ = val ; }
    00994
    01000   int status_;
    01002   inline int status()
    01003   { return (status_) ; }
    01005   inline void setStatus(int status)
    01006   { status_ = (status&0x3) ; }
    01007
    01013   int pass_;
    01015   inline void setPass (int pass = 0)
    01016   { pass_ = pass ; }
    01017
    01022   int maxSubstLevel_;
    01024   inline void setMaximumSubstitutionLevel (int level)
    01025   { maxSubstLevel_ = level ; }
    01026
    01027
    01050   unsigned char * colChanged_;
    01052   int * colsToDo_;
    01054   int numberColsToDo_;
    01056   int * nextColsToDo_;
    01058   int numberNextColsToDo_;
    01059
    01069   unsigned char * rowChanged_;
    01071   int * rowsToDo_;
    01073   int numberRowsToDo_;
    01075   int * nextRowsToDo_;
    01077   int numberNextRowsToDo_;
    01085   int presolveOptions_;
    01091   bool anyProhibited_;
    01093   int * usefulRowInt_;
    01095   double * usefulRowDouble_;
    01097   int * usefulColumnInt_;
    01099   double * usefulColumnDouble_;
    01101   double * randomNumber_;
    01103   int * infiniteUp_;
    01105   double * sumUp_;
    01107   int * infiniteDown_;
    01109   double * sumDown_;
    01111
    01114
    01120   void initColsToDo () ;
    01121
    01127   int stepColsToDo () ;
    01128
    01130   inline int numberColsToDo()
    01131   { return (numberColsToDo_) ; }
    01132
    01134   inline bool colChanged(int i) const {
    01135     return (colChanged_[i]&1)!=0;
    01136   }
    01138   inline void unsetColChanged(int i) {
    01139     colChanged_[i] = static_cast<unsigned char>(colChanged_[i] & (~1)) ;
    01140   }
    01142   inline void setColChanged(int i) {
    01143     colChanged_[i] = static_cast<unsigned char>(colChanged_[i] | (1)) ;
    01144   }
    01146   inline void addCol(int i) {
    01147     if ((colChanged_[i]&1)==0) {
    01148       colChanged_[i] = static_cast<unsigned char>(colChanged_[i] | (1)) ;
    01149       nextColsToDo_[numberNextColsToDo_++] = i;
    01150     }
    01151   }
    01153   inline bool colProhibited(int i) const {
    01154     return (colChanged_[i]&2)!=0;
    01155   }
    01162   inline bool colProhibited2(int i) const {
    01163     if (!anyProhibited_)
    01164       return false;
    01165     else
    01166       return (colChanged_[i]&2)!=0;
    01167   }
    01169   inline void setColProhibited(int i) {
    01170     colChanged_[i] = static_cast<unsigned char>(colChanged_[i] | (2)) ;
    01171   }
    01177   inline bool colUsed(int i) const {
    01178     return (colChanged_[i]&4)!=0;
    01179   }
    01181   inline void setColUsed(int i) {
    01182     colChanged_[i] = static_cast<unsigned char>(colChanged_[i] | (4)) ;
    01183   }
    01185   inline void unsetColUsed(int i) {
    01186     colChanged_[i] = static_cast<unsigned char>(colChanged_[i] & (~4)) ;
    01187   }
    01188
    01194   void initRowsToDo () ;
    01195
    01201   int stepRowsToDo () ;
    01202
    01204   inline int numberRowsToDo()
    01205   { return (numberRowsToDo_) ; }
    01206
    01208   inline bool rowChanged(int i) const {
    01209     return (rowChanged_[i]&1)!=0;
    01210   }
    01212   inline void unsetRowChanged(int i) {
    01213     rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] & (~1)) ;
    01214   }
    01216   inline void setRowChanged(int i) {
    01217     rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] | (1)) ;
    01218   }
    01220   inline void addRow(int i) {
    01221     if ((rowChanged_[i]&1)==0) {
    01222       rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] | (1)) ;
    01223       nextRowsToDo_[numberNextRowsToDo_++] = i;
    01224     }
    01225   }
    01227   inline bool rowProhibited(int i) const {
    01228     return (rowChanged_[i]&2)!=0;
    01229   }
    01236   inline bool rowProhibited2(int i) const {
    01237     if (!anyProhibited_)
    01238       return false;
    01239     else
    01240       return (rowChanged_[i]&2)!=0;
    01241   }
    01243   inline void setRowProhibited(int i) {
    01244     rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] | (2)) ;
    01245   }
    01251   inline bool rowUsed(int i) const {
    01252     return (rowChanged_[i]&4)!=0;
    01253   }
    01255   inline void setRowUsed(int i) {
    01256     rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] | (4)) ;
    01257   }
    01259   inline void unsetRowUsed(int i) {
    01260     rowChanged_[i] = static_cast<unsigned char>(rowChanged_[i] & (~4)) ;
    01261   }
    01262
    01263
    01265   inline bool anyProhibited() const
    01266   { return anyProhibited_;}
    01268   inline void setAnyProhibited(bool val = true)
    01269   { anyProhibited_ = val ; }
    01272   int recomputeSums(int iRow);
    01274   int initializeStuff();
    01276   void deleteStuff();
    01278
    01279 };
    01280
    01305 class CoinPostsolveMatrix : public CoinPrePostsolveMatrix
    01306 {
    01307  public:
    01308
    01315   CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc,
    01316                       CoinBigIndex nelems_alloc) ;
    01317
    01318
    01323   CoinPostsolveMatrix(ClpSimplex * si,
    01324
    01325                    int ncols0,
    01326                    int nrows0,
    01327                    CoinBigIndex nelems0,
    01328
    01329                    double maxmin_,
    01330                    // end prepost members
    01331
    01332                    double *sol,
    01333                    double *acts,
    01334
    01335                    unsigned char *colstat,
    01336                    unsigned char *rowstat);
    01337
    01342   CoinPostsolveMatrix(OsiSolverInterface * si,
    01343
    01344                    int ncols0,
    01345                    int nrows0,
    01346                    CoinBigIndex nelems0,
    01347
    01348                    double maxmin_,
    01349                    // end prepost members
    01350
    01351                    double *sol,
    01352                    double *acts,
    01353
    01354                    unsigned char *colstat,
    01355                    unsigned char *rowstat);
    01356
    01367   void assignPresolveToPostsolve (CoinPresolveMatrix *&preObj) ;
    01368
    01370   ~CoinPostsolveMatrix();
    01371
    01383
    01385   CoinBigIndex free_list_;
    01387   int maxlink_;
    01392   CoinBigIndex *link_;
    01393
    01395
    01403   char *cdone_;
    01404   char *rdone_;
    01406
    01408   void check_nbasic();
    01409
    01410 };
    01411
    01412
    01413 #define PRESOLVEFINITE(n)       (-PRESOLVE_INF < (n) && (n) < PRESOLVE_INF)
    01414
    01421
    01426 void presolve_make_memlists(CoinBigIndex *starts, int *lengths,
    01427                             presolvehlink *link, int n);
    01428
    01436 bool presolve_expand_major(CoinBigIndex *majstrts, double *majels,
    01437                            int *minndxs, int *majlens,
    01438                            presolvehlink *majlinks, int nmaj, int k) ;
    01439
    01445 inline bool presolve_expand_col(CoinBigIndex *mcstrt, double *colels,
    01446                                 int *hrow, int *hincol,
    01447                                 presolvehlink *clink, int ncols, int colx)
    01448 { return presolve_expand_major(mcstrt,colels,
    01449                                hrow,hincol,clink,ncols,colx) ; }
    01450
    01456 inline bool presolve_expand_row(CoinBigIndex *mrstrt, double *rowels,
    01457                                 int *hcol, int *hinrow,
    01458                                 presolvehlink *rlink, int nrows, int rowx)
    01459 { return presolve_expand_major(mrstrt,rowels,
    01460                                hcol,hinrow,rlink,nrows,rowx) ; }
    01461
    01462
    01471 inline CoinBigIndex presolve_find_minor(int tgt, CoinBigIndex ks, CoinBigIndex ke,
    01472                                  const int *minndxs)
    01473 { CoinBigIndex k ;
    01474   for (k = ks ; k < ke ; k++)
    01475 #ifndef NDEBUG
    01476   { if (minndxs[k] == tgt)
    01477       return (k) ; }
    01478   DIE("FIND_MINOR") ;
    01479
    01480   abort () ; return -1;
    01481 #else
    01482   { if (minndxs[k] == tgt)
    01483       break ; }
    01484   return (k) ;
    01485 #endif
    01486 }
    01487
    01494 inline CoinBigIndex presolve_find_row(int row, CoinBigIndex kcs,
    01495                                       CoinBigIndex kce, const int *hrow)
    01496 { return presolve_find_minor(row,kcs,kce,hrow) ; }
    01497
    01504 inline CoinBigIndex presolve_find_col(int col, CoinBigIndex krs,
    01505                                       CoinBigIndex kre, const int *hcol)
    01506 { return presolve_find_minor(col,krs,kre,hcol) ; }
    01507
    01508
    01517 CoinBigIndex presolve_find_minor1(int tgt, CoinBigIndex ks, CoinBigIndex ke,
    01518                                   const int *minndxs);
    01519
    01526 inline CoinBigIndex presolve_find_row1(int row, CoinBigIndex kcs,
    01527                                        CoinBigIndex kce, const int *hrow)
    01528 { return presolve_find_minor1(row,kcs,kce,hrow) ; }
    01529
    01536 inline CoinBigIndex presolve_find_col1(int col, CoinBigIndex krs,
    01537                                        CoinBigIndex kre, const int *hcol)
    01538 { return presolve_find_minor1(col,krs,kre,hcol) ; }
    01539
    01548 CoinBigIndex presolve_find_minor2(int tgt, CoinBigIndex ks, int majlen,
    01549                                   const int *minndxs,
    01550                                   const CoinBigIndex *majlinks) ;
    01551
    01559 inline CoinBigIndex presolve_find_row2(int row, CoinBigIndex kcs, int collen,
    01560                                        const int *hrow,
    01561                                        const CoinBigIndex *clinks)
    01562 { return presolve_find_minor2(row,kcs,collen,hrow,clinks) ; }
    01563
    01572 CoinBigIndex presolve_find_minor3(int tgt, CoinBigIndex ks, int majlen,
    01573                                   const int *minndxs,
    01574                                   const CoinBigIndex *majlinks) ;
    01575
    01583 inline CoinBigIndex presolve_find_row3(int row, CoinBigIndex kcs, int collen,
    01584                                        const int *hrow,
    01585                                        const CoinBigIndex *clinks)
    01586 { return presolve_find_minor3(row,kcs,collen,hrow,clinks) ; }
    01587
    01597 inline void presolve_delete_from_major(int majndx, int minndx,
    01598                                 const CoinBigIndex *majstrts,
    01599                                 int *majlens, int *minndxs, double *els)
    01600 { CoinBigIndex ks = majstrts[majndx] ;
    01601   CoinBigIndex ke = ks + majlens[majndx] ;
    01602
    01603   CoinBigIndex kmi = presolve_find_minor(minndx,ks,ke,minndxs) ;
    01604
    01605   minndxs[kmi] = minndxs[ke-1] ;
    01606   els[kmi] = els[ke-1] ;
    01607   majlens[majndx]-- ;
    01608
    01609   return ; }
    01610 // Delete all marked from major (and zero marked)
    01611 inline void presolve_delete_many_from_major(int majndx, char * marked,
    01612                                 const CoinBigIndex *majstrts,
    01613                                 int *majlens, int *minndxs, double *els)
    01614 {
    01615   CoinBigIndex ks = majstrts[majndx] ;
    01616   CoinBigIndex ke = ks + majlens[majndx] ;
    01617   CoinBigIndex put=ks;
    01618   for (CoinBigIndex k=ks;k<ke;k++) {
    01619     int iMinor = minndxs[k];
    01620     if (!marked[iMinor]) {
    01621       minndxs[put]=iMinor;
    01622       els[put++]=els[k];
    01623     } else {
    01624       marked[iMinor]=0;
    01625     }
    01626   }
    01627   majlens[majndx] = put-ks ;
    01628   return ;
    01629 }
    01630
    01641 inline void presolve_delete_from_col(int row, int col,
    01642                                      const CoinBigIndex *mcstrt,
    01643                                      int *hincol, int *hrow, double *colels)
    01644 { presolve_delete_from_major(col,row,mcstrt,hincol,hrow,colels) ; }
    01645
    01656 inline void presolve_delete_from_row(int row, int col,
    01657                                      const CoinBigIndex *mrstrt,
    01658                                      int *hinrow, int *hcol, double *rowels)
    01659 { presolve_delete_from_major(row,col,mrstrt,hinrow,hcol,rowels) ; }
    01660
    01671 void presolve_delete_from_major2 (int majndx, int minndx,
    01672                                   CoinBigIndex *majstrts, int *majlens,
    01673                                   int *minndxs, double *els, int *majlinks,
    01674                                    CoinBigIndex *free_listp) ;
    01675
    01686 inline void presolve_delete_from_col2(int row, int col, CoinBigIndex *mcstrt,
    01687                                       int *hincol, int *hrow,
    01688                                       double *colels, int *clinks,
    01689                                       CoinBigIndex *free_listp)
    01690 { presolve_delete_from_major2(col,row,mcstrt,hincol,hrow,colels,clinks,
    01691                               free_listp) ; }
    01692
    01694
    01700
    01712 double *presolve_dupmajor(const double *elems, const int *indices,
    01713                           int length, CoinBigIndex offset, int tgt = -1);
    01715 void coin_init_random_vec(double *work, int n);
    01717
    01718
    01719 #endif