00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef CglMixedIntegerRounding_H
00013 #define CglMixedIntegerRounding_H
00014
00015 #include <iostream>
00016 #include <fstream>
00017
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
00032 class CglMixIntRoundVUB
00033 {
00034
00035
00036
00037 protected:
00038 int var_;
00039 double val_;
00040
00041 public:
00042
00043 CglMixIntRoundVUB() : var_(-1), val_(-1) {}
00044
00045
00046 CglMixIntRoundVUB(const CglMixIntRoundVUB& source) {
00047 var_ = source.var_;
00048 val_ = source.val_;
00049 }
00050
00051
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
00061 ~CglMixIntRoundVUB() {}
00062
00063
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
00073
00074 typedef CglMixIntRoundVUB CglMixIntRoundVLB;
00075
00076
00077
00080
00081
00082
00083
00084
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
00095 enum RowType {
00096
00097 ROW_UNDEFINED,
00101 ROW_VARUB,
00105 ROW_VARLB,
00108 ROW_VAREQ,
00109
00110
00111 ROW_MIX,
00112
00113 ROW_CONT,
00114
00115 ROW_INT,
00116
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
00206
00207
00208 void gutsOfConstruct ( const int maxaggr,
00209 const bool multiply,
00210 const int criterion );
00211
00212
00213 void gutsOfDelete();
00214
00215
00216 void gutsOfCopy (const CglMixedIntegerRounding& rhs);
00217
00218
00219
00220
00221
00222 void mixIntRoundPreprocess(const OsiSolverInterface& si) const;
00223
00224
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
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
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
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
00274
00275 void aggregateRow( const int colSelected,
00276 CoinPackedVector& rowToAggregate, double rhs,
00277 CoinPackedVector& rowAggregated,
00278 double& rhsAggregated ) const;
00279
00280
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
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
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
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
00331 inline double functionG( const double d, const double f ) const;
00332
00333
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
00351
00352
00353 int MAXAGGR_;
00354
00355 bool MULTIPLY_;
00356
00357 int CRITERION_;
00358
00359 double EPSILON_;
00361 int UNDEFINED_;
00362
00363 double TOLERANCE_;
00364
00365 mutable int numRows_;
00366
00367 mutable int numCols_;
00368
00369 mutable bool doneInitPre_;
00370
00371 mutable CglMixIntRoundVUB* vubs_;
00372
00373 mutable CglMixIntRoundVLB* vlbs_;
00374
00375 mutable RowType* rowTypes_;
00376
00377 mutable int* indRows_;
00378
00379 mutable int numRowMix_;
00380
00381 mutable int* indRowMix_;
00382
00383 mutable int numRowCont_;
00384
00385 mutable int* indRowCont_;
00386
00387 mutable int numRowInt_;
00388
00389 mutable int* indRowInt_;
00390
00391
00392 mutable int numRowContVB_;
00393
00394
00395 mutable int* indRowContVB_;
00396
00397 mutable char * sense_;
00398
00399 mutable double * RHS_;
00400
00401 };
00402
00403
00404
00405
00406
00407
00408
00409 void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
00410 const std::string mpdDir );
00411
00412 #endif