- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Alps-1.3.0/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 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