/home/coin/SVN-release/CoinAll-1.1.0/Clp/src/ClpSimplex.hpp

Go to the documentation of this file.

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

/* 
   Authors
 
   John Forrest

 */
#ifndef ClpSimplex_H
#define ClpSimplex_H

#include <iostream>
#include <cfloat>
#include "ClpModel.hpp"
#include "ClpMatrixBase.hpp"
#include "ClpSolve.hpp"
class ClpDualRowPivot;
class ClpPrimalColumnPivot;
class ClpFactorization;
class CoinIndexedVector;
class ClpNonLinearCost;
class CoinModel;
class OsiClpSolverInterface;
class CoinWarmStartBasis;
class ClpDisasterHandler;
class ClpConstraint;

class ClpSimplex : public ClpModel {
  friend void ClpSimplexUnitTest(const std::string & mpsDir);

public:
  enum Status {
    isFree = 0x00,
    basic = 0x01,
    atUpperBound = 0x02,
    atLowerBound = 0x03,
    superBasic = 0x04,
    isFixed = 0x05
  };
  // For Dual
  enum FakeBound {
    noFake = 0x00,
    bothFake = 0x01,
    upperFake = 0x02,
    lowerFake = 0x03
  };


    ClpSimplex (bool emptyMessages = false  );

  ClpSimplex(const ClpSimplex & rhs, int scalingMode =-1);
  ClpSimplex(const ClpModel & rhs, int scalingMode=-1);
  ClpSimplex (const ClpModel * wholeModel,
              int numberRows, const int * whichRows,
              int numberColumns, const int * whichColumns,
              bool dropNames=true, bool dropIntegers=true,
              bool fixOthers=false);
  ClpSimplex (const ClpSimplex * wholeModel,
              int numberRows, const int * whichRows,
              int numberColumns, const int * whichColumns,
              bool dropNames=true, bool dropIntegers=true,
              bool fixOthers=false);
  ClpSimplex (ClpSimplex * wholeModel,
              int numberColumns, const int * whichColumns);
  void originalModel(ClpSimplex * miniModel);
  void setPersistenceFlag(int value);
  void auxiliaryModel(int options);
  void deleteAuxiliaryModel();
  inline bool usingAuxiliaryModel() const
  { return auxiliaryModel_!=NULL;}
  void makeBaseModel();
  void deleteBaseModel();
  inline ClpSimplex *  baseModel() const
  { return baseModel_;}
  void setToBaseModel(ClpSimplex * model=NULL);
    ClpSimplex & operator=(const ClpSimplex & rhs);
   ~ClpSimplex (  );
  // Ones below are just ClpModel with some changes
  void loadProblem (  const ClpMatrixBase& matrix,
                     const double* collb, const double* colub,   
                     const double* obj,
                     const double* rowlb, const double* rowub,
                      const double * rowObjective=NULL);
  void loadProblem (  const CoinPackedMatrix& matrix,
                     const double* collb, const double* colub,   
                     const double* obj,
                     const double* rowlb, const double* rowub,
                      const double * rowObjective=NULL);

  void loadProblem (  const int numcols, const int numrows,
                     const CoinBigIndex* start, const int* index,
                     const double* value,
                     const double* collb, const double* colub,   
                     const double* obj,
                      const double* rowlb, const double* rowub,
                      const double * rowObjective=NULL);
  void loadProblem (  const int numcols, const int numrows,
                     const CoinBigIndex* start, const int* index,
                      const double* value,const int * length,
                     const double* collb, const double* colub,   
                     const double* obj,
                      const double* rowlb, const double* rowub,
                      const double * rowObjective=NULL);
  int loadProblem (  CoinModel & modelObject,bool keepSolution=false);
  int readMps(const char *filename,
              bool keepNames=false,
              bool ignoreErrors = false);
  int readGMPL(const char *filename,const char * dataName,
               bool keepNames=false);
  int readLp(const char *filename, const double epsilon = 1e-5);
  void borrowModel(ClpModel & otherModel);
  void borrowModel(ClpSimplex & otherModel);
   void passInEventHandler(const ClpEventHandler * eventHandler);
  void getbackSolution(const ClpSimplex & smallModel,const int * whichRow, const int * whichColumn);
  int loadNonLinear(void * info, int & numberConstraints, 
                    ClpConstraint ** & constraints);

