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 const int preproc = -1);
00144
00146 CglMixedIntegerRounding (
00147 const CglMixedIntegerRounding &);
00148
00150 virtual CglCutGenerator * clone() const;
00151
00153 CglMixedIntegerRounding &
00154 operator=(
00155 const CglMixedIntegerRounding& rhs);
00156
00158 virtual
00159 ~CglMixedIntegerRounding ();
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","CglMixedIntegerRounding");
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","CglMixedIntegerRounding");
00197 }
00198 }
00199
00201 inline int getCRITERION_ () const { return CRITERION_; }
00202
00203
00205 void setDoPreproc(int value);
00207 bool getDoPreproc() const;
00208
00210
00211 private:
00212
00213
00214
00215
00216 void gutsOfConstruct (const int maxaggr,
00217 const bool multiply,
00218 const int criterion,
00219 const int preproc);
00220
00221
00222 void gutsOfDelete();
00223
00224
00225 void gutsOfCopy (const CglMixedIntegerRounding& rhs);
00226
00227
00228
00229
00230
00231 void mixIntRoundPreprocess(const OsiSolverInterface& si) const;
00232
00233
00234 RowType determineRowType(const OsiSolverInterface& si,
00235 const int rowLen, const int* ind,
00236 const double* coef, const char sense,
00237 const double rhs) const;
00238
00239
00240 void generateMirCuts( const OsiSolverInterface& si,
00241 const double* xlp,
00242 const double* colUpperBound,
00243 const double* colLowerBound,
00244 const CoinPackedMatrix& matrixByRow,
00245 const double* LHS,
00246 const double* coefByRow,
00247 const int* colInds,
00248 const int* rowStarts,
00249 const int* rowLengths,
00250 const CoinPackedMatrix& matrixByCol,
00251 const double* coefByCol,
00252 const int* rowInds,
00253 const int* colStarts,
00254 const int* colLengths,
00255 OsiCuts& cs ) const;
00256
00257
00258 void copyRowSelected( const int iAggregate,
00259 const int rowSelected,
00260 std::set<int>& setRowsAggregated,
00261 int* listRowsAggregated,
00262 double* xlpExtra,
00263 const char sen,
00264 const double rhs,
00265 const double lhs,
00266 const CoinPackedMatrix& matrixByRow,
00267 CoinPackedVector& rowToAggregate,
00268 double& rhsToAggregate) const;
00269
00270
00271 bool selectRowToAggregate( const OsiSolverInterface& si,
00272 const CoinPackedVector& rowAggregated,
00273 const double* colUpperBound,
00274 const double* colLowerBound,
00275 const std::set<int>& setRowsAggregated,
00276 const double* xlp, const double* coefByCol,
00277 const int* rowInds, const int* colStarts,
00278 const int* colLengths,
00279 int& rowSelected,
00280 int& colSelected ) const;
00281
00282
00283
00284 void aggregateRow( const int colSelected,
00285 CoinPackedVector& rowToAggregate, double rhs,
00286 CoinPackedVector& rowAggregated,
00287 double& rhsAggregated ) const;
00288
00289
00290 inline bool isLowerSubst(const double inf,
00291 const double aj,
00292 const double xlp,
00293 const double LB,
00294 const double UB) const;
00295
00296
00297 bool boundSubstitution( const OsiSolverInterface& si,
00298 const CoinPackedVector& rowAggregated,
00299 const double* xlp,
00300 const double* xlpExtra,
00301 const double* colUpperBound,
00302 const double* colLowerBound,
00303 CoinPackedVector& mixedKnapsack,
00304 double& rhsMixedKnapsack, double& sStar,
00305 CoinPackedVector& contVariablesInS ) const;
00306
00307
00308 bool cMirSeparation ( const OsiSolverInterface& si,
00309 const CoinPackedMatrix& matrixByRow,
00310 const CoinPackedVector& rowAggregated,
00311 const int* listRowsAggregated,
00312 const char* sense, const double* RHS,
00313 const double* coefByRow,
00314 const int* colInds, const int* rowStarts,
00315 const int* rowLengths,
00316 const double* xlp, const double sStar,
00317 const double* colUpperBound,
00318 const double* colLowerBound,
00319 const CoinPackedVector& mixedKnapsack,
00320 const double& rhsMixedKnapsack,
00321 const CoinPackedVector& contVariablesInS,
00322 OsiRowCut& flowCut ) const;
00323
00324
00325 void cMirInequality( const int numInt,
00326 const double delta,
00327 const double numeratorBeta,
00328 const int *knapsackIndices,
00329 const double* knapsackElements,
00330 const double* xlp,
00331 const double sStar,
00332 const double* colUpperBound,
00333 const std::set<int>& setC,
00334 CoinPackedVector& cMIR,
00335 double& rhscMIR,
00336 double& sCoef,
00337 double& violation) const;
00338
00339
00340 inline double functionG( const double d, const double f ) const;
00341
00342
00343 void printStats(
00344 std::ofstream & fout,
00345 const bool hasCut,
00346 const OsiSolverInterface& si,
00347 const CoinPackedVector& rowAggregated,
00348 const double& rhsAggregated, const double* xlp,
00349 const double* xlpExtra,
00350 const int* listRowsAggregated,
00351 const int* listColsSelected,
00352 const int level,
00353 const double* colUpperBound,
00354 const double* colLowerBound ) const;
00355
00356
00357 private:
00358
00359
00360
00361
00362 int MAXAGGR_;
00363
00364 bool MULTIPLY_;
00365
00366 int CRITERION_;
00367
00368 double EPSILON_;
00370 int UNDEFINED_;
00371
00372 double TOLERANCE_;
00380 int doPreproc_;
00381
00382 mutable int numRows_;
00383
00384 mutable int numCols_;
00385
00386 mutable bool doneInitPre_;
00387
00388 mutable CglMixIntRoundVUB* vubs_;
00389
00390 mutable CglMixIntRoundVLB* vlbs_;
00391
00392 mutable RowType* rowTypes_;
00393
00394 mutable int* indRows_;
00395
00396 mutable int numRowMix_;
00397
00398 mutable int* indRowMix_;
00399
00400 mutable int numRowCont_;
00401
00402 mutable int* indRowCont_;
00403
00404 mutable int numRowInt_;
00405
00406 mutable int* indRowInt_;
00407
00408
00409 mutable int numRowContVB_;
00410
00411
00412 mutable int* indRowContVB_;
00413
00414 mutable char * sense_;
00415
00416 mutable double * RHS_;
00417
00418 };
00419
00420
00421
00422
00423
00424
00425
00426 void CglMixedIntegerRoundingUnitTest(const OsiSolverInterface * siP,
00427 const std::string mpdDir);
00428
00429 #endif