CoinSimpFactorization.hpp

Go to the documentation of this file.

/* $Id: CoinSimpFactorization.hpp 1416 2011-04-17 09:57:29Z stefan $ */
// Copyright (C) 2008, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).

/* 
   This is a simple factorization of the LP Basis
 */
#ifndef CoinSimpFactorization_H
#define CoinSimpFactorization_H

#include <iostream>
#include <string>
#include <cassert>
#include "CoinTypes.hpp"
#include "CoinIndexedVector.hpp"
#include "CoinDenseFactorization.hpp"
class CoinPackedMatrix;


class FactorPointers{
public:
    double *rowMax;
    int *firstRowKnonzeros;
    int *prevRow;
    int *nextRow;
    int *firstColKnonzeros;
    int *prevColumn;
    int *nextColumn;
    int *newCols;
    //constructor
    FactorPointers( int numRows, int numCols, int *UrowLengths_, int *UcolLengths_ );
    // destructor
    ~ FactorPointers();
};

class CoinSimpFactorization : public CoinOtherFactorization {
   friend void CoinSimpFactorizationUnitTest( const std::string & mpsDir );

public:

  CoinSimpFactorization (  );
  CoinSimpFactorization ( const CoinSimpFactorization &other);
  
  virtual ~CoinSimpFactorization (  );
  CoinSimpFactorization & operator = ( const CoinSimpFactorization & other );
  virtual CoinOtherFactorization * clone() const ;

  virtual void getAreas ( int numberRows,
                  int numberColumns,
                  CoinBigIndex maximumL,
                  CoinBigIndex maximumU );
  
  virtual void preProcess ( );
  virtual int factor ( );
  virtual void postProcess(const int * sequence, int * pivotVariable);
  virtual void makeNonSingular(int * sequence, int numberColumns);

  virtual inline int numberElements (  ) const {
    return numberRows_*(numberColumns_+numberPivots_);
  }
  double maximumCoefficient() const;


  virtual int replaceColumn ( CoinIndexedVector * regionSparse,
                      int pivotRow,
                      double pivotCheck ,
                              bool checkBeforeModifying=false,
                              double acceptablePivot=1.0e-8);

    virtual int updateColumnFT ( CoinIndexedVector * regionSparse,
                         CoinIndexedVector * regionSparse2,
                         bool noPermute=false);
    
    virtual int updateColumn ( CoinIndexedVector * regionSparse,
                       CoinIndexedVector * regionSparse2,
                       bool noPermute=false) const;
    virtual int updateTwoColumnsFT(CoinIndexedVector * regionSparse1,
                           CoinIndexedVector * regionSparse2,
                           CoinIndexedVector * regionSparse3,
                           bool noPermute=false);
    int upColumn ( CoinIndexedVector * regionSparse,
                   CoinIndexedVector * regionSparse2,
                   bool noPermute=false, bool save=false) const;
    virtual int updateColumnTranspose ( CoinIndexedVector * regionSparse,
                                CoinIndexedVector * regionSparse2) const;
    int upColumnTranspose ( CoinIndexedVector * regionSparse,
                                CoinIndexedVector * regionSparse2) const;

  inline void clearArrays()
  { gutsOfDestructor();}
  inline int * indices() const
  { return reinterpret_cast<int *> (elements_+numberRows_*numberRows_);}
  virtual inline int * permute() const
  { return pivotRow_;}