  int initialSolve(ClpSolve & options);
  int initialSolve();
  int initialDualSolve();
  int initialPrimalSolve();
  int initialBarrierSolve();
  int initialBarrierNoCrossSolve();
  int dual(int ifValuesPass=0, int startFinishOptions=0);
  // If using Debug
  int dualDebug(int ifValuesPass=0, int startFinishOptions=0);
  int primal(int ifValuesPass=0, int startFinishOptions=0);
  int nonlinearSLP(int numberPasses,double deltaTolerance);
  int nonlinearSLP(int numberConstraints, ClpConstraint ** constraints,
                   int numberPasses,double deltaTolerance);
  int barrier(bool crossover=true);
  int reducedGradient(int phase=0);
  int cleanup(int cleanupScaling);
  int dualRanging(int numberCheck,const int * which,
                  double * costIncrease, int * sequenceIncrease,
                  double * costDecrease, int * sequenceDecrease,
                  double * valueIncrease=NULL, double * valueDecrease=NULL);
  int primalRanging(int numberCheck,const int * which,
                  double * valueIncrease, int * sequenceIncrease,
                  double * valueDecrease, int * sequenceDecrease);
  int writeBasis(const char *filename,
                 bool writeValues=false,
                 int formatType=0) const;
  int readBasis(const char *filename);
  CoinWarmStartBasis * getBasis() const;
  void setFactorization( ClpFactorization & factorization);
  int tightenPrimalBounds(double factor=0.0,int doTight=0,bool tightIntegers=false);
  int crash(double gap,int pivot);
  void setDualRowPivotAlgorithm(ClpDualRowPivot & choice);
  void setPrimalColumnPivotAlgorithm(ClpPrimalColumnPivot & choice);
  int strongBranching(int numberVariables,const int * variables,
                      double * newLower, double * newUpper,
                      double ** outputSolution,
                      int * outputStatus, int * outputIterations,
                      bool stopOnFirstInfeasible=true,
                      bool alwaysFinish=false,
                      int startFinishOptions=0);

  int pivot();

  int primalPivotResult();
  
  int dualPivotResult();

  int startup(int ifValuesPass,int startFinishOptions=0);
  void finish(int startFinishOptions=0);
  
  bool statusOfProblem(bool initial=false);
  void defaultFactorizationFrequency();


  inline bool primalFeasible() const
         { return (numberPrimalInfeasibilities_==0);}
  inline bool dualFeasible() const
         { return (numberDualInfeasibilities_==0);}
  inline ClpFactorization * factorization() const 
          { return factorization_;}
  bool sparseFactorization() const;
  void setSparseFactorization(bool value);
  int factorizationFrequency() const;
  void setFactorizationFrequency(int value);
  inline double dualBound() const
          { return dualBound_;}
  void setDualBound(double value);
  inline double infeasibilityCost() const
          { return infeasibilityCost_;}
  void setInfeasibilityCost(double value);
  inline int perturbation() const
    { return perturbation_;}
  void setPerturbation(int value);
  inline int algorithm() const 
  {return algorithm_; } 
  inline void setAlgorithm(int value)
  {algorithm_=value; } 
  inline double sumDualInfeasibilities() const 
          { return sumDualInfeasibilities_;} 
  inline void setSumDualInfeasibilities(double value)
          { sumDualInfeasibilities_=value;} 
  inline double sumOfRelaxedDualInfeasibilities() const 
          { return sumOfRelaxedDualInfeasibilities_;} 
  inline void setSumOfRelaxedDualInfeasibilities(double value)
          { sumOfRelaxedDualInfeasibilities_=value;} 
  inline int numberDualInfeasibilities() const 
          { return numberDualInfeasibilities_;} 
  inline void setNumberDualInfeasibilities(int value)
          { numberDualInfeasibilities_=value;} 
  inline int numberDualInfeasibilitiesWithoutFree() const 
          { return numberDualInfeasibilitiesWithoutFree_;} 
  inline double sumPrimalInfeasibilities() const 
          { return sumPrimalInfeasibilities_;} 
  inline void setSumPrimalInfeasibilities(double value)
          { sumPrimalInfeasibilities_=value;} 
  inline double sumOfRelaxedPrimalInfeasibilities() const 
          { return sumOfRelaxedPrimalInfeasibilities_;} 
  inline void setSumOfRelaxedPrimalInfeasibilities(double value)
          { sumOfRelaxedPrimalInfeasibilities_=value;} 
  inline int numberPrimalInfeasibilities() const 
          { return numberPrimalInfeasibilities_;} 
  inline void setNumberPrimalInfeasibilities(int value)
          { numberPrimalInfeasibilities_=value;} 
  int saveModel(const char * fileName);
  int restoreModel(const char * fileName);
  
