/home/coin/SVN-release/Cbc-1.1.1/Cgl/src/CglMixedIntegerRounding2/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 Common 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 
00146   CglMixedIntegerRounding2 (
00147     const CglMixedIntegerRounding2 &);
00148 
00150   virtual CglCutGenerator * clone() const;
00151 
00153   CglMixedIntegerRounding2 &
00154     operator=(
00155     const CglMixedIntegerRounding2& rhs);
00156   
00158   virtual
00159     ~CglMixedIntegerRounding2 ();
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","CglMixedIntegerRounding2");
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","CglMixedIntegerRounding2");
00197     }
00198   };
00199 
00201   inline int getCRITERION_ () const { return CRITERION_; };
00203 
00204 private:
00205   //--------------------------------------------------------------------------
00206   // Private member methods
00207 
00208   // Construct
00209   void gutsOfConstruct ( const int maxaggr,
00210                          const bool multiply,
00211                          const int criterion );
00212 
00213   // Delete
00214   void gutsOfDelete();
00215 
00216   // Copy
00217   void gutsOfCopy (const CglMixedIntegerRounding2& rhs);
00218 
00219   // Do preprocessing.
00220   // It determines the type of each row. It also identifies the variable
00221   // upper bounds and variable lower bounds.
00222   // It may change sense and RHS for ranged rows
00223   void mixIntRoundPreprocess(const OsiSolverInterface& si) const;
00224 
00225   // Determine the type of a given row.
00226   RowType determineRowType(const OsiSolverInterface& si,
00227                            const int rowLen, const int* ind, 
00228                            const double* coef, const char sense, 
00229                            const double rhs) const;
00230 
00231   // Generate MIR cuts
00232   void generateMirCuts( const OsiSolverInterface& si,
00233                         const double* xlp,
00234                         const double* colUpperBound,
00235                         const double* colLowerBound,
00236                         const CoinPackedMatrix& matrixByRow,
00237                         const double* LHS,
00238                         const double* coefByRow,
00239                         const int* colInds,
00240                         const int* rowStarts,
00241                         const int* rowLengths,
00242                         const CoinPackedMatrix& matrixByCol,
00243                         const double* coefByCol,
00244                         const int* rowInds,
00245                         const int* colStarts,
00246                         const int* colLengths,
00247                         OsiCuts& cs ) const;
00248 
00249   // Copy row selected to CoinIndexedVector
00250   void copyRowSelected( const int iAggregate,
00251                         const int rowSelected,
00252                         std::set<int>& setRowsAggregated,
00253                         int* listRowsAggregated,
00254                         double* xlpExtra,
00255                         const char sen,
00256                         const double rhs,
00257                         const double lhs,
00258                         const CoinPackedMatrix& matrixByRow,
00259                         CoinIndexedVector& rowToAggregate,
00260                         double& rhsToAggregate) const;
00261 
00262   // Select a row to aggregate
00263   bool selectRowToAggregate( const OsiSolverInterface& si,
00264                              const CoinIndexedVector& rowAggregated,
00265                              const double* colUpperBound,
00266                              const double* colLowerBound,
00267                              const std::set<int>& setRowsAggregated,
00268                              const double* xlp, const double* coefByCol,
00269                              const int* rowInds, const int* colStarts,
00270                              const int* colLengths,
00271                              int& rowSelected,
00272                              int& colSelected ) const;
00273 
00274   // Aggregation heuristic. 
00275   // Combines one or more rows of the original matrix 
00276   void aggregateRow( const int colSelected,
00277                      CoinIndexedVector& rowToAggregate, double rhs,
00278                      CoinIndexedVector& rowAggregated, 
00279                      double& rhsAggregated ) const;
00280 
00281   // Choose the bound substitution based on the criteria defined by the user
00282   inline bool isLowerSubst(const double inf, 
00283                            const double aj,
00284                            const double xlp, 
00285                            const double LB, 
00286                            const double UB) const;
00287     
00288   // Bound substitution heuristic
00289   bool boundSubstitution( const OsiSolverInterface& si,
00290                           const CoinIndexedVector& rowAggregated,
00291                           const double* xlp,
00292                           const double* xlpExtra,
00293                           const double* colUpperBound,
00294                           const double* colLowerBound,
00295                           CoinIndexedVector& mixedKnapsack,
00296                           double& rhsMixedKnapsack, double& sStar,
00297                           CoinIndexedVector& contVariablesInS ) const;
00298 
00299   // c-MIR separation heuristic
00300   bool cMirSeparation ( const OsiSolverInterface& si,
00301                         const CoinPackedMatrix& matrixByRow,
00302                         const CoinIndexedVector& rowAggregated,
00303                         const int* listRowsAggregated,
00304                         const char* sense, const double* RHS,
00305                         const double* coefByRow,
00306                         const int* colInds, const int* rowStarts,
00307                         const int* rowLengths,
00308                         const double* xlp, const double sStar,
00309                         const double* colUpperBound,
00310                         const double* colLowerBound,
00311                         const CoinIndexedVector& mixedKnapsack,
00312                         const double& rhsMixedKnapsack,
00313                         const CoinIndexedVector& contVariablesInS,
00314                         CoinIndexedVector * workVector,
00315                         OsiRowCut& flowCut ) const;
00316 
00317   // function to create one c-MIR inequality
00318   void cMirInequality( const int numInt, 
00319                        const double delta,
00320                        const double numeratorBeta,
00321                        const int *knapsackIndices,
00322                        const double* knapsackElements,
00323                        const double* xlp, 
00324                        const double sStar,             
00325                        const double* colUpperBound,
00326                        const std::set<int>& setC,
00327                        CoinIndexedVector& cMIR,
00328                        double& rhscMIR,
00329                        double& sCoef,
00330                        double& violation) const;
00331 
00332   // function to compute G
00333   inline double functionG( const double d, const double f ) const;
00334 
00335   // function to print statistics (used only in debug mode)
00336   void printStats(
00337                             std::ofstream & fout,
00338                             const bool hasCut,
00339                             const OsiSolverInterface& si,
00340                             const CoinIndexedVector& rowAggregated,
00341                             const double& rhsAggregated, const double* xlp,
00342                             const double* xlpExtra,
00343                             const int* listRowsAggregated,
00344                             const int* listColsSelected,
00345                             const int level,
00346                             const double* colUpperBound,
00347                             const double* colLowerBound ) const;
00348 
00349 
00350 private:
00351   //---------------------------------------------------------------------------
00352   // Private member data
00353   
00354   // Maximum number of rows to aggregate
00355   int MAXAGGR_;
00356   // Flag that indicates if an aggregated row is also multiplied by -1
00357   bool MULTIPLY_;
00358   // The criterion to use in the bound substitution
00359   int CRITERION_;
00360   // Tolerance used for numerical purposes
00361   double EPSILON_;
00363   int UNDEFINED_;
00364   // If violation of a cut is greater that this number, the cut is accepted
00365   double TOLERANCE_;
00366   // The number of rows of the problem.
00367   mutable int numRows_;
00368   // The number columns of the problem.
00369   mutable int numCols_;
00370   // Indicates whether preprocessing has been done.
00371   mutable bool doneInitPre_;
00372   // The array of CglMixIntRoundVUB2s.
00373   mutable CglMixIntRoundVUB2* vubs_;
00374   // The array of CglMixIntRoundVLB2s.
00375   mutable CglMixIntRoundVLB2* vlbs_;
00376   // Array with the row types of the rows in the model.
00377   mutable RowType* rowTypes_;
00378   // The indices of the rows of the initial matrix
00379   mutable int* indRows_;
00380   // The number of rows of type ROW_MIX
00381   mutable int numRowMix_;
00382   // The indices of the rows of type ROW_MIX
00383   mutable int* indRowMix_;
00384   // The number of rows of type ROW_CONT
00385   mutable int numRowCont_;
00386   // The indices of the rows of type ROW_CONT
00387   mutable int* indRowCont_;
00388   // The number of rows of type ROW_INT
00389   mutable int numRowInt_;
00390   // The indices of the rows of type ROW_INT
00391   mutable int* indRowInt_;
00392   // The number of rows of type ROW_CONT that have at least one variable
00393   // with variable upper or lower bound
00394   mutable int numRowContVB_;
00395   // The indices of the rows of type ROW_CONT that have at least one variable
00396   // with variable upper or lower bound
00397   mutable int* indRowContVB_;
00398   // If integer - for speed
00399   mutable char * integerType_;
00400   // Sense of rows (modified if ranges)
00401   mutable char * sense_;
00402   // RHS of rows (modified if ranges)
00403   mutable double * RHS_;
00404   
00405 };
00406 
00407 //#############################################################################
00408 // A function that tests the methods in the CglMixedIntegerRounding2 class. The
00409 // only reason for it not to be a member method is that this way it doesn't
00410 // have to be compiled into the library. And that's a gain, because the
00411 // library should be compiled with optimization on, but this method should be
00412 // compiled with debugging.
00413 void CglMixedIntegerRounding2UnitTest(const OsiSolverInterface * siP,
00414                           const std::string mpdDir );
00415   
00416 #endif

Generated on Thu May 15 21:59:04 2008 by  doxygen 1.4.7