/home/coin/SVN-release/CoinAll-1.1.0/CoinUtils/src/CoinPresolveMatrix.hpp

Go to the documentation of this file.

// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.
#ifndef CoinPresolveMatrix_H
#define CoinPresolveMatrix_H

#include "CoinPragma.hpp"
#include "CoinPackedMatrix.hpp"
#include "CoinMessage.hpp"
#include "CoinTime.hpp"

#include <cmath>
#include <cassert>
#include <cfloat>
#include <cassert>

#if defined(_MSC_VER)
// Avoid MS Compiler problem in recognizing type to delete
// by casting to type.
#define deleteAction(array,type) delete [] ((type) array)
#else
#define deleteAction(array,type) delete [] array
#endif

const double ZTOLDP      = 1e-12;
//#define PRESOLVE_DEBUG 1
// Debugging macros/functions

#if PRESOLVE_DEBUG || PRESOLVE_CONSISTENCY
#define PRESOLVE_STMT(s)        s
#define PRESOLVEASSERT(x) \
  ((x) ? 1 : \
        ((std::cerr << "FAILED ASSERTION at line " \
                    << __LINE__ << ":  " #x "\n"), abort(), 0))

inline void DIE(const char *s)  { std::cout<<s; abort(); }

// This code is used in [cr]done for columns and rows that are present in
// the presolved system.
#define PRESENT_IN_REDUCED      '\377'

#else

#define PRESOLVEASSERT(x) 
#define PRESOLVE_STMT(s)

inline void DIE(const char *s)  {}

#endif

inline int ALIGN(int n, int m)  { return (((n + m - 1) / m) * m); }
inline int ALIGN_DOUBLE(int n)  { return ALIGN(n,sizeof(double)); }

// Plus infinity
#ifndef COIN_DBL_MAX
#define COIN_DBL_MAX DBL_MAX
#endif
#define PRESOLVE_INF COIN_DBL_MAX

class CoinPostsolveMatrix;

// Note 77
// "Members and bases are constructed in order of declation
//  in the class and destroyed in the reverse order."  C++PL 3d Ed. p. 307
//
// That's why I put integer members (such as ncols) before the array members;
// I like to use those integer values during initialization.
// NOT ANYMORE

class CoinPresolveAction
{
 public:
  static void throwCoinError(const char *error, const char *ps_routine)
  { throw CoinError(error, ps_routine, "CoinPresolve"); } 


  const CoinPresolveAction *next;
  
  CoinPresolveAction(const CoinPresolveAction *next) : next(next) {}

  virtual const char *name() const = 0;

  virtual void postsolve(CoinPostsolveMatrix *prob) const = 0;

  virtual ~CoinPresolveAction() {}
};

/*
  These are needed for OSI-aware constructors associated with
  CoinPrePostsolveMatrix, CoinPresolveMatrix, and CoinPostsolveMatrix.
*/
  class ClpSimplex;
  class OsiSolverInterface;

/*
  CoinWarmStartBasis is required for methods in CoinPrePostsolveMatrix
  that accept/return a CoinWarmStartBasis object.
*/
  class CoinWarmStartBasis ;

class CoinPrePostsolveMatrix
{
 public:

  CoinPrePostsolveMatrix(int ncols_alloc, int nrows_alloc,
                         CoinBigIndex nelems_alloc) ;

  CoinPrePostsolveMatrix(const OsiSolverInterface * si,
                        int ncols_,
                        int nrows_,
                        CoinBigIndex nelems_);

  CoinPrePostsolveMatrix(const ClpSimplex * si,
                        int ncols_,
                        int nrows_,
                        CoinBigIndex nelems_,
                         double bulkRatio);

  ~CoinPrePostsolveMatrix();

  enum Status {
    isFree = 0x00,
    basic = 0x01,
    atUpperBound = 0x02,
    atLowerBound = 0x03,
    superBasic = 0x04
  };

  
  inline void setRowStatus(int sequence, Status status)
  {
    unsigned char & st_byte = rowstat_[sequence];
    st_byte &= ~7;
    st_byte |= status;
  }
  inline Status getRowStatus(int sequence) const
  {return static_cast<Status> (rowstat_[sequence]&7);}
  inline bool rowIsBasic(int sequence) const
  {return (static_cast<Status> (rowstat_[sequence]&7)==basic);}
  inline void setColumnStatus(int sequence, Status status)
  {
    unsigned char & st_byte = colstat_[sequence];
    st_byte &= ~7;
    st_byte |= status;

#   ifdef PRESOLVE_DEBUG
    switch (status)
    { case isFree:
      { if (clo_[sequence] > -PRESOLVE_INF || cup_[sequence] < PRESOLVE_INF)
        { std::cout << "Bad status: Var " << sequence
                    << " isFree, lb = " << clo_[sequence]
                    << ", ub = " << cup_[sequence] << std::endl ; }
        break ; }
      case basic:
      { break ; }
      case atUpperBound:
      { if (cup_[sequence] >= PRESOLVE_INF)
        { std::cout << "Bad status: Var " << sequence
                    << " atUpperBound, lb = " << clo_[sequence]
                    << ", ub = " << cup_[sequence] << std::endl ; }
        break ; }
      case atLowerBound:
      { if (clo_[sequence] <= -PRESOLVE_INF)
        { std::cout << "Bad status: Var " << sequence
                    << " atLowerBound, lb = " << clo_[sequence]
                    << ", ub = " << cup_[sequence] << std::endl ; }
        break ; }
      case superBasic:
      { if (clo_[sequence] <= -PRESOLVE_INF && cup_[sequence] >= PRESOLVE_INF)
        { std::cout << "Bad status: Var " << sequence
                    << " superBasic, lb = " << clo_[sequence]
                    << ", ub = " << cup_[sequence] << std::endl ; }
        break ; }
      default:
      { assert(false) ;
        break ; } }
#   endif
  }
  inline Status getColumnStatus(int sequence) const
  {return static_cast<Status> (colstat_[sequence]&7);}
  inline bool columnIsBasic(int sequence) const
  {return (static_cast<Status> (colstat_[sequence]&7)==basic);}
  void setRowStatusUsingValue(int iRow);
  void setColumnStatusUsingValue(int iColumn);
  void setStructuralStatus(const char *strucStatus, int lenParam) ;
  void setArtificialStatus(const char *artifStatus, int lenParam) ;
  void setStatus(const CoinWarmStartBasis *basis) ;
  CoinWarmStartBasis *getStatus() ;
  const char *columnStatusString(int j) const ;
  const char *rowStatusString(int i) const ;


  void setObjOffset(double offset) ;
  void setObjSense(double objSense) ;
  void setPrimalTolerance(double primTol) ;
  void setDualTolerance(double dualTol) ;
  void setColLower(const double *colLower, int lenParam) ;
  void setColUpper(const double *colUpper, int lenParam) ;
  void setColSolution(const double *colSol, int lenParam) ;
  void setCost(const double *cost, int lenParam) ;
  void setReducedCost(const double *redCost, int lenParam) ;
  void setRowLower(const double *rowLower, int lenParam) ;
  void setRowUpper(const double *rowUpper, int lenParam) ;
  void setRowPrice(const double *rowSol, int lenParam) ;
  void setRowActivity(const double *rowAct, int lenParam) ;


  inline int getNumCols()
  { return (ncols_) ; } 
  inline int getNumRows()
  { return (nrows_) ; } 
  inline int getNumElems()
  { return (nelems_) ; } 
  inline const CoinBigIndex *getColStarts() const
  { return (mcstrt_) ; } 
  inline const int *getColLengths() const
  { return (hincol_) ; } 
  inline const int *getRowIndicesByCol() const
  { return (hrow_) ; } 
  inline const double *getElementsByCol() const
  { return (colels_) ; } 
  inline const double *getColLower() const
  { return (clo_) ; } 
  inline const double *getColUpper() const
  { return (cup_) ; } 
  inline const double *getCost() const
  { return (cost_) ; } 
  inline const double *getRowLower() const
  { return (rlo_) ; } 
  inline const double *getRowUpper() const
  { return (rup_) ; } 
  inline const double *getColSolution() const
  { return (sol_) ; }
  inline const double *getRowActivity() const
  { return (acts_) ; }
  inline const double *getRowPrice() const
  { return (rowduals_) ; }
  inline const double *getReducedCost() const
  { return (rcosts_) ; }
  inline int countEmptyCols()
  { int empty = 0 ;
    for (int i = 0 ; i < ncols_ ; i++) if (hincol_[i] == 0) empty++ ;
    return (empty) ; }



  inline CoinMessageHandler *messageHandler() const 
  { return handler_; }
  inline void setMessageHandler(CoinMessageHandler *handler)
  { if (defaultHandler_ == true)
    { delete handler_ ;
      defaultHandler_ = false ; }
    handler_ = handler ; }
  inline CoinMessages messages() const 
  { return messages_; }


  int ncols_;
  int nrows_;
  CoinBigIndex nelems_;

  int ncols0_;
  int nrows0_ ;
  CoinBigIndex nelems0_ ;
  CoinBigIndex bulk0_ ;
  double bulkRatio_;


  CoinBigIndex *mcstrt_;
  int *hincol_;
  int *hrow_;
  double *colels_;

  double *cost_;
  double originalOffset_;

  double *clo_;
  double *cup_;

  double *rlo_;
  double *rup_;

  int * originalColumn_;
  int * originalRow_;

  double ztolzb_;
  double ztoldj_;

  double maxmin_;

  double *sol_;
  double *rowduals_;
  double *acts_;
  double *rcosts_;

  unsigned char *colstat_;

  unsigned char *rowstat_;


  CoinMessageHandler *handler_; 
  bool defaultHandler_;
  CoinMessage messages_; 

};


class presolvehlink
{ public:
  int pre, suc;
} ;

#define NO_LINK -66666666

inline void PRESOLVE_REMOVE_LINK(presolvehlink *link, int i)
{ 
  int ipre = link[i].pre;
  int isuc = link[i].suc;
  if (ipre >= 0) {
    link[ipre].suc = isuc;
  }
  if (isuc >= 0) {
    link[isuc].pre = ipre;
  }
  link[i].pre = NO_LINK, link[i].suc = NO_LINK;
}

inline void PRESOLVE_INSERT_LINK(presolvehlink *link, int i, int j)
{
  int isuc = link[j].suc;
  link[j].suc = i;
  link[i].pre = j;
  if (isuc >= 0) {
    link[isuc].pre = i;
  }
  link[i].suc = isuc;
}

inline void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j)
{ 
  int ipre = link[i].pre;
  int isuc = link[i].suc;
  if (ipre >= 0) {
    link[ipre].suc = j;
  }
  if (isuc >= 0) {
    link[isuc].pre = j;
  }
  link[i].pre = NO_LINK, link[i].suc = NO_LINK;
}


class CoinPresolveMatrix : public CoinPrePostsolveMatrix
{
 public:

  CoinPresolveMatrix(int ncols_alloc, int nrows_alloc,
                     CoinBigIndex nelems_alloc) ;

  CoinPresolveMatrix(int ncols0,
                    double maxmin,
                    // end prepost members

                    ClpSimplex * si,

                    // rowrep
                    int nrows,
                    CoinBigIndex nelems,
                 bool doStatus,
                 double nonLinearVariable,
                     double bulkRatio);

  void update_model(ClpSimplex * si,
                            int nrows0,
                            int ncols0,
                            CoinBigIndex nelems0);
  CoinPresolveMatrix(int ncols0,
                    double maxmin,
                    // end prepost members

                    OsiSolverInterface * si,

                    // rowrep
                    int nrows,
                    CoinBigIndex nelems,
                 bool doStatus,
                 double nonLinearVariable,
                     const char * prohibited);

  void update_model(OsiSolverInterface * si,
                            int nrows0,
                            int ncols0,
                            CoinBigIndex nelems0);

  ~CoinPresolveMatrix();

  friend void assignPresolveToPostsolve (CoinPresolveMatrix *&preObj) ;

  void setMatrix(const CoinPackedMatrix *mtx) ;

  inline int countEmptyRows()
  { int empty = 0 ;
    for (int i = 0 ; i < nrows_ ; i++) if (hinrow_[i] == 0) empty++ ;
    return (empty) ; }

  inline void setVariableType(int i, int variableType)
  { if (integerType_ == 0) integerType_ = new unsigned char [ncols0_] ;
    integerType_[i] = variableType ; }

  void setVariableType(const unsigned char *variableType, int lenParam) ;

  void setVariableType (bool allIntegers, int lenParam) ;

  inline void setAnyInteger (bool anyInteger = true)
  { anyInteger_ = anyInteger ; }


  inline const CoinBigIndex *getRowStarts() const
  { return (mrstrt_) ; }
  inline const int *getColIndicesByRow() const
  { return (hcol_) ; }
  inline const double *getElementsByRow() const
  { return (rowels_) ; }

  inline bool isInteger (int i) const
  { if (integerType_ == 0)
    { return (anyInteger_) ; }
    else
    if (integerType_[i] == 1)
    { return (true) ; }
    else
    { return (false) ; } }

  inline bool anyInteger () const
  { return (anyInteger_) ; }
  inline int presolveOptions() const
  { return presolveOptions_;}
  inline void setPresolveOptions(int value)
  { presolveOptions_=value;}


  presolvehlink *clink_;
  presolvehlink *rlink_;

  double dobias_;

  inline void change_bias(double change_amount)
  {
    dobias_ += change_amount;
  #if PRESOLVE_DEBUG
    assert(fabs(change_amount)<1.0e50);
  #endif
    if (change_amount)
      PRESOLVE_STMT(printf("changing bias by %g to %g\n",
                      change_amount, dobias_));  
  }


  CoinBigIndex *mrstrt_;
  int *hinrow_;
  double *rowels_;
  int *hcol_;

  unsigned char *integerType_;
  bool anyInteger_ ;
  bool tuning_;
  void statistics();
  double startTime_;

  double feasibilityTolerance_;
  inline double feasibilityTolerance()
  { return (feasibilityTolerance_) ; }
  inline void setFeasibilityTolerance (double val)
  { feasibilityTolerance_ = val ; }

  int status_;
  inline int status()
  { return (status_) ; }
  inline void setStatus(int status)
  { status_ = (status&0x3) ; }

  int pass_;
  inline void setPass (int pass = 0)
  { pass_ = pass ; }

  int maxSubstLevel_;
  inline void setMaximumSubstitutionLevel (int level)
  { maxSubstLevel_ = level ; }


  unsigned char * colChanged_;
  int * colsToDo_;
  int numberColsToDo_;
  int * nextColsToDo_;
  int numberNextColsToDo_;

  unsigned char * rowChanged_;
  int * rowsToDo_;
  int numberRowsToDo_;
  int * nextRowsToDo_;
  int numberNextRowsToDo_;
  int presolveOptions_;
  bool anyProhibited_;


  void initColsToDo () ;

  int stepColsToDo () ;

  inline int numberColsToDo()
  { return (numberColsToDo_) ; }

  inline bool colChanged(int i) const {
    return (colChanged_[i]&1)!=0;
  }
  inline void unsetColChanged(int i) {
    colChanged_[i]  &= ~1;;
  }
  inline void setColChanged(int i) {
    colChanged_[i] |= 1;
  }
  inline void addCol(int i) {
    if ((colChanged_[i]&1)==0) {
      colChanged_[i] |= 1;
      nextColsToDo_[numberNextColsToDo_++] = i;
    }
  }
  inline bool colProhibited(int i) const {
    return (colChanged_[i]&2)!=0;
  }
  inline bool colProhibited2(int i) const {
    if (!anyProhibited_)
      return false;
    else
      return (colChanged_[i]&2)!=0;
  }
  inline void setColProhibited(int i) {
    colChanged_[i] |= 2;
  }
  inline bool colUsed(int i) const {
    return (colChanged_[i]&4)!=0;
  }
  inline void setColUsed(int i) {
    colChanged_[i] |= 4;
  }
  inline void unsetColUsed(int i) {
    colChanged_[i]  &= ~4;;
  }

  void initRowsToDo () ;

  int stepRowsToDo () ;

  inline int numberRowsToDo()
  { return (numberRowsToDo_) ; }

  inline bool rowChanged(int i) const {
    return (rowChanged_[i]&1)!=0;
  }
  inline void unsetRowChanged(int i) {
    rowChanged_[i]  &= ~1;;
  }
  inline void setRowChanged(int i) {
    rowChanged_[i] |= 1;
  }
  inline void addRow(int i) {
    if ((rowChanged_[i]&1)==0) {
      rowChanged_[i] |= 1;
      nextRowsToDo_[numberNextRowsToDo_++] = i;
    }
  }
  inline bool rowProhibited(int i) const {
    return (rowChanged_[i]&2)!=0;
  }
  inline bool rowProhibited2(int i) const {
    if (!anyProhibited_)
      return false;
    else
      return (rowChanged_[i]&2)!=0;
  }
  inline void setRowProhibited(int i) {
    rowChanged_[i] |= 2;
  }
  inline bool rowUsed(int i) const {
    return (rowChanged_[i]&4)!=0;
  }
  inline void setRowUsed(int i) {
    rowChanged_[i] |= 4;
  }
  inline void unsetRowUsed(int i) {
    rowChanged_[i]  &= ~4;;
  }


  inline bool anyProhibited() const
  { return anyProhibited_;}
  inline void setAnyProhibited(bool val = true)
  { anyProhibited_ = val ; }

};

class CoinPostsolveMatrix : public CoinPrePostsolveMatrix
{
 public:

  CoinPostsolveMatrix(int ncols_alloc, int nrows_alloc,
                      CoinBigIndex nelems_alloc) ;


  CoinPostsolveMatrix(ClpSimplex * si,

                   int ncols0,
                   int nrows0,
                   CoinBigIndex nelems0,
                     
                   double maxmin_,
                   // end prepost members

                   double *sol,
                   double *acts,

                   unsigned char *colstat,
                   unsigned char *rowstat);

  CoinPostsolveMatrix(OsiSolverInterface * si,

                   int ncols0,
                   int nrows0,
                   CoinBigIndex nelems0,
                     
                   double maxmin_,
                   // end prepost members

                   double *sol,
                   double *acts,

                   unsigned char *colstat,
                   unsigned char *rowstat);

  void assignPresolveToPostsolve (CoinPresolveMatrix *&preObj) ;

  ~CoinPostsolveMatrix();


  CoinBigIndex free_list_;
  int maxlink_;
  CoinBigIndex *link_;


  char *cdone_;
  char *rdone_;

  void check_nbasic();

};


#define PRESOLVEFINITE(n)       (-PRESOLVE_INF < (n) && (n) < PRESOLVE_INF)


void presolve_make_memlists(CoinBigIndex *starts, int *lengths,
                            presolvehlink *link, int n);

bool presolve_expand_major(CoinBigIndex *majstrts, double *majels,
                           int *minndxs, int *majlens,
                           presolvehlink *majlinks, int nmaj, int k) ;

inline bool presolve_expand_col(CoinBigIndex *mcstrt, double *colels,
                                int *hrow, int *hincol,
                                presolvehlink *clink, int ncols, int colx)
{ return presolve_expand_major(mcstrt,colels,
                               hrow,hincol,clink,ncols,colx) ; }

inline bool presolve_expand_row(CoinBigIndex *mrstrt, double *rowels,
                                int *hcol, int *hinrow,
                                presolvehlink *rlink, int nrows, int rowx)
{ return presolve_expand_major(mrstrt,rowels,
                               hcol,hinrow,rlink,nrows,rowx) ; }


CoinBigIndex presolve_find_minor(int tgt, CoinBigIndex ks, CoinBigIndex ke,
                                 const int *minndxs);

inline CoinBigIndex presolve_find_row(int row, CoinBigIndex kcs,
                                      CoinBigIndex kce, const int *hrow)
{ return presolve_find_minor(row,kcs,kce,hrow) ; }

inline CoinBigIndex presolve_find_col(int col, CoinBigIndex krs,
                                      CoinBigIndex kre, const int *hcol)
{ return presolve_find_minor(col,krs,kre,hcol) ; }


CoinBigIndex presolve_find_minor1(int tgt, CoinBigIndex ks, CoinBigIndex ke,
                                  const int *minndxs);

inline CoinBigIndex presolve_find_row1(int row, CoinBigIndex kcs,
                                       CoinBigIndex kce, const int *hrow)
{ return presolve_find_minor1(row,kcs,kce,hrow) ; } 

inline CoinBigIndex presolve_find_col1(int col, CoinBigIndex krs,
                                       CoinBigIndex kre, const int *hcol)
{ return presolve_find_minor1(col,krs,kre,hcol) ; } 

CoinBigIndex presolve_find_minor2(int tgt, CoinBigIndex ks, int majlen,
                                  const int *minndxs,
                                  const CoinBigIndex *majlinks) ;

inline CoinBigIndex presolve_find_row2(int row, CoinBigIndex kcs, int collen,
                                       const int *hrow,
                                       const CoinBigIndex *clinks)
{ return presolve_find_minor2(row,kcs,collen,hrow,clinks) ; }

CoinBigIndex presolve_find_minor3(int tgt, CoinBigIndex ks, int majlen,
                                  const int *minndxs,
                                  const CoinBigIndex *majlinks) ;

inline CoinBigIndex presolve_find_row3(int row, CoinBigIndex kcs, int collen,
                                       const int *hrow,
                                       const CoinBigIndex *clinks)
{ return presolve_find_minor3(row,kcs,collen,hrow,clinks) ; }

void presolve_delete_from_major(int majndx, int minndx,
                                const CoinBigIndex *majstrts,
                                int *majlens, int *minndxs, double *els) ;
// Delete all marked from major (and zero marked)
void presolve_delete_many_from_major(int majndx, char * marked,
                                const CoinBigIndex *majstrts,
                                int *majlens, int *minndxs, double *els) ;

inline void presolve_delete_from_col(int row, int col,
                                     const CoinBigIndex *mcstrt,
                                     int *hincol, int *hrow, double *colels)
{ presolve_delete_from_major(col,row,mcstrt,hincol,hrow,colels) ; }

inline void presolve_delete_from_row(int row, int col,
                                     const CoinBigIndex *mrstrt,
                                     int *hinrow, int *hcol, double *rowels)
{ presolve_delete_from_major(row,col,mrstrt,hinrow,hcol,rowels) ; }

void presolve_delete_from_major2 (int majndx, int minndx,
                                  CoinBigIndex *majstrts, int *majlens,
                                  int *minndxs, double *els, int *majlinks,
                                   CoinBigIndex *free_listp) ;

inline void presolve_delete_from_col2(int row, int col, CoinBigIndex *mcstrt,
                                      int *hincol, int *hrow,
                                      double *colels, int *clinks,
                                      CoinBigIndex *free_listp)
{ presolve_delete_from_major2(col,row,mcstrt,hincol,hrow,colels,clinks,
                              free_listp) ; }



double *presolve_dupmajor(const double *elems, const int *indices,
                          int length, CoinBigIndex offset, int tgt = -1);



#endif

---