Cgl trunk
|
00001 // $Id$ 00002 // Copyright (C) 2002, International Business Machines 00003 // Corporation and others. All Rights Reserved. 00004 // This code is licensed under the terms of the Eclipse Public License (EPL). 00005 00006 #ifndef CglProbing_H 00007 #define CglProbing_H 00008 00009 #include <string> 00010 00011 #include "CglCutGenerator.hpp" 00016 typedef struct { 00017 //unsigned int zeroOne:1; // nonzero if affected variable is 0-1 00018 //unsigned int whenAtUB:1; // nonzero if fixing happens when this variable at 1 00019 //unsigned int affectedToUB:1; // nonzero if affected variable fixed to UB 00020 //unsigned int affected:29; // If 0-1 then 0-1 sequence, otherwise true 00021 unsigned int affected; 00022 } disaggregationAction; 00023 00025 class CglProbing : public CglCutGenerator { 00026 friend void CglProbingUnitTest(const OsiSolverInterface * siP, 00027 const std::string mpdDir ); 00028 00029 public: 00030 00031 00099 virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs, 00100 const CglTreeInfo info = CglTreeInfo()) const; 00101 int generateCutsAndModify( const OsiSolverInterface & si, OsiCuts & cs, 00102 CglTreeInfo * info); 00104 00115 int snapshot ( const OsiSolverInterface & si, 00116 char * possible=NULL, 00117 bool withObjective=true); 00119 void deleteSnapshot ( ); 00125 int createCliques( OsiSolverInterface & si, 00126 int minimumSize=2, int maximumSize=100); 00128 void deleteCliques(); 00130 00133 00134 const double * tightLower() const; 00136 const double * tightUpper() const; 00138 const char * tightenBounds() const 00139 { return tightenBounds_;} 00141 00144 00145 const double * relaxedRowLower() const; 00147 const double * relaxedRowUpper() const; 00149 00152 00153 void setMode(int mode); 00155 int getMode() const; 00157 00160 00161 void setMaxPass(int value); 00163 int getMaxPass() const; 00165 void setLogLevel(int value); 00167 int getLogLevel() const; 00169 void setMaxProbe(int value); 00171 int getMaxProbe() const; 00173 void setMaxLook(int value); 00175 int getMaxLook() const; 00177 void setMaxElements(int value); 00179 int getMaxElements() const; 00181 void setMaxPassRoot(int value); 00183 int getMaxPassRoot() const; 00185 void setMaxProbeRoot(int value); 00187 int getMaxProbeRoot() const; 00189 void setMaxLookRoot(int value); 00191 int getMaxLookRoot() const; 00193 void setMaxElementsRoot(int value); 00195 int getMaxElementsRoot() const; 00203 virtual bool mayGenerateRowCutsInTree() const; 00205 00208 00209 inline int numberThisTime() const 00210 { return numberThisTime_;} 00212 inline const int * lookedAt() const 00213 { return lookedAt_;} 00215 00218 00219 00220 void setRowCuts(int type); 00222 int rowCuts() const; 00224 00232 void setUsingObjective(int yesNo); 00234 int getUsingObjective() const; 00236 00239 00240 void tightenThese(const OsiSolverInterface & solver, int number, const int * which); 00242 00245 00246 CglProbing (); 00247 00249 CglProbing ( 00250 const CglProbing &); 00251 00253 virtual CglCutGenerator * clone() const; 00254 00256 CglProbing & 00257 operator=( 00258 const CglProbing& rhs); 00259 00261 virtual 00262 ~CglProbing (); 00263 00265 virtual void refreshSolver(OsiSolverInterface * solver); 00267 virtual std::string generateCpp( FILE * fp); 00269 00270 private: 00271 00272 // Private member methods 00275 00276 int probe( const OsiSolverInterface & si, 00277 const OsiRowCutDebugger * debugger, 00278 OsiCuts & cs, 00279 double * colLower, double * colUpper, CoinPackedMatrix *rowCopy, 00280 CoinPackedMatrix *columnCopy,const CoinBigIndex * rowStartPos, 00281 const int * realRow, const double * rowLower, const double * rowUpper, 00282 const char * intVar, double * minR, double * maxR, int * markR, 00283 CglTreeInfo * info) const; 00285 int probeCliques( const OsiSolverInterface & si, 00286 const OsiRowCutDebugger * debugger, 00287 OsiCuts & cs, 00288 double * colLower, double * colUpper, CoinPackedMatrix *rowCopy, 00289 CoinPackedMatrix *columnCopy, const int * realRow, 00290 double * rowLower, double * rowUpper, 00291 char * intVar, double * minR, double * maxR, int * markR, 00292 CglTreeInfo * info) const; 00294 int probeSlacks( const OsiSolverInterface & si, 00295 const OsiRowCutDebugger * debugger, 00296 OsiCuts & cs, 00297 double * colLower, double * colUpper, CoinPackedMatrix *rowCopy, 00298 CoinPackedMatrix *columnCopy, 00299 double * rowLower, double * rowUpper, 00300 char * intVar, double * minR, double * maxR,int * markR, 00301 CglTreeInfo * info) const; 00304 int gutsOfGenerateCuts( const OsiSolverInterface & si, 00305 OsiCuts & cs, 00306 double * rowLower, double * rowUpper, 00307 double * colLower, double * colUpper, 00308 CglTreeInfo * info) const; 00310 void setupRowCliqueInformation(const OsiSolverInterface & si); 00313 int tighten(double *colLower, double * colUpper, 00314 const int *column, const double *rowElements, 00315 const CoinBigIndex *rowStart,const CoinBigIndex * rowStartPos, 00316 const int * rowLength, 00317 double *rowLower, double *rowUpper, 00318 int nRows,int nCols,char * intVar,int maxpass, 00319 double tolerance) const; 00321 void tighten2(double *colLower, double * colUpper, 00322 const int *column, const double *rowElements, 00323 const CoinBigIndex *rowStart, 00324 const int * rowLength, 00325 double *rowLower, double *rowUpper, 00326 double * minR, double * maxR, int * markR, 00327 int nRows) const; 00329 00330 // Private member data 00331 00332 struct disaggregation_struct_tag ; 00333 friend struct CglProbing::disaggregation_struct_tag ; 00334 00337 00338 CoinPackedMatrix * rowCopy_; 00340 CoinPackedMatrix * columnCopy_; 00342 double * rowLower_; 00344 double * rowUpper_; 00346 mutable double * colLower_; 00348 mutable double * colUpper_; 00350 mutable int numberRows_; 00352 mutable int numberColumns_; 00354 double primalTolerance_; 00358 int mode_; 00363 mutable int rowCuts_; 00365 int maxPass_; 00367 int logLevel_; 00369 int maxProbe_; 00371 int maxStack_; 00373 int maxElements_; 00375 int maxPassRoot_; 00377 int maxProbeRoot_; 00379 int maxStackRoot_; 00381 int maxElementsRoot_; 00383 int usingObjective_; 00385 int numberIntegers_; 00387 int number01Integers_; 00389 mutable int numberThisTime_; 00391 mutable int totalTimesCalled_; 00393 mutable int * lookedAt_; 00395 typedef struct disaggregation_struct_tag { 00396 int sequence; // integer variable 00397 // index will be NULL if no probing done yet 00398 int length; // length of newValue 00399 disaggregationAction * index; // columns whose bounds will be changed 00400 } disaggregation; 00401 disaggregation * cutVector_; 00404 int numberCliques_; 00406 typedef struct { 00407 unsigned int equality:1; // nonzero if clique is == 00408 } cliqueType; 00409 cliqueType * cliqueType_; 00411 int * cliqueStart_; 00413 cliqueEntry * cliqueEntry_; 00416 int * oneFixStart_; 00419 int * zeroFixStart_; 00421 int * endFixStart_; 00423 int * whichClique_; 00428 cliqueEntry * cliqueRow_; 00430 int * cliqueRowStart_; 00432 char * tightenBounds_; 00434 }; 00435 inline int affectedInDisaggregation(const disaggregationAction & dis) 00436 { return dis.affected&0x1fffffff;} 00437 inline void setAffectedInDisaggregation(disaggregationAction & dis, 00438 int affected) 00439 { dis.affected = affected|(dis.affected&0xe0000000);} 00440 #ifdef NDEBUG 00441 inline bool zeroOneInDisaggregation(const disaggregationAction & ) 00442 { return true;} 00443 #else 00444 inline bool zeroOneInDisaggregation(const disaggregationAction & dis) 00445 //{ return (dis.affected&0x80000000)!=0;} 00446 { assert ((dis.affected&0x80000000)!=0); return true;} 00447 #endif 00448 inline void setZeroOneInDisaggregation(disaggregationAction & dis,bool zeroOne) 00449 { dis.affected = (zeroOne ? 0x80000000 : 0)|(dis.affected&0x7fffffff);} 00450 inline bool whenAtUBInDisaggregation(const disaggregationAction & dis) 00451 { return (dis.affected&0x40000000)!=0;} 00452 inline void setWhenAtUBInDisaggregation(disaggregationAction & dis,bool whenAtUB) 00453 { dis.affected = (whenAtUB ? 0x40000000 : 0)|(dis.affected&0xbfffffff);} 00454 inline bool affectedToUBInDisaggregation(const disaggregationAction & dis) 00455 { return (dis.affected&0x20000000)!=0;} 00456 inline void setAffectedToUBInDisaggregation(disaggregationAction & dis,bool affectedToUB) 00457 { dis.affected = (affectedToUB ? 0x20000000 : 0)|(dis.affected&0xdfffffff);} 00458 00459 //############################################################################# 00465 void CglProbingUnitTest(const OsiSolverInterface * siP, 00466 const std::string mpdDir ); 00468 class CglImplication : public CglCutGenerator { 00469 00470 public: 00471 00477 virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs, 00478 const CglTreeInfo info = CglTreeInfo()) const; 00480 00483 00484 CglImplication (); 00485 00487 CglImplication (CglTreeProbingInfo * info); 00488 00490 CglImplication ( 00491 const CglImplication &); 00492 00494 virtual CglCutGenerator * clone() const; 00495 00497 CglImplication & 00498 operator=( 00499 const CglImplication& rhs); 00500 00502 virtual 00503 ~CglImplication (); 00505 virtual std::string generateCpp( FILE * fp); 00507 00509 00510 inline void setProbingInfo(CglTreeProbingInfo * info) 00511 { probingInfo_=info;} 00513 00514 private: 00517 00518 CglTreeProbingInfo * probingInfo_; 00520 }; 00521 #endif