coin-Cgl
/tmp/buildd/coinor-cgl-0.55.0/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 #include "CglTreeInfo.hpp"
00010 
00012 class CglKnapsackCover : public CglCutGenerator {
00013    friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00014                                         const std::string mpdDir );
00015 
00016 public:
00018    void setTestedRowIndices(int num, const int* ind);
00019 
00025   virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
00026                             const CglTreeInfo info = CglTreeInfo()) const;
00028 
00031 
00032   CglKnapsackCover ();
00033  
00035   CglKnapsackCover (
00036     const CglKnapsackCover &);
00037 
00039   virtual CglCutGenerator * clone() const;
00040 
00042   CglKnapsackCover &
00043     operator=(
00044     const CglKnapsackCover& rhs);
00045   
00047   virtual
00048     ~CglKnapsackCover ();
00050   virtual std::string generateCpp( FILE * fp);
00052   virtual void refreshSolver(OsiSolverInterface * solver);
00054 
00055 
00058 
00059   inline void setMaxInKnapsack(int value)
00060            { if (value>0) maxInKnapsack_ = value;}
00062   inline int getMaxInKnapsack() const
00063            {return maxInKnapsack_;}
00065   inline void switchOffExpensive()
00066   { expensiveCuts_=false;}
00068   inline void switchOnExpensive()
00069   { expensiveCuts_=true;}
00070 private:
00071   
00072  // Private member methods
00073 
00074 
00077 
00085   int deriveAKnapsack(
00086     const OsiSolverInterface & si, 
00087     OsiCuts & cs,
00088     CoinPackedVector & krow,
00089     bool treatAsLRow,
00090     double & b,
00091     int *  complement,
00092     double *  xstar,
00093     int rowIndex,
00094     int numberElements,
00095     const int * index,
00096     const double * element) const;
00097 
00098   int deriveAKnapsack(
00099     const OsiSolverInterface & si, 
00100     OsiCuts & cs,
00101     CoinPackedVector & krow,
00102     double & b,
00103     int *  complement,
00104     double *  xstar,
00105     int rowIndex,
00106     const CoinPackedVectorBase & matrixRow) const;
00107 
00113   int findExactMostViolatedMinCover(
00114       int nCols, 
00115       int row,
00116       CoinPackedVector & krow,
00117       double b, 
00118       double *  xstar, 
00119       CoinPackedVector & cover,
00120       CoinPackedVector & remainder) const ;
00121 
00125   int findLPMostViolatedMinCover(
00126       int nCols,
00127       int row,
00128       CoinPackedVector & krow,
00129       double & b,
00130       double * xstar, 
00131       CoinPackedVector & cover,
00132       CoinPackedVector & remainder) const;  
00133   
00135   int findGreedyCover(
00136       int row,
00137       CoinPackedVector & krow,
00138       double & b,
00139       double * xstar,
00140       CoinPackedVector & cover,
00141       CoinPackedVector & remainder
00142       ) const;
00143 
00145   int liftCoverCut(
00146      double & b,
00147      int nRowElem,
00148      CoinPackedVector & cover,
00149      CoinPackedVector & remainder,
00150      CoinPackedVector & cut ) const;
00151  
00153   int liftAndUncomplementAndAdd(
00154      double rowub,
00155      CoinPackedVector & krow,
00156      double & b,
00157      int * complement,
00158      int row,
00159      CoinPackedVector & cover,
00160      CoinPackedVector & remainder,
00161      OsiCuts & cs ) const;
00162 
00164 void seqLiftAndUncomplementAndAdd(
00165       int nCols,
00166       double * xstar, 
00167       int * complement,
00168       int row,
00169       int nRowElem,
00170       double & b,
00171       CoinPackedVector & cover,      // need not be violated
00172       CoinPackedVector & remainder,
00173       OsiCuts & cs ) const;
00174 
00176 void liftUpDownAndUncomplementAndAdd(
00177          int nCols,
00178          double * xstar, 
00179          int * complement,
00180          int row,
00181          int nRowElem,
00182          double & b,
00183 
00184          // the following 3 packed vectors partition the krow:
00185          CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation
00186                                        // and form cover with the vars atOne
00187          CoinPackedVector & atOne,     // vars have soln value of 1 in lp relaxation
00188                                        // and together with fracCover form minimal (?) cover. 
00189          CoinPackedVector & remainder,
00190          OsiCuts & cs ) const;
00191 
00193   int findPseudoJohnAndEllisCover (
00194      int row,
00195      CoinPackedVector & krow,
00196      double & b,
00197      double * xstar,                     
00198      CoinPackedVector & cover,  
00199      CoinPackedVector & remainder) const;
00200 
00202   int findJohnAndEllisCover (
00203      int row,
00204      CoinPackedVector & krow,
00205      double & b,
00206      double * xstar,                     
00207      CoinPackedVector & fracCover,  
00208      CoinPackedVector & atOnes,  
00209      CoinPackedVector & remainder) const;
00210 
00211 
00219   int exactSolveKnapsack(
00220       int n, 
00221       double c, 
00222       double const *pp, 
00223       double const *ww,
00224       double & z, 
00225       int * x) const;
00226 
00232   int createCliques( OsiSolverInterface & si, 
00233                     int minimumSize=2, int maximumSize=100, bool extendCliques=false);
00235   void deleteCliques();
00237 
00238   // Private member data
00239 
00242 
00243   double epsilon_;  
00245   double epsilon2_;
00247   double onetol_;  
00249   int maxInKnapsack_;
00252    int numRowsToCheck_;
00253    int* rowsToCheck_;
00255   bool expensiveCuts_;
00258   mutable const OsiSolverInterface * solver_;
00259   mutable int whichRow_;
00260   mutable int * complement_;
00261   mutable double * elements_;
00263   int numberCliques_;
00265   typedef struct {
00266     unsigned int equality:1; //  nonzero if clique is ==
00267   } cliqueType;
00268   cliqueType * cliqueType_;
00270   int * cliqueStart_;
00272   cliqueEntry * cliqueEntry_;
00275   int * oneFixStart_;
00278   int * zeroFixStart_;
00280   int * endFixStart_;
00282   int * whichClique_;
00284   int numberColumns_;
00289   //cliqueEntry * cliqueRow_;
00291   //int * cliqueRowStart_;
00293 };
00294 
00295 //#############################################################################
00301 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00302                               const std::string mpdDir );
00303   
00304 #endif