  void checkSolution(int setToBounds=false);
  void checkSolutionInternal();
  inline CoinIndexedVector * rowArray(int index) const
  { return rowArray_[index];}
  inline CoinIndexedVector * columnArray(int index) const
  { return columnArray_[index];}

  /******************** End of most useful part **************/
  int getSolution (  const double * rowActivities,
                     const double * columnActivities);
  int getSolution ();
  int createPiecewiseLinearCosts(const int * starts,
                   const double * lower, const double * gradient);
  ClpDualRowPivot * dualRowPivot() const
  { return dualRowPivot_;}
  void returnModel(ClpSimplex & otherModel);
  int internalFactorize(int solveType);
  ClpDataSave saveData() ;
  void restoreData(ClpDataSave saved);
  void cleanStatus();
  int factorize();
  void computeDuals(double * givenDjs);
  void computePrimals (  const double * rowActivities,
                     const double * columnActivities);
  void add(double * array,
                   int column, double multiplier) const;
  void unpack(CoinIndexedVector * rowArray) const ;
  void unpack(CoinIndexedVector * rowArray,int sequence) const;
  void unpackPacked(CoinIndexedVector * rowArray) ;
  void unpackPacked(CoinIndexedVector * rowArray,int sequence);
protected:  
  int housekeeping(double objectiveChange);
  void checkPrimalSolution(const double * rowActivities=NULL,
                           const double * columnActivies=NULL);
  void checkDualSolution();
  void checkBothSolutions();
public:
  void setValuesPassAction(double incomingInfeasibility,
                           double allowedInfeasibility);

public: 
  inline double alphaAccuracy() const
          { return alphaAccuracy_;} 
  inline void setAlphaAccuracy(double value)
          { alphaAccuracy_ = value;} 
public:
  inline void setDisasterHandler(ClpDisasterHandler * handler)
  { disasterArea_= handler;}
  inline double largeValue() const 
          { return largeValue_;} 
  void setLargeValue( double value) ;
  inline double largestPrimalError() const
          { return largestPrimalError_;} 
  inline double largestDualError() const
          { return largestDualError_;} 
  inline void setLargestPrimalError(double value)
          { largestPrimalError_=value;} 
  inline void setLargestDualError(double value)
          { largestDualError_=value;} 
  inline int * pivotVariable() const
          { return pivotVariable_;}
  inline bool automaticScaling() const
  { return automaticScale_!=0;}
  inline void setAutomaticScaling(bool onOff)
  { automaticScale_ = onOff ? 1: 0;} 
  inline double currentDualTolerance() const 
          { return dualTolerance_;} 
  inline void setCurrentDualTolerance(double value)
          { dualTolerance_ = value;} 
  inline double currentPrimalTolerance() const 
          { return primalTolerance_;} 
  inline void setCurrentPrimalTolerance(double value)
          { primalTolerance_ = value;} 
  inline int numberRefinements() const 
          { return numberRefinements_;} 
  void setNumberRefinements( int value) ;
  inline double alpha() const { return alpha_;}
  inline void setAlpha(double value) { alpha_ = value;}
  inline double dualIn() const { return dualIn_;}
  inline int pivotRow() const{ return pivotRow_;}
  inline void setPivotRow(int value) { pivotRow_=value;}
  double valueIncomingDual() const;

