- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Blis-0.91.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
    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