Cgl: CglKnapsackCover.hpp Source 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) const;
00026 
00029 
00030   CglKnapsackCover ();
00031  
00033   CglKnapsackCover (
00034     const CglKnapsackCover &);
00035 
00037   CglKnapsackCover &
00038     operator=(
00039     const CglKnapsackCover& rhs);
00040   
00042   virtual
00043     ~CglKnapsackCover ();
00045 
00046 
00049 
00050   inline void setMaxInKnapsack(int value)
00051            { if (value>0) maxInKnapsack_ = value;};
00053   inline int getMaxInKnapsack() const
00054            {return maxInKnapsack_;};
00055 private:
00056   
00057  // Private member methods
00058 
00059 
00062 
00070   int deriveAKnapsack(
00071     const OsiSolverInterface & si, 
00072     OsiCuts & cs,
00073     CoinPackedVector & krow,
00074     bool treatAsLRow,
00075     double & b,
00076     int *  complement,
00077     double *  xstar,
00078     int rowIndex,
00079     int numberElements,
00080     const int * index,
00081     const double * element) const;
00082 
00083   int deriveAKnapsack(
00084     const OsiSolverInterface & si, 
00085     OsiCuts & cs,
00086     CoinPackedVector & krow,
00087     double & b,
00088     int *  complement,
00089     double *  xstar,
00090     int rowIndex,
00091     const CoinPackedVectorBase & matrixRow) const;
00092 
00098   int findExactMostViolatedMinCover(
00099       int nCols, 
00100       int row,
00101       CoinPackedVector & krow,
00102       double b, 
00103       double *  xstar, 
00104       CoinPackedVector & cover,
00105       CoinPackedVector & remainder) const ;
00106 
00110   int findLPMostViolatedMinCover(
00111       int nCols,
00112       int row,
00113       CoinPackedVector & krow,
00114       double & b,
00115       double * xstar, 
00116       CoinPackedVector & cover,
00117       CoinPackedVector & remainder) const;  
00118   
00120   int findGreedyCover(
00121       int row,
00122       CoinPackedVector & krow,
00123       double & b,
00124       double * xstar,
00125       CoinPackedVector & cover,
00126       CoinPackedVector & remainder
00127       ) const;
00128 
00130   int liftCoverCut(
00131      double & b,
00132      int nRowElem,
00133      CoinPackedVector & cover,
00134      CoinPackedVector & remainder,
00135      CoinPackedVector & cut ) const;
00136  
00138   int liftAndUncomplementAndAdd(
00139      double rowub,
00140      CoinPackedVector & krow,
00141      double & b,
00142      int * complement,
00143      int row,
00144      CoinPackedVector & cover,
00145      CoinPackedVector & remainder,
00146      OsiCuts & cs) const;
00147 
00149 void seqLiftAndUncomplementAndAdd(
00150       int nCols,
00151       double * xstar, 
00152       int * complement,
00153       int row,
00154       int nRowElem,
00155       double & b,
00156       CoinPackedVector & cover,      // need not be violated
00157       CoinPackedVector & remainder,
00158       OsiCuts & cs) const;
00159 
00161 void liftUpDownAndUncomplementAndAdd(
00162          int nCols,
00163          double * xstar, 
00164          int * complement,
00165          int row,
00166          int nRowElem,
00167          double & b,
00168 
00169          // the following 3 packed vectors partition the krow:
00170          CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation
00171                                        // and form cover with the vars atOne
00172          CoinPackedVector & atOne,     // vars have soln value of 1 in lp relaxation
00173                                        // and together with fracCover form minimal (?) cover. 
00174          CoinPackedVector & remainder,
00175          OsiCuts & cs ) const;
00176 
00178   int findPseudoJohnAndEllisCover (
00179      int row,
00180      CoinPackedVector & krow,
00181      double & b,
00182      double * xstar,                     
00183      CoinPackedVector & cover,  
00184      CoinPackedVector & remainder) const;
00185 
00187   int findJohnAndEllisCover (
00188      int row,
00189      CoinPackedVector & krow,
00190      double & b,
00191      double * xstar,                     
00192      CoinPackedVector & fracCover,  
00193      CoinPackedVector & atOnes,  
00194      CoinPackedVector & remainder) const;
00195 
00196 
00204   int exactSolveKnapsack(
00205       int n, 
00206       double c, 
00207       double const *pp, 
00208       double const *ww,
00209       double & z, 
00210       int * x) const;
00211 
00213 
00214   // Private member data
00215 
00218 
00219   double epsilon_;  
00221   double epsilon2_;
00223   double onetol_;  
00225   int maxInKnapsack_;
00228    int numRowsToCheck_;
00229    int* rowsToCheck_;
00231 };
00232 
00233 //#############################################################################
00239 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00240                               const std::string mpdDir );
00241   
00242 #endif