  protected:
  int gutsOfSolution ( double * givenDuals,
                       const double * givenPrimals,
                       bool valuesPass=false);
  void gutsOfDelete(int type);
  void gutsOfCopy(const ClpSimplex & rhs);
  bool createRim(int what,bool makeRowCopy=false,int startFinishOptions=0);
  void createRim1(bool initial);
  void createRim4(bool initial);
  void createRim5(bool initial);
  void deleteRim(int getRidOfFactorizationData=2);
  bool sanityCheck();
  public:
  inline double * solutionRegion(int section) const
  { if (!section) return rowActivityWork_; else return columnActivityWork_;}
  inline double * djRegion(int section) const
  { if (!section) return rowReducedCost_; else return reducedCostWork_;}
  inline double * lowerRegion(int section) const
  { if (!section) return rowLowerWork_; else return columnLowerWork_;}
  inline double * upperRegion(int section) const
  { if (!section) return rowUpperWork_; else return columnUpperWork_;}
  inline double * costRegion(int section) const
  { if (!section) return rowObjectiveWork_; else return objectiveWork_;}
  inline double * solutionRegion() const
  { return solution_;}
  inline double * djRegion() const
  { return dj_;}
  inline double * lowerRegion() const
  { return lower_;}
  inline double * upperRegion() const
  { return upper_;}
  inline double * costRegion() const
  { return cost_;}
  inline Status getStatus(int sequence) const
  {return static_cast<Status> (status_[sequence]&7);}
  inline void setStatus(int sequence, Status status)
  {
    unsigned char & st_byte = status_[sequence];
    st_byte &= ~7;
    st_byte |= status;
  }
  bool startPermanentArrays();
  void setInitialDenseFactorization(bool onOff);
  bool  initialDenseFactorization() const;
  inline int sequenceIn() const
  {return sequenceIn_;}
  inline int sequenceOut() const
  {return sequenceOut_;}
  inline void  setSequenceIn(int sequence)
  { sequenceIn_=sequence;}
  inline void  setSequenceOut(int sequence)
  { sequenceOut_=sequence;}
  inline int directionIn() const
  {return directionIn_;}
  inline int directionOut() const
  {return directionOut_;}
  inline void  setDirectionIn(int direction)
  { directionIn_=direction;}
  inline void  setDirectionOut(int direction)
  { directionOut_=direction;}
  inline double valueOut() const
  { return valueOut_;}
  inline int isColumn(int sequence) const
  { return sequence<numberColumns_ ? 1 : 0;}
  inline int sequenceWithin(int sequence) const
  { return sequence<numberColumns_ ? sequence : sequence-numberColumns_;}
  inline double solution(int sequence)
  { return solution_[sequence];}
  inline double & solutionAddress(int sequence)
  { return solution_[sequence];}
  inline double reducedCost(int sequence)
   { return dj_[sequence];}
  inline double & reducedCostAddress(int sequence)
   { return dj_[sequence];}
  inline double lower(int sequence)
  { return lower_[sequence];}
  inline double & lowerAddress(int sequence)
  { return lower_[sequence];}
  inline double upper(int sequence)
  { return upper_[sequence];}
  inline double & upperAddress(int sequence)
  { return upper_[sequence];}
  inline double cost(int sequence)
  { return cost_[sequence];}
  inline double & costAddress(int sequence)
  { return cost_[sequence];}
  inline double originalLower(int iSequence) const
  { if (iSequence<numberColumns_) return columnLower_[iSequence]; else
    return rowLower_[iSequence-numberColumns_];}
  inline double originalUpper(int iSequence) const
  { if (iSequence<numberColumns_) return columnUpper_[iSequence]; else
    return rowUpper_[iSequence-numberColumns_];}
  inline double theta() const
  { return theta_;}
  inline ClpNonLinearCost * nonLinearCost() const
  { return nonLinearCost_;}
  inline int moreSpecialOptions() const
  { return moreSpecialOptions_;}
  inline void setMoreSpecialOptions(int value)
  { moreSpecialOptions_ = value;}

