Cgl  trunk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
CglProbing.hpp
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines