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

- File List
- File Members

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