  inline void setFakeBound(int sequence, FakeBound fakeBound)
  {
    unsigned char & st_byte = status_[sequence];
    st_byte &= ~24;
    st_byte |= fakeBound<<3;
  }
  inline FakeBound getFakeBound(int sequence) const
  {return static_cast<FakeBound> ((status_[sequence]>>3)&3);}
  inline void setRowStatus(int sequence, Status status)
  {
    unsigned char & st_byte = status_[sequence+numberColumns_];
    st_byte &= ~7;
    st_byte |= status;
  }
  inline Status getRowStatus(int sequence) const
  {return static_cast<Status> (status_[sequence+numberColumns_]&7);}
  inline void setColumnStatus(int sequence, Status status)
  {
    unsigned char & st_byte = status_[sequence];
    st_byte &= ~7;
    st_byte |= status;
  }
  inline Status getColumnStatus(int sequence) const
  {return static_cast<Status> (status_[sequence]&7);}
  inline void setPivoted( int sequence)
  { status_[sequence] |= 32;}
  inline void clearPivoted( int sequence)
  { status_[sequence] &= ~32; }
  inline bool pivoted(int sequence) const
  {return (((status_[sequence]>>5)&1)!=0);}
  void setFlagged( int sequence);
  inline void clearFlagged( int sequence)
  {
    status_[sequence] &= ~64;
  }
  inline bool flagged(int sequence) const
  {return ((status_[sequence]&64)!=0);}
  inline void setActive( int iRow)
  {
    status_[iRow] |= 128;
  }
  inline void clearActive( int iRow)
  {
    status_[iRow] &= ~128;
  }
  inline bool active(int iRow) const
  {return ((status_[iRow]&128)!=0);}
  void createStatus() ;
  void allSlackBasis(bool resetSolution=false);
    
  inline int lastBadIteration() const
  {return lastBadIteration_;}
  inline int progressFlag() const
  {return progressFlag_;}
  inline void forceFactorization(int value)
  { forceFactorization_ = value;}
  inline double rawObjectiveValue() const
  { return objectiveValue_;}
  void computeObjectiveValue(bool useWorkingSolution=false);
  double computeInternalObjectiveValue();
  inline int numberExtraRows() const
  { return numberExtraRows_;}
  inline int maximumBasic() const
  { return maximumBasic_;}
  inline int baseIteration() const
  { return baseIteration_;}
  void generateCpp( FILE * fp,bool defaultFactor=false);
  ClpFactorization * getEmptyFactorization();
  void setEmptyFactorization();
  void moveInfo(const ClpSimplex & rhs, bool justStatus=false);

  // These are only to be used using startFinishOptions (ClpSimplexDual, ClpSimplexPrimal)
  // *** At present only without scaling
  // *** Slacks havve -1.0 element (so == row activity) - take care
  void getBInvARow(int row, double* z, double * slack=NULL);
  
  void getBInvRow(int row, double* z);
  
  void getBInvACol(int col, double* vec);
  
  void getBInvCol(int col, double* vec);
  
  void getBasics(int* index);
  
    //-------------------------------------------------------------------------
       void setObjectiveCoefficient( int elementIndex, double elementValue );
       inline void setObjCoeff( int elementIndex, double elementValue )
       { setObjectiveCoefficient( elementIndex, elementValue);}

       void setColumnLower( int elementIndex, double elementValue );
      
       void setColumnUpper( int elementIndex, double elementValue );

      void setColumnBounds( int elementIndex,
        double lower, double upper );

      void setColumnSetBounds(const int* indexFirst,
                                   const int* indexLast,
                                   const double* boundList);
      
