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 int *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