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

- File List
- File Members

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