CglMixedIntegerRounding.hpp

Go to the documentation of this file.
00001 // LAST EDIT: 
00002 //-----------------------------------------------------------------------------
00003 // name: Mixed Integer Rounding Cut Generator
00004 // authors: Joao Goncalves (jog7@lehigh.edu) 
00005 //          Laszlo Ladanyi (ladanyi@us.ibm.com) 
00006 // date: August 11, 2004 
00007 //-----------------------------------------------------------------------------
00008 // Copyright (C) 2004, International Business Machines Corporation and others. 
00009 // All Rights Reserved.
00010 // This code is published under the Eclipse Public License.
00011 
00012 #ifndef CglMixedIntegerRounding_H
00013 #define CglMixedIntegerRounding_H
00014 
00015 #include <iostream>
00016 #include <fstream>
00017 //#include <vector>
00018 
00019 #include "CoinError.hpp"
00020 
00021 #include "CglCutGenerator.hpp"
00022 
00023 //=============================================================================
00024 
00025 #ifndef CGL_DEBUG
00026 #define CGL_DEBUG 0
00027 #endif
00028 
00029 //=============================================================================
00030 
00031 // Class to store variable upper bounds (VUB)
00032 class CglMixIntRoundVUB
00033 {
00034   // Variable upper bounds have the form x_j <= a y_j, where x_j is
00035   // a continuous variable and y_j is an integer variable
00036 
00037 protected:
00038   int    var_;            // The index of y_j
00039   double val_;            // The value of a 
00040 
00041 public:
00042   // Default constructor
00043   CglMixIntRoundVUB() : var_(-1), val_(-1) {}
00044 
00045   // Copy constructor
00046   CglMixIntRoundVUB(const CglMixIntRoundVUB& source) { 
00047     var_ = source.var_; 
00048     val_ = source.val_; 
00049   } 
00050 
00051   // Assignment operator
00052   CglMixIntRoundVUB& operator=(const CglMixIntRoundVUB& rhs) { 
00053     if (this != &rhs) { 
00054       var_ = rhs.var_; 
00055       val_ = rhs.val_; 
00056     }
00057     return *this; 
00058   }
00059 
00060   // Destructor
00061   ~CglMixIntRoundVUB() {}
00062 
00063   // Query and set functions
00064   int    getVar() const          { return var_; }
00065   double getVal() const          { return val_; }
00066   void   setVar(const int v)     { var_ = v; }
00067   void   setVal(const double v)  { val_ = v; }
00068 };
00069 
00070 //=============================================================================
00071 
00072 // Class to store variable lower bounds (VLB).
00073 // It is the same as the class to store variable upper bounds
00074 typedef CglMixIntRoundVUB CglMixIntRoundVLB;
00075 
00076 //=============================================================================
00077 
00080 // Reference: 
00081 //    Hugues Marchand and Laurence A. Wolsey
00082 //    Aggregation and Mixed Integer Rounding to Solve MIPs
00083 //    Operations Research, 49(3), May-June 2001.
00084 //    Also published as CORE Dicusion Paper 9839, June 1998.
00085 
00086 class CglMixedIntegerRounding : public CglCutGenerator {
00087 
00088   friend void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
00089                                               const std::string mpdDir);
00090 
00091 
00092 private:
00093   //---------------------------------------------------------------------------
00094   // Enumeration constants that describe the various types of rows
00095   enum RowType {
00096     // The row type of this row is NOT defined yet.
00097     ROW_UNDEFINED,
00101     ROW_VARUB,
00105     ROW_VARLB,
00108     ROW_VAREQ,
00109     // The row contains continuous and integer variables;
00110     // the total number of variables is at least 2
00111     ROW_MIX,
00112     // The row contains only continuous variables
00113     ROW_CONT,
00114     // The row contains only integer variables
00115     ROW_INT,
00116     // The row contains other types of rows
00117     ROW_OTHER
00118   };
00119 
00120 
00121 public:
00122 
00129   virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
00130                             const CglTreeInfo info = CglTreeInfo());
00132 
00133   //---------------------------------------------------------------------------
00136 
00137   CglMixedIntegerRounding ();
00138 
00140   CglMixedIntegerRounding (const int maxaggr,
00141                            const bool multiply,
00142                            const int criterion,
00143                            const int preproc = -1);
00144 
00146   CglMixedIntegerRounding (
00147     const CglMixedIntegerRounding &);
00148 
00150   virtual CglCutGenerator * clone() const;
00151 
00153   CglMixedIntegerRounding &
00154     operator=(
00155     const CglMixedIntegerRounding& rhs);
00156   
00158   virtual
00159     ~CglMixedIntegerRounding ();
00161   virtual void refreshSolver(OsiSolverInterface * solver);
00163   virtual std::string generateCpp( FILE * fp);
00165 
00166   //---------------------------------------------------------------------------
00169 
00170   inline void setMAXAGGR_ (int maxaggr) {
00171     if (maxaggr > 0) {
00172       MAXAGGR_ = maxaggr;
00173     }
00174     else {
00175       throw CoinError("Unallowable value. maxaggr must be > 0",
00176                       "gutsOfConstruct","CglMixedIntegerRounding");
00177     }
00178   }
00179 
00181   inline int getMAXAGGR_ () const { return MAXAGGR_; }
00182 
00184   inline void setMULTIPLY_ (bool multiply) { MULTIPLY_ = multiply; }
00185 
00187   inline bool getMULTIPLY_ () const { return MULTIPLY_; }
00188 
00190   inline void setCRITERION_ (int criterion) {
00191     if ((criterion >= 1) && (criterion <= 3)) {
00192       CRITERION_ = criterion;
00193     }
00194     else {
00195       throw CoinError("Unallowable value. criterion must be 1, 2 or 3",
00196                       "gutsOfConstruct","CglMixedIntegerRounding");
00197     }
00198   }
00199 
00201   inline int getCRITERION_ () const { return CRITERION_; }
00202 
00203 
00205   void setDoPreproc(int value);
00207   bool getDoPreproc() const;
00208 
00210 
00211 private:
00212   //--------------------------------------------------------------------------
00213   // Private member methods
00214 
00215   // Construct
00216   void gutsOfConstruct (const int maxaggr,
00217                         const bool multiply,
00218                         const int criterion,
00219                         const int preproc);
00220 
00221   // Delete
00222   void gutsOfDelete();
00223 
00224   // Copy
00225   void gutsOfCopy (const CglMixedIntegerRounding& rhs);
00226 
00227   // Do preprocessing.
00228   // It determines the type of each row. It also identifies the variable
00229   // upper bounds and variable lower bounds.
00230   // It may change sense and RHS for ranged rows
00231   void mixIntRoundPreprocess(const OsiSolverInterface& si);
00232 
00233   // Determine the type of a given row.
00234   RowType determineRowType(const OsiSolverInterface& si,
00235                            const int rowLen, const int* ind, 
00236                            const double* coef, const char sense, 
00237                            const double rhs) const;
00238 
00239   // Generate MIR cuts
00240   void generateMirCuts( const OsiSolverInterface& si,
00241                         const double* xlp,
00242                         const double* colUpperBound,
00243                         const double* colLowerBound,
00244                         const CoinPackedMatrix& matrixByRow,
00245                         const double* LHS,
00246                         const double* coefByRow,
00247                         const int* colInds,
00248                         const int* rowStarts,
00249                         const int* rowLengths,
00250                         //const CoinPackedMatrix& matrixByCol,
00251                         const double* coefByCol,
00252                         const int* rowInds,
00253                         const int* colStarts,
00254                         const int* colLengths,
00255                         OsiCuts& cs ) const;
00256 
00257   // Copy row selected to CoinPackedVector
00258   void copyRowSelected( const int iAggregate,
00259                         const int rowSelected,
00260                         std::set<int>& setRowsAggregated,
00261                         int* listRowsAggregated,
00262                         double* xlpExtra,
00263                         const char sen,
00264                         const double rhs,
00265                         const double lhs,
00266                         const CoinPackedMatrix& matrixByRow,
00267                         CoinPackedVector& rowToAggregate,
00268                         double& rhsToAggregate) const;
00269 
00270   // Select a row to aggregate
00271   bool selectRowToAggregate( const OsiSolverInterface& si,
00272                              const CoinPackedVector& rowAggregated,
00273                              const double* colUpperBound,
00274                              const double* colLowerBound,
00275                              const std::set<int>& setRowsAggregated,
00276                              const double* xlp, const double* coefByCol,
00277                              const int* rowInds, const int* colStarts,
00278                              const int* colLengths,
00279                              int& rowSelected,
00280                              int& colSelected ) const;
00281 
00282   // Aggregation heuristic. 
00283   // Combines one or more rows of the original matrix 
00284   void aggregateRow( const int colSelected,
00285                      CoinPackedVector& rowToAggregate, double rhs,
00286                      CoinPackedVector& rowAggregated, 
00287                      double& rhsAggregated ) const;
00288 
00289   // Choose the bound substitution based on the criteria defined by the user
00290   inline bool isLowerSubst(const double inf, 
00291                            const double aj,
00292                            const double xlp, 
00293                            const double LB, 
00294                            const double UB) const;
00295     
00296   // Bound substitution heuristic
00297   bool boundSubstitution( const OsiSolverInterface& si,
00298                           const CoinPackedVector& rowAggregated,
00299                           const double* xlp,
00300                           const double* xlpExtra,
00301                           const double* colUpperBound,
00302                           const double* colLowerBound,
00303                           CoinPackedVector& mixedKnapsack,
00304                           double& rhsMixedKnapsack, double& sStar,
00305                           CoinPackedVector& contVariablesInS ) const;
00306 
00307   // c-MIR separation heuristic
00308   bool cMirSeparation ( const OsiSolverInterface& si,
00309                         const CoinPackedMatrix& matrixByRow,
00310                         const CoinPackedVector& rowAggregated,
00311                         const int* listRowsAggregated,
00312                         const char* sense, const double* RHS,
00313                         //const double* coefByRow,
00314                         //const int* colInds, const int* rowStarts,
00315                         //const int* rowLengths,
00316                         const double* xlp, const double sStar,
00317                         const double* colUpperBound,
00318                         const double* colLowerBound,
00319                         const CoinPackedVector& mixedKnapsack,
00320                         const double& rhsMixedKnapsack,
00321                         const CoinPackedVector& contVariablesInS,
00322                         OsiRowCut& flowCut ) const;
00323 
00324   // function to create one c-MIR inequality
00325   void cMirInequality( const int numInt, 
00326                        const double delta,
00327                        const double numeratorBeta,
00328                        const int *knapsackIndices,
00329                        const double* knapsackElements,
00330                        const double* xlp, 
00331                        const double sStar,             
00332                        const double* colUpperBound,
00333                        const std::set<int>& setC,
00334                        CoinPackedVector& cMIR,
00335                        double& rhscMIR,
00336                        double& sCoef,
00337                        double& violation) const;
00338 
00339   // function to compute G
00340   inline double functionG( const double d, const double f ) const;
00341 
00342   // function to print statistics (used only in debug mode)
00343   void printStats(
00344                             std::ofstream & fout,
00345                             const bool hasCut,
00346                             const OsiSolverInterface& si,
00347                             const CoinPackedVector& rowAggregated,
00348                             const double& rhsAggregated, const double* xlp,
00349                             const double* xlpExtra,
00350                             const int* listRowsAggregated,
00351                             const int* listColsSelected,
00352                             const int level,
00353                             const double* colUpperBound,
00354                             const double* colLowerBound ) const;
00355 
00356 
00357 private:
00358   //---------------------------------------------------------------------------
00359   // Private member data
00360   
00361   // Maximum number of rows to aggregate
00362   int MAXAGGR_;
00363   // Flag that indicates if an aggregated row is also multiplied by -1
00364   bool MULTIPLY_;
00365   // The criterion to use in the bound substitution
00366   int CRITERION_;
00367   // Tolerance used for numerical purposes
00368   double EPSILON_;
00370   int UNDEFINED_;
00371   // If violation of a cut is greater that this number, the cut is accepted
00372   double TOLERANCE_;
00380   int doPreproc_;
00381   // The number of rows of the problem.
00382   int numRows_;
00383   // The number columns of the problem.
00384   int numCols_;
00385   // Indicates whether preprocessing has been done.
00386   bool doneInitPre_;
00387   // The array of CglMixIntRoundVUBs.
00388   CglMixIntRoundVUB* vubs_;
00389   // The array of CglMixIntRoundVLBs.
00390   CglMixIntRoundVLB* vlbs_;
00391   // Array with the row types of the rows in the model.
00392   RowType* rowTypes_;
00393   // The indices of the rows of the initial matrix
00394   int* indRows_;
00395   // The number of rows of type ROW_MIX
00396   int numRowMix_;
00397   // The indices of the rows of type ROW_MIX
00398   int* indRowMix_;
00399   // The number of rows of type ROW_CONT
00400   int numRowCont_;
00401   // The indices of the rows of type ROW_CONT
00402   int* indRowCont_;
00403   // The number of rows of type ROW_INT
00404   int numRowInt_;
00405   // The indices of the rows of type ROW_INT
00406   int* indRowInt_;
00407   // The number of rows of type ROW_CONT that have at least one variable
00408   // with variable upper or lower bound
00409   int numRowContVB_;
00410   // The indices of the rows of type ROW_CONT that have at least one variable
00411   // with variable upper or lower bound
00412   int* indRowContVB_;
00413   // Sense of rows (modified if ranges)
00414   char * sense_;
00415   // RHS of rows (modified if ranges)
00416   double * RHS_;
00417   
00418 };
00419 
00420 //#############################################################################
00421 // A function that tests the methods in the CglMixedIntegerRounding class. The
00422 // only reason for it not to be a member method is that this way it doesn't
00423 // have to be compiled into the library. And that's a gain, because the
00424 // library should be compiled with optimization on, but this method should be
00425 // compiled with debugging.
00426 void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
00427                                      const std::string mpdDir);
00428   
00429 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on 31 Oct 2014 for Cgl by  doxygen 1.6.1