Cgl trunk
CglKnapsackCover.hpp
Go to the documentation of this file.
00001 // $Id$
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines