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