CoinSimpFactorization.hpp

Go to the documentation of this file.

/* $Id: CoinSimpFactorization.hpp 2083 2019-01-06 19:38:09Z unxusr $ */
// 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,
    int maximumL,
    int 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

/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
*/