- Main Page
- Namespaces
- Classes
- Files
- Directories

- Search for |

- File List
- File Members

# 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()) const;
    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) const;
    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   mutable int numRows_;
    00383   // The number columns of the problem.
    00384   mutable int numCols_;
    00385   // Indicates whether preprocessing has been done.
    00386   mutable bool doneInitPre_;
    00387   // The array of CglMixIntRoundVUBs.
    00388   mutable CglMixIntRoundVUB* vubs_;
    00389   // The array of CglMixIntRoundVLBs.
    00390   mutable CglMixIntRoundVLB* vlbs_;
    00391   // Array with the row types of the rows in the model.
    00392   mutable RowType* rowTypes_;
    00393   // The indices of the rows of the initial matrix
    00394   mutable int* indRows_;
    00395   // The number of rows of type ROW_MIX
    00396   mutable int numRowMix_;
    00397   // The indices of the rows of type ROW_MIX
    00398   mutable int* indRowMix_;
    00399   // The number of rows of type ROW_CONT
    00400   mutable int numRowCont_;
    00401   // The indices of the rows of type ROW_CONT
    00402   mutable int* indRowCont_;
    00403   // The number of rows of type ROW_INT
    00404   mutable int numRowInt_;
    00405   // The indices of the rows of type ROW_INT
    00406   mutable 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   mutable 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   mutable int* indRowContVB_;
    00413   // Sense of rows (modified if ranges)
    00414   mutable char * sense_;
    00415   // RHS of rows (modified if ranges)
    00416   mutable 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