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

Generated on 15 Jun 2013 for Cgl by  doxygen 1.6.1