# CglGMI.hpp

Go to the documentation of this file.

    00001 // Last edit: 02/05/2013
    00002 //
    00003 // Name:     CglGMI.hpp
    00004 // Author:   Giacomo Nannicini
    00005 //           Singapore University of Technology and Design, Singapore
    00006 //           email: nannicini@sutd.edu.sg
    00007 // Date:     11/17/09
    00008 //-----------------------------------------------------------------------------
    00009 // Copyright (C) 2009, Giacomo Nannicini.  All Rights Reserved.
    00010
    00011 #ifndef CglGMI_H
    00012 #define CglGMI_H
    00013
    00014 #include "CglCutGenerator.hpp"
    00015 #include "CglGMIParam.hpp"
    00016 #include "CoinWarmStartBasis.hpp"
    00017 #include "CoinFactorization.hpp"
    00018
    00019 /* Enable tracking of rejection of cutting planes. If this is disabled,
    00020    the cut generator is slightly faster. If defined, it enables proper use
    00021    of setTrackRejection and related functions. */
    00022 //#define TRACK_REJECT
    00023
    00024 /* Debug output */
    00025 //#define GMI_TRACE
    00026
    00027 /* Debug output: print optimal tableau */
    00028 //#define GMI_TRACETAB
    00029
    00030 /* Print reason for cut rejection, whenever a cut is discarded */
    00031 //#define GMI_TRACE_CLEAN
    00032
    00037 class CglGMI : public CglCutGenerator {
    00038
    00039   friend void CglGMIUnitTest(const OsiSolverInterface * siP,
    00040                              const std::string mpdDir);
    00041 public:
    00042
    00044   enum RejectionType{
    00045     failureFractionality,
    00046     failureDynamism,
    00047     failureViolation,
    00048     failureSupport,
    00049     failureScale
    00050   };
    00051
    00073   virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
    00074                             const CglTreeInfo info = CglTreeInfo());
    00075
    00077   virtual bool needsOptimalBasis() const { return true; }
    00079
    00082   // Function for checking equality with user tolerance
    00083   inline bool areEqual(double x, double y,
    00084                        double epsAbs = 1e-12,
    00085                        double epsRel = 1e-12) {
    00086     return (fabs((x) - (y)) <=
    00087             std::max(epsAbs, epsRel * std::max(fabs(x), fabs(y))));
    00088   }
    00089
    00090   // Function for checking is a number is zero
    00091   inline bool isZero(double x, double epsZero = 1e-20) {
    00092     return (fabs(x) <= epsZero);
    00093   }
    00094
    00095
    00096   // Function for checking if a number is integer
    00097   inline bool isIntegerValue(double x,
    00098                              double intEpsAbs = 1e-9,
    00099                              double intEpsRel = 1e-15) {
    00100     return (fabs((x) - floor((x)+0.5)) <=
    00101             std::max(intEpsAbs, intEpsRel * fabs(x)));
    00102   }
    00103
    00104
    00106
    00107
    00110
    00111   // Set the parameters to the values of the given CglGMIParam object.
    00112   void setParam(const CglGMIParam &source);
    00113   // Return the CglGMIParam object of the generator.
    00114   inline CglGMIParam getParam() const {return param;}
    00115   inline CglGMIParam & getParam() {return param;}
    00116
    00117   // Compute entries of is_integer.
    00118   void computeIsInteger();
    00119
    00121   void printOptTab(OsiSolverInterface *solver) const;
    00122
    00126   void setTrackRejection(bool value);
    00127   bool getTrackRejection();
    00128
    00130   int getNumberRejectedCuts(RejectionType reason);
    00131
    00133   void resetRejectionCounters();
    00134
    00136   int getNumberGeneratedCuts();
    00137
    00139
    00142
    00143   CglGMI();
    00144
    00146   CglGMI(const CglGMIParam &param);
    00147
    00149   CglGMI(const CglGMI &);
    00150
    00152   virtual CglCutGenerator * clone() const;
    00153
    00155   CglGMI & operator=(const CglGMI& rhs);
    00156
    00158   virtual ~CglGMI();
    00160   virtual std::string generateCpp( FILE * fp);
    00161
    00163
    00164 private:
    00165
    00166   // Private member methods
    00167
    00171
    00172   // Method generating the cuts after all CglGMI members are properly set.
    00173   void generateCuts(OsiCuts & cs);
    00174
    00176   inline double aboveInteger(double value) const;
    00177
    00180   inline bool computeCutFractionality(double varRhs, double& cutRhs);
    00181
    00183   inline double computeCutCoefficient(double rowElem, int index);
    00184
    00187   inline void eliminateSlack(double cutElem, int cutIndex, double* cut,
    00188                               double& cutRhs, const double *elements,
    00189                               const int *rowStart, const int *indices,
    00190                               const int *rowLength, const double *rhs);
    00191
    00194   inline void flip(double& rowElem, int rowIndex);
    00195
    00200   inline void unflipOrig(double& rowElem, int rowIndex, double& rowRhs);
    00201   inline void unflipSlack(double& rowElem, int rowIndex, double& rowRhs,
    00202                            const double* slack_val);
    00203
    00205   inline void packRow(double* row, double* rowElem, int* rowIndex,
    00206                        int& rowNz);
    00207
    00213   bool cleanCut(double* cutElem, int* cutIndex, int& cutNz,
    00214                  double& cutRhs, const double* xbar);
    00215
    00218
    00220   bool checkViolation(const double* cutElem, const int* cutIndex,
    00221                        int cutNz, double cutrhs, const double* xbar);
    00222
    00224   bool checkDynamism(const double* cutElem, const int* cutIndex,
    00225                       int cutNz);
    00226
    00228   bool checkSupport(int cutNz);
    00229
    00231   bool removeSmallCoefficients(double* cutElem, int* cutIndex,
    00232                                  int& cutNz, double& cutRhs);
    00233
    00235   void relaxRhs(double& rhs);
    00236
    00242   bool scaleCut(double* cutElem, int* cutIndex, int cutNz,
    00243                  double& cutRhs, int scalingType);
    00244
    00246   bool scaleCutIntegral(double* cutElem, int* cutIndex, int cutNz,
    00247                           double& cutRhs);
    00248
    00250   bool nearestRational(double val, double maxdelta, long maxdnom,
    00251                         long& numerator, long& denominator);
    00252
    00254   long computeGcd(long a, long b);
    00255
    00257   void printvecINT(const char *vecstr, const int *x, int n) const;
    00259   void printvecDBL(const char *vecstr, const double *x, int n) const;
    00261   void printvecDBL(const char *vecstr, const double *elem, const int * index,
    00262                    int nz) const;
    00263
    00268   int factorize(CoinFactorization & factorization,
    00269                 int* colBasisIndex, int* rowBasisIndex);
    00270
    00271
    00273
    00274
    00275   // Private member data
    00276
    00280
    00282   CglGMIParam param;
    00283
    00285   int nrow;
    00286
    00288   int ncol;
    00289
    00291   const double *colLower;
    00292
    00294   const double *colUpper;
    00295
    00297   const double *rowLower;
    00298
    00300   const double *rowUpper;
    00301
    00303   const double *rowRhs;
    00304
    00307   bool *isInteger;
    00308
    00310   int *cstat;
    00311
    00313   int *rstat;
    00314
    00316   OsiSolverInterface *solver;
    00317
    00319   const double *xlp;
    00320
    00322   const double *rowActivity;
    00323
    00326   const CoinPackedMatrix *byRow;
    00327
    00330   const CoinPackedMatrix *byCol;
    00331
    00333   double f0;
    00334   double f0compl;
    00335   double ratiof0compl;
    00336
    00337 #if defined(TRACK_REJECT) || defined (TRACK_REJECT_SIMPLE)
    00339   bool trackRejection;
    00341   int fracFail;
    00342   int dynFail;
    00343   int violFail;
    00344   int suppFail;
    00345   int smallCoeffFail;
    00346   int scaleFail;
    00348   int numGeneratedCuts;
    00349 #endif
    00350
    00352 };
    00353
    00354 //#############################################################################
    00360 void CglGMIUnitTest(const OsiSolverInterface * siP,
    00361                          const std::string mpdDir );
    00362
    00363
    00364 #endif

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines