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

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