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

- File List
- File Members

# /home/coin/svn-release/Blis-0.93.2/Cgl/src/CglKnapsackCover/CglKnapsackCover.hpp

Go to the documentation of this file.

    00001 // $Id: CglKnapsackCover.hpp 936 2011-01-04 23:21:32Z lou $
    00002 // Copyright (C) 2000, International Business Machines
    00003 // Corporation and others.  All Rights Reserved.
    00004 // This code is licensed under the terms of the Eclipse Public License (EPL).
    00005
    00006 #ifndef CglKnapsackCover_H
    00007 #define CglKnapsackCover_H
    00008
    00009 #include <string>
    00010
    00011 #include "CglCutGenerator.hpp"
    00012 #include "CglTreeInfo.hpp"
    00013
    00015 class CglKnapsackCover : public CglCutGenerator {
    00016    friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
    00017                                         const std::string mpdDir );
    00018
    00019 public:
    00021    void setTestedRowIndices(int num, const int* ind);
    00022
    00028   virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
    00029                             const CglTreeInfo info = CglTreeInfo()) const;
    00031
    00034
    00035   CglKnapsackCover ();
    00036
    00038   CglKnapsackCover (
    00039     const CglKnapsackCover &);
    00040
    00042   virtual CglCutGenerator * clone() const;
    00043
    00045   CglKnapsackCover &
    00046     operator=(
    00047     const CglKnapsackCover& rhs);
    00048
    00050   virtual
    00051     ~CglKnapsackCover ();
    00053   virtual std::string generateCpp( FILE * fp);
    00055   virtual void refreshSolver(OsiSolverInterface * solver);
    00057
    00058
    00061
    00062   inline void setMaxInKnapsack(int value)
    00063            { if (value>0) maxInKnapsack_ = value;}
    00065   inline int getMaxInKnapsack() const
    00066            {return maxInKnapsack_;}
    00068   inline void switchOffExpensive()
    00069   { expensiveCuts_=false;}
    00071   inline void switchOnExpensive()
    00072   { expensiveCuts_=true;}
    00073 private:
    00074
    00075  // Private member methods
    00076
    00077
    00080
    00088   int deriveAKnapsack(
    00089     const OsiSolverInterface & si,
    00090     OsiCuts & cs,
    00091     CoinPackedVector & krow,
    00092     bool treatAsLRow,
    00093     double & b,
    00094     int *  complement,
    00095     double *  xstar,
    00096     int rowIndex,
    00097     int numberElements,
    00098     const int * index,
    00099     const double * element) const;
    00100
    00101   int deriveAKnapsack(
    00102     const OsiSolverInterface & si,
    00103     OsiCuts & cs,
    00104     CoinPackedVector & krow,
    00105     double & b,
    00106     int *  complement,
    00107     double *  xstar,
    00108     int rowIndex,
    00109     const CoinPackedVectorBase & matrixRow) const;
    00110
    00116   int findExactMostViolatedMinCover(
    00117       int nCols,
    00118       int row,
    00119       CoinPackedVector & krow,
    00120       double b,
    00121       double *  xstar,
    00122       CoinPackedVector & cover,
    00123       CoinPackedVector & remainder) const ;
    00124
    00128   int findLPMostViolatedMinCover(
    00129       int nCols,
    00130       int row,
    00131       CoinPackedVector & krow,
    00132       double & b,
    00133       double * xstar,
    00134       CoinPackedVector & cover,
    00135       CoinPackedVector & remainder) const;
    00136
    00138   int findGreedyCover(
    00139       int row,
    00140       CoinPackedVector & krow,
    00141       double & b,
    00142       double * xstar,
    00143       CoinPackedVector & cover,
    00144       CoinPackedVector & remainder
    00145       ) const;
    00146
    00148   int liftCoverCut(
    00149      double & b,
    00150      int nRowElem,
    00151      CoinPackedVector & cover,
    00152      CoinPackedVector & remainder,
    00153      CoinPackedVector & cut ) const;
    00154
    00156   int liftAndUncomplementAndAdd(
    00157      double rowub,
    00158      CoinPackedVector & krow,
    00159      double & b,
    00160      int * complement,
    00161      int row,
    00162      CoinPackedVector & cover,
    00163      CoinPackedVector & remainder,
    00164      OsiCuts & cs ) const;
    00165
    00167 void seqLiftAndUncomplementAndAdd(
    00168       int nCols,
    00169       double * xstar,
    00170       int * complement,
    00171       int row,
    00172       int nRowElem,
    00173       double & b,
    00174       CoinPackedVector & cover,      // need not be violated
    00175       CoinPackedVector & remainder,
    00176       OsiCuts & cs ) const;
    00177
    00179 void liftUpDownAndUncomplementAndAdd(
    00180          int nCols,
    00181          double * xstar,
    00182          int * complement,
    00183          int row,
    00184          int nRowElem,
    00185          double & b,
    00186
    00187          // the following 3 packed vectors partition the krow:
    00188          CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation
    00189                                        // and form cover with the vars atOne
    00190          CoinPackedVector & atOne,     // vars have soln value of 1 in lp relaxation
    00191                                        // and together with fracCover form minimal (?) cover.
    00192          CoinPackedVector & remainder,
    00193          OsiCuts & cs ) const;
    00194
    00196   int findPseudoJohnAndEllisCover (
    00197      int row,
    00198      CoinPackedVector & krow,
    00199      double & b,
    00200      double * xstar,
    00201      CoinPackedVector & cover,
    00202      CoinPackedVector & remainder) const;
    00203
    00205   int findJohnAndEllisCover (
    00206      int row,
    00207      CoinPackedVector & krow,
    00208      double & b,
    00209      double * xstar,
    00210      CoinPackedVector & fracCover,
    00211      CoinPackedVector & atOnes,
    00212      CoinPackedVector & remainder) const;
    00213
    00214
    00222   int exactSolveKnapsack(
    00223       int n,
    00224       double c,
    00225       double const *pp,
    00226       double const *ww,
    00227       double & z,
    00228       int * x) const;
    00229
    00235   int createCliques( OsiSolverInterface & si,
    00236                     int minimumSize=2, int maximumSize=100, bool extendCliques=false);
    00238   void deleteCliques();
    00240
    00241   // Private member data
    00242
    00245
    00246   double epsilon_;
    00248   double epsilon2_;
    00250   double onetol_;
    00252   int maxInKnapsack_;
    00255    int numRowsToCheck_;
    00256    int* rowsToCheck_;
    00258   bool expensiveCuts_;
    00261   mutable const OsiSolverInterface * solver_;
    00262   mutable int whichRow_;
    00263   mutable int * complement_;
    00264   mutable double * elements_;
    00266   int numberCliques_;
    00268   typedef struct {
    00269     unsigned int equality:1; //  nonzero if clique is ==
    00270   } cliqueType;
    00271   cliqueType * cliqueType_;
    00273   int * cliqueStart_;
    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