  void gutsOfDestructor();
  void gutsOfInitialize();
  void gutsOfCopy(const CoinSimpFactorization &other);

    
  void factorize(int numberOfRows,
                 int numberOfColumns,
                 const int colStarts[],
                 const int indicesRow[],
                 const double elements[]);
    int mainLoopFactor (FactorPointers &pointers );
    void copyLbyRows();
    void copyUbyColumns();
    int findPivot(FactorPointers &pointers, int &r, int &s, bool &ifSlack);
    int findPivotShCol(FactorPointers &pointers, int &r, int &s);
    int findPivotSimp(FactorPointers &pointers, int &r, int &s);
    void GaussEliminate(FactorPointers &pointers, int &r, int &s);
    int findShortRow(const int column, const int length, int &minRow, 
                     int &minRowLength, FactorPointers &pointers);
    int findShortColumn(const int row, const int length, int &minCol, 
                        int &minColLength, FactorPointers &pointers);
    double findMaxInRrow(const int row, FactorPointers &pointers);
    void pivoting(const int pivotRow, const int pivotColumn,
                  const double invPivot, FactorPointers &pointers);
    void updateCurrentRow(const int pivotRow, const int row, 
                          const double multiplier, FactorPointers &pointers,
                          int &newNonZeros);
    void increaseLsize();
    void increaseRowSize(const int row, const int newSize);
    void increaseColSize(const int column, const int newSize, const bool b);
    void enlargeUrow(const int numNewElements);
    void enlargeUcol(const int numNewElements, const bool b);
    int findInRow(const int row, const int column);
    int findInColumn(const int column, const int row);
    void removeRowFromActSet(const int row, FactorPointers &pointers);
    void removeColumnFromActSet(const int column, FactorPointers &pointers);
    void allocateSpaceForU();
    void allocateSomeArrays();
    void initialSomeNumbers();
    void Lxeqb(double *b) const;
    void Lxeqb2(double *b1, double *b2) const;
    void Uxeqb(double *b, double *sol) const;
    void Uxeqb2(double *b1, double *sol1, double *sol2, double *b2) const;
    void xLeqb(double *b) const;
    void xUeqb(double *b, double *sol) const;
    int LUupdate(int newBasicCol);
    void newEta(int row, int numNewElements);
    void copyRowPermutations();
    void Hxeqb(double *b) const;
    void Hxeqb2(double *b1, double *b2) const;
    void xHeqb(double *b) const;
    void ftran(double *b, double *sol, bool save) const;
    void ftran2(double *b1, double *sol1, double *b2, double *sol2) const;
    void btran(double *b, double *sol) const;



protected:
  int checkPivot(double saveFromU, double oldPivot) const;
protected:

    double *denseVector_;
    double *workArea2_; 
    double *workArea3_;
    int *vecLabels_;
    int *indVector_;

    double *auxVector_;
    int *auxInd_;

    double *vecKeep_;
    int *indKeep_;
    mutable int keepSize_;

    

    int *LrowStarts_;
    int *LrowLengths_;
    double *Lrows_;
    int *LrowInd_;
    int LrowSize_; 
    int LrowCap_;

    int *LcolStarts_;
    int *LcolLengths_;
    double *Lcolumns_;
    int *LcolInd_;
    int LcolSize_;
    int LcolCap_;
   

    int *UrowStarts_;
    int *UrowLengths_;
#ifdef COIN_SIMP_CAPACITY
    int *UrowCapacities_;
#endif
    double *Urows_;
    int *UrowInd_;
    int UrowMaxCap_;
    int UrowEnd_;
    int firstRowInU_;
    int lastRowInU_;
    int *prevRowInU_;
    int *nextRowInU_;

    int *UcolStarts_;
    int *UcolLengths_;
#ifdef COIN_SIMP_CAPACITY
    int *UcolCapacities_;
#endif
    double *Ucolumns_;
    int *UcolInd_;
    int *prevColInU_;
    int *nextColInU_;
    int firstColInU_;
    int lastColInU_;
    int UcolMaxCap_;
    int UcolEnd_;    
    int *colSlack_;
 
    double *invOfPivots_;

    int *colOfU_;
    int *colPosition_;
    int *rowOfU_;
    int *rowPosition_;
    int *secRowOfU_;
    int *secRowPosition_;
    
    int *EtaPosition_;
    int *EtaStarts_;
    int *EtaLengths_;
    int *EtaInd_;
    double *Eta_;
    int EtaSize_;
    int lastEtaRow_;
    int maxEtaRows_;
    int EtaMaxCap_;
    
    int minIncrease_;
    double updateTol_;
    bool doSuhlHeuristic_;
    double maxU_;
    double maxGrowth_;
    double maxA_;
    int pivotCandLimit_;    
    int numberSlacks_;    
    int firstNumberSlacks_;
};
#endif