Coin-All: /home/coin/SVN-release/CoinAll-1.1.0/Cgl/src/CglKnapsackCover/CglKnapsackCover.hpp Source 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 
00052 
00055 
00056   inline void setMaxInKnapsack(int value)
00057            { if (value>0) maxInKnapsack_ = value;}
00059   inline int getMaxInKnapsack() const
00060            {return maxInKnapsack_;}
00062   inline void switchOffExpensive()
00063   { expensiveCuts_=false;}
00065   inline void switchOnExpensive()
00066   { expensiveCuts_=true;}
00067 private:
00068   
00069  // Private member methods
00070 
00071 
00074 
00082   int deriveAKnapsack(
00083     const OsiSolverInterface & si, 
00084     OsiCuts & cs,
00085     CoinPackedVector & krow,
00086     bool treatAsLRow,
00087     double & b,
00088     int *  complement,
00089     double *  xstar,
00090     int rowIndex,
00091     int numberElements,
00092     const int * index,
00093     const double * element) const;
00094 
00095   int deriveAKnapsack(
00096     const OsiSolverInterface & si, 
00097     OsiCuts & cs,
00098     CoinPackedVector & krow,
00099     double & b,
00100     int *  complement,
00101     double *  xstar,
00102     int rowIndex,
00103     const CoinPackedVectorBase & matrixRow) const;
00104 
00110   int findExactMostViolatedMinCover(
00111       int nCols, 
00112       int row,
00113       CoinPackedVector & krow,
00114       double b, 
00115       double *  xstar, 
00116       CoinPackedVector & cover,
00117       CoinPackedVector & remainder) const ;
00118 
00122   int findLPMostViolatedMinCover(
00123       int nCols,
00124       int row,
00125       CoinPackedVector & krow,
00126       double & b,
00127       double * xstar, 
00128       CoinPackedVector & cover,
00129       CoinPackedVector & remainder) const;  
00130   
00132   int findGreedyCover(
00133       int row,
00134       CoinPackedVector & krow,
00135       double & b,
00136       double * xstar,
00137       CoinPackedVector & cover,
00138       CoinPackedVector & remainder
00139       ) const;
00140 
00142   int liftCoverCut(
00143      double & b,
00144      int nRowElem,
00145      CoinPackedVector & cover,
00146      CoinPackedVector & remainder,
00147      CoinPackedVector & cut ) const;
00148  
00150   int liftAndUncomplementAndAdd(
00151      double rowub,
00152      CoinPackedVector & krow,
00153      double & b,
00154      int * complement,
00155      int row,
00156      CoinPackedVector & cover,
00157      CoinPackedVector & remainder,
00158      OsiCuts & cs ) const;
00159 
00161 void seqLiftAndUncomplementAndAdd(
00162       int nCols,
00163       double * xstar, 
00164       int * complement,
00165       int row,
00166       int nRowElem,
00167       double & b,
00168       CoinPackedVector & cover,      // need not be violated
00169       CoinPackedVector & remainder,
00170       OsiCuts & cs ) const;
00171 
00173 void liftUpDownAndUncomplementAndAdd(
00174          int nCols,
00175          double * xstar, 
00176          int * complement,
00177          int row,
00178          int nRowElem,
00179          double & b,
00180 
00181          // the following 3 packed vectors partition the krow:
00182          CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation
00183                                        // and form cover with the vars atOne
00184          CoinPackedVector & atOne,     // vars have soln value of 1 in lp relaxation
00185                                        // and together with fracCover form minimal (?) cover. 
00186          CoinPackedVector & remainder,
00187          OsiCuts & cs ) const;
00188 
00190   int findPseudoJohnAndEllisCover (
00191      int row,
00192      CoinPackedVector & krow,
00193      double & b,
00194      double * xstar,                     
00195      CoinPackedVector & cover,  
00196      CoinPackedVector & remainder) const;
00197 
00199   int findJohnAndEllisCover (
00200      int row,
00201      CoinPackedVector & krow,
00202      double & b,
00203      double * xstar,                     
00204      CoinPackedVector & fracCover,  
00205      CoinPackedVector & atOnes,  
00206      CoinPackedVector & remainder) const;
00207 
00208 
00216   int exactSolveKnapsack(
00217       int n, 
00218       double c, 
00219       double const *pp, 
00220       double const *ww,
00221       double & z, 
00222       int * x) const;
00223 
00225 
00226   // Private member data
00227 
00230 
00231   double epsilon_;  
00233   double epsilon2_;
00235   double onetol_;  
00237   int maxInKnapsack_;
00240    int numRowsToCheck_;
00241    int* rowsToCheck_;
00243   bool expensiveCuts_;
00245 };
00246 
00247 //#############################################################################
00253 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00254                               const std::string mpdDir );
00255   
00256 #endif