/home/coin/SVN-release/Bcps-0.91.2/Cgl/src/CglKnapsackCover/CglKnapsackCover.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef CglKnapsackCover_H
00004 #define CglKnapsackCover_H
00005 
00006 #include <string>
00007 
00008 #include "CglCutGenerator.hpp"
00009 
00011 class CglKnapsackCover : public CglCutGenerator {
00012    friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00013                                         const std::string mpdDir );
00014 
00015 public:
00017    void setTestedRowIndices(int num, const int* ind);
00018 
00024   virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
00025                             const CglTreeInfo info = CglTreeInfo()) const;
00027 
00030 
00031   CglKnapsackCover ();
00032  
00034   CglKnapsackCover (
00035     const CglKnapsackCover &);
00036 
00038   virtual CglCutGenerator * clone() const;
00039 
00041   CglKnapsackCover &
00042     operator=(
00043     const CglKnapsackCover& rhs);
00044   
00046   virtual
00047     ~CglKnapsackCover ();
00049   virtual std::string generateCpp( FILE * fp);
00051   virtual void refreshSolver(OsiSolverInterface * solver);
00053 
00054 
00057 
00058   inline void setMaxInKnapsack(int value)
00059            { if (value>0) maxInKnapsack_ = value;}
00061   inline int getMaxInKnapsack() const
00062            {return maxInKnapsack_;}
00064   inline void switchOffExpensive()
00065   { expensiveCuts_=false;}
00067   inline void switchOnExpensive()
00068   { expensiveCuts_=true;}
00069 private:
00070   
00071  // Private member methods
00072 
00073 
00076 
00084   int deriveAKnapsack(
00085     const OsiSolverInterface & si, 
00086     OsiCuts & cs,
00087     CoinPackedVector & krow,
00088     bool treatAsLRow,
00089     double & b,
00090     int *  complement,
00091     double *  xstar,
00092     int rowIndex,
00093     int numberElements,
00094     const int * index,
00095     const double * element) const;
00096 
00097   int deriveAKnapsack(
00098     const OsiSolverInterface & si, 
00099     OsiCuts & cs,
00100     CoinPackedVector & krow,
00101     double & b,
00102     int *  complement,
00103     double *  xstar,
00104     int rowIndex,
00105     const CoinPackedVectorBase & matrixRow) const;
00106 
00112   int findExactMostViolatedMinCover(
00113       int nCols, 
00114       int row,
00115       CoinPackedVector & krow,
00116       double b, 
00117       double *  xstar, 
00118       CoinPackedVector & cover,
00119       CoinPackedVector & remainder) const ;
00120 
00124   int findLPMostViolatedMinCover(
00125       int nCols,
00126       int row,
00127       CoinPackedVector & krow,
00128       double & b,
00129       double * xstar, 
00130       CoinPackedVector & cover,
00131       CoinPackedVector & remainder) const;  
00132   
00134   int findGreedyCover(
00135       int row,
00136       CoinPackedVector & krow,
00137       double & b,
00138       double * xstar,
00139       CoinPackedVector & cover,
00140       CoinPackedVector & remainder
00141       ) const;
00142 
00144   int liftCoverCut(
00145      double & b,
00146      int nRowElem,
00147      CoinPackedVector & cover,
00148      CoinPackedVector & remainder,
00149      CoinPackedVector & cut ) const;
00150  
00152   int liftAndUncomplementAndAdd(
00153      double rowub,
00154      CoinPackedVector & krow,
00155      double & b,
00156      int * complement,
00157      int row,
00158      CoinPackedVector & cover,
00159      CoinPackedVector & remainder,
00160      OsiCuts & cs ) const;
00161 
00163 void seqLiftAndUncomplementAndAdd(
00164       int nCols,
00165       double * xstar, 
00166       int * complement,
00167       int row,
00168       int nRowElem,
00169       double & b,
00170       CoinPackedVector & cover,      // need not be violated
00171       CoinPackedVector & remainder,
00172       OsiCuts & cs ) const;
00173 
00175 void liftUpDownAndUncomplementAndAdd(
00176          int nCols,
00177          double * xstar, 
00178          int * complement,
00179          int row,
00180          int nRowElem,
00181          double & b,
00182 
00183          // the following 3 packed vectors partition the krow:
00184          CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation
00185                                        // and form cover with the vars atOne
00186          CoinPackedVector & atOne,     // vars have soln value of 1 in lp relaxation
00187                                        // and together with fracCover form minimal (?) cover. 
00188          CoinPackedVector & remainder,
00189          OsiCuts & cs ) const;
00190 
00192   int findPseudoJohnAndEllisCover (
00193      int row,
00194      CoinPackedVector & krow,
00195      double & b,
00196      double * xstar,                     
00197      CoinPackedVector & cover,  
00198      CoinPackedVector & remainder) const;
00199 
00201   int findJohnAndEllisCover (
00202      int row,
00203      CoinPackedVector & krow,
00204      double & b,
00205      double * xstar,                     
00206      CoinPackedVector & fracCover,  
00207      CoinPackedVector & atOnes,  
00208      CoinPackedVector & remainder) const;
00209 
00210 
00218   int exactSolveKnapsack(
00219       int n, 
00220       double c, 
00221       double const *pp, 
00222       double const *ww,
00223       double & z, 
00224       int * x) const;
00225 
00231   int createCliques( OsiSolverInterface & si, 
00232                     int minimumSize=2, int maximumSize=100, bool extendCliques=false);
00234   void deleteCliques();
00236 
00237   // Private member data
00238 
00241 
00242   double epsilon_;  
00244   double epsilon2_;
00246   double onetol_;  
00248   int maxInKnapsack_;
00251    int numRowsToCheck_;
00252    int* rowsToCheck_;
00254   bool expensiveCuts_;
00257   mutable const OsiSolverInterface * solver_;
00258   mutable int whichRow_;
00259   mutable int * complement_;
00260   mutable double * elements_;
00262   int numberCliques_;
00264   typedef struct {
00265     unsigned int equality:1; //  nonzero if clique is ==
00266   } cliqueType;
00267   cliqueType * cliqueType_;
00269   int * cliqueStart_;
00271   typedef struct {
00272     unsigned int oneFixes:1; //  nonzero if variable to 1 fixes all
00273     unsigned int sequence:31; //  variable (in matrix) (but also see cliqueRow_)
00274   } cliqueEntry;
00275   cliqueEntry * cliqueEntry_;
00278   int * oneFixStart_;
00281   int * zeroFixStart_;
00283   int * endFixStart_;
00285   int * whichClique_;
00287   int numberColumns_;
00292   //cliqueEntry * cliqueRow_;
00294   //int * cliqueRowStart_;
00296 };
00297 
00298 //#############################################################################
00304 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00305                               const std::string mpdDir );
00306   
00307 #endif

Generated on Thu Feb 4 03:02:04 2010 by  doxygen 1.4.7