       inline void setColLower( int elementIndex, double elementValue )
       { setColumnLower(elementIndex, elementValue);}
       inline void setColUpper( int elementIndex, double elementValue )
       { setColumnUpper(elementIndex, elementValue);}

      inline void setColBounds( int elementIndex,
        double lower, double upper )
       { setColumnBounds(elementIndex, lower, upper);}

      inline void setColSetBounds(const int* indexFirst,
                                   const int* indexLast,
                                   const double* boundList)
      { setColumnSetBounds(indexFirst, indexLast, boundList);}
      
      void setRowLower( int elementIndex, double elementValue );
      
      void setRowUpper( int elementIndex, double elementValue ) ;
    
      void setRowBounds( int elementIndex,
                                 double lower, double upper ) ;
    
      void setRowSetBounds(const int* indexFirst,
                                   const int* indexLast,
                                   const double* boundList);
    

protected:


  double columnPrimalInfeasibility_;
  double rowPrimalInfeasibility_;
  int columnPrimalSequence_;
  int rowPrimalSequence_;
  double columnDualInfeasibility_;
  double rowDualInfeasibility_;
  int moreSpecialOptions_;
  int baseIteration_;
  double primalToleranceToGetOptimal_;
  double remainingDualInfeasibility_;
  double largeValue_;
  double largestPrimalError_;
  double largestDualError_;
  double alphaAccuracy_;
  double dualBound_;
  double alpha_;
  double theta_;
  double lowerIn_;
  double valueIn_;
  double upperIn_;
  double dualIn_;
  double lowerOut_;
  double valueOut_;
  double upperOut_;
  double dualOut_;
  double dualTolerance_;
  double primalTolerance_;
  double sumDualInfeasibilities_;
  double sumPrimalInfeasibilities_;
  double infeasibilityCost_;
  double sumOfRelaxedDualInfeasibilities_;
  double sumOfRelaxedPrimalInfeasibilities_;
  double acceptablePivot_;
  double * lower_;
  double * rowLowerWork_;
  double * columnLowerWork_;
  double * upper_;
  double * rowUpperWork_;
  double * columnUpperWork_;
  double * cost_;
  double * rowObjectiveWork_;
  double * objectiveWork_;
  CoinIndexedVector * rowArray_[6];
  CoinIndexedVector * columnArray_[6];
  int sequenceIn_;
  int directionIn_;
  int sequenceOut_;
  int directionOut_;
  int pivotRow_;
  int lastGoodIteration_;
  double * dj_;
  double * rowReducedCost_;
  double * reducedCostWork_;
  double * solution_;
  double * rowActivityWork_;
  double * columnActivityWork_;
  ClpSimplex * auxiliaryModel_;
  int numberDualInfeasibilities_;
  int numberDualInfeasibilitiesWithoutFree_;
  int numberPrimalInfeasibilities_;
  int numberRefinements_;
  ClpDualRowPivot * dualRowPivot_;
  ClpPrimalColumnPivot * primalColumnPivot_;
  int * pivotVariable_;
  ClpFactorization * factorization_;
  double * savedSolution_;
  int numberTimesOptimal_;
  ClpDisasterHandler * disasterArea_;
  int changeMade_;
  int algorithm_;
  int forceFactorization_;
  int perturbation_;
  unsigned char * saveStatus_;
  ClpNonLinearCost * nonLinearCost_;
  int lastBadIteration_;
  int lastFlaggedIteration_;
  int numberFake_;
  int numberChanged_;
  int progressFlag_;
  int firstFree_;
  int numberExtraRows_;
  int maximumBasic_;
  double incomingInfeasibility_;
  double allowedInfeasibility_;
  int automaticScale_;
  ClpSimplex * baseModel_;
  ClpSimplexProgress progress_;
public:
  mutable int spareIntArray_[4];
  mutable double spareDoubleArray_[4];
protected:
  friend class OsiClpSolverInterface;
};
//#############################################################################
void
ClpSimplexUnitTest(const std::string & mpsDir);

// For Devex stuff
#define DEVEX_TRY_NORM 1.0e-4
#define DEVEX_ADD_ONE 1.0
#endif

---