CglGMI.hpp

Go to the documentation of this file.

// Last edit: 02/05/2013
//
// Name:     CglGMI.hpp
// Author:   Giacomo Nannicini
//           Singapore University of Technology and Design, Singapore
//           email: nannicini@sutd.edu.sg
// Date:     11/17/09
//-----------------------------------------------------------------------------
// Copyright (C) 2009, Giacomo Nannicini.  All Rights Reserved.
 
#ifndef CglGMI_H
#define CglGMI_H
 
#include "CglCutGenerator.hpp"
#include "CglGMIParam.hpp"
#include "CoinWarmStartBasis.hpp"
#include "CoinFactorization.hpp"
 
/* Enable tracking of rejection of cutting planes. If this is disabled,
   the cut generator is slightly faster. If defined, it enables proper use
   of setTrackRejection and related functions. */
//#define TRACK_REJECT
 
/* Debug output */
//#define GMI_TRACE
 
/* Debug output: print optimal tableau */
//#define GMI_TRACETAB
 
/* Print reason for cut rejection, whenever a cut is discarded */
//#define GMI_TRACE_CLEAN
 
class CglGMI : public CglCutGenerator {
 
  friend void CglGMIUnitTest(const OsiSolverInterface * siP,
                             const std::string mpdDir);
public:
 
  enum RejectionType{
    failureFractionality,
    failureDynamism,
    failureViolation,
    failureSupport,
    failureScale
  };
 
  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
                            const CglTreeInfo info = CglTreeInfo());
 
  virtual bool needsOptimalBasis() const { return true; }
 
  // Function for checking equality with user tolerance
  inline bool areEqual(double x, double y, 
                       double epsAbs = 1e-12, 
                       double epsRel = 1e-12) {
    return (fabs((x) - (y)) <= 
            std::max(epsAbs, epsRel * std::max(fabs(x), fabs(y))));
  }
 
  // Function for checking is a number is zero
  inline bool isZero(double x, double epsZero = 1e-20) {
    return (fabs(x) <= epsZero);
  }
 
 
  // Function for checking if a number is integer
  inline bool isIntegerValue(double x, 
                             double intEpsAbs = 1e-9,
                             double intEpsRel = 1e-15) {
    return (fabs((x) - floor((x)+0.5)) <= 
            std::max(intEpsAbs, intEpsRel * fabs(x)));
  }
 
  
  
  
 
  // Set the parameters to the values of the given CglGMIParam object.
  void setParam(const CglGMIParam &source); 
  // Return the CglGMIParam object of the generator. 
  inline CglGMIParam getParam() const {return param;}
  inline CglGMIParam & getParam() {return param;}
 
  // Compute entries of is_integer.
  void computeIsInteger();
 
  void printOptTab(OsiSolverInterface *solver) const;
 
  void setTrackRejection(bool value);
  bool getTrackRejection();
 
  int getNumberRejectedCuts(RejectionType reason);
 
  void resetRejectionCounters();
 
  int getNumberGeneratedCuts();
  
 
  CglGMI();
 
  CglGMI(const CglGMIParam &param);
 
  CglGMI(const CglGMI &);
 
  virtual CglCutGenerator * clone() const;
 
  CglGMI & operator=(const CglGMI& rhs);
  
  virtual ~CglGMI();
  virtual std::string generateCpp( FILE * fp);
 
    
private:
  
  // Private member methods
 
 
  // Method generating the cuts after all CglGMI members are properly set.
  void generateCuts(OsiCuts & cs);
 
  inline double aboveInteger(double value) const; 
 
  inline bool computeCutFractionality(double varRhs, double& cutRhs);
 
  inline double computeCutCoefficient(double rowElem, int index);
 
  inline void eliminateSlack(double cutElem, int cutIndex, double* cut,
                              double& cutRhs, const double *elements, 
                              const CoinBigIndex *rowStart, const int *indices, 
                              const int *rowLength, const double *rhs);
 
  inline void flip(double& rowElem, int rowIndex);
 
  inline void unflipOrig(double& rowElem, int rowIndex, double& rowRhs);
  inline void unflipSlack(double& rowElem, int rowIndex, double& rowRhs,
                           const double* slack_val);
 
  inline void packRow(double* row, double* rowElem, int* rowIndex,
                       int& rowNz);
 
  bool cleanCut(double* cutElem, int* cutIndex, int& cutNz,
                 double& cutRhs, const double* xbar);
 
 
  bool checkViolation(const double* cutElem, const int* cutIndex,
                       int cutNz, double cutrhs, const double* xbar);
 
  bool checkDynamism(const double* cutElem, const int* cutIndex,
                      int cutNz);
 
  bool checkSupport(int cutNz);
 
  bool removeSmallCoefficients(double* cutElem, int* cutIndex, 
                                 int& cutNz, double& cutRhs);
 
  void relaxRhs(double& rhs);
 
  bool scaleCut(double* cutElem, int* cutIndex, int cutNz,
                 double& cutRhs, int scalingType);
 
  bool scaleCutIntegral(double* cutElem, int* cutIndex, int cutNz,
                          double& cutRhs);
 
  bool nearestRational(double val, double maxdelta, long maxdnom,
                        long& numerator, long& denominator);
 
  long computeGcd(long a, long b);
 
  void printvecINT(const char *vecstr, const int *x, int n) const;
  void printvecDBL(const char *vecstr, const double *x, int n) const;
  void printvecDBL(const char *vecstr, const double *elem, const int * index, 
                   int nz) const;
 
  int factorize(CoinFactorization & factorization,
                int* colBasisIndex, int* rowBasisIndex);
 
 
 
  
  // Private member data
 
 
  CglGMIParam param;
 
  int nrow; 
 
  int ncol;
 
  const double *colLower;
 
  const double *colUpper;
  
  const double *rowLower;
 
  const double *rowUpper;
 
  const double *rowRhs;
 
  bool *isInteger;
 
  int *cstat;
 
  int *rstat;
 
  OsiSolverInterface *solver;
 
  const double *xlp;
 
  const double *rowActivity;
 
  const CoinPackedMatrix *byRow;
 
  const CoinPackedMatrix *byCol;
 
  double f0;
  double f0compl;
  double ratiof0compl;
 
#if defined(TRACK_REJECT) || defined (TRACK_REJECT_SIMPLE)
  bool trackRejection;
  int fracFail;
  int dynFail;
  int violFail;
  int suppFail;
  int smallCoeffFail;
  int scaleFail;
  int numGeneratedCuts;
#endif
 
};
 
//#############################################################################
void CglGMIUnitTest(const OsiSolverInterface * siP,
                         const std::string mpdDir );
 
 
#endif