/home/coin/SVN-release/Bcp-1.2.1/Applications/Csp/include/CSP.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2005, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef CSP_H
00004 #define CSP_H
00005 
00006 #include <iostream>
00007 #include <vector>
00008 #include <map>
00009 #include <string>
00010 #include <algorithm>
00011 #include <numeric>
00012 
00013 #include <CoinHelperFunctions.hpp>
00014 
00015 #include "BCP_buffer.hpp"
00016 
00017 class PATTERN;
00018 class CSPROBLEM;
00019 
00020 struct DELETEOBJECT {
00021 template<typename T>
00022   void operator() (const T*& ptr){ delete ptr; ptr = NULL; }
00023 template<typename T>
00024   void operator() (T*& ptr){ delete ptr; ptr = NULL; }
00025 };
00026 
00027 class CSP_packedVector {
00028 
00029 private:
00030   int size_;
00031   int * indices_;
00032   double * elements_;
00033 
00034 
00035 public: 
00036  // constructor: we ALWAYS copy
00037   CSP_packedVector(const int size,
00038                    const int* indices, 
00039                    const double* elements){
00040     size_=size;
00041     indices_=new int[size_];
00042     elements_=new double[size_];
00043     CoinDisjointCopyN(indices, size_, indices_);
00044     CoinDisjointCopyN(elements, size_, elements_);
00045   }
00046 
00047   CSP_packedVector():size_(0), indices_(0), elements_(0){}
00048 
00049   // constructor from a buffer
00050   
00051   CSP_packedVector(BCP_buffer & buf){
00052     buf.unpack(indices_, size_);
00053     buf.unpack(elements_, size_);
00054   }
00055     
00056   void  pack(BCP_buffer& buf) const {
00057     buf.pack(indices_, size_);
00058     buf.pack(elements_, size_);
00059   }
00060 
00061   void  unpack(BCP_buffer& buf){
00062     delete [] indices_;
00063     delete [] elements_;
00064     buf.unpack(indices_, size_);
00065     buf.unpack(elements_, size_);
00066   }
00067 
00068 
00069   const int* getIndices()const {
00070     return indices_;
00071   }
00072 
00073   const double* getElements() const {
00074     return elements_;
00075   }
00076 
00077   const int getSize() const {
00078     return size_;
00079   }
00080 
00081   // disable copy constructor
00082   CSP_packedVector(const CSP_packedVector& pv):size_(pv.size_){
00083     indices_=new int[size_];
00084     elements_=new double[size_];
00085     CoinDisjointCopyN(pv.indices_, size_, indices_);
00086     CoinDisjointCopyN(pv.elements_, size_, elements_);
00087   }
00088     
00089     
00090 
00091 
00092 
00093 private:
00094 
00095 
00096   // disable assignmnet operator
00097   CSP_packedVector& operator=(const CSP_packedVector& pv);
00098 };
00099   
00100     
00101 //#############################################################################
00102 // Class CSPROBLEM contains all the data 
00103 //       for an instance of the cutting stock problem
00104 
00105 class CSPROBLEM {
00106 
00107 public:
00108 
00109   inline int getL() const { return l_; }
00110   inline const int* getDemand() const { return demand_; }
00111   inline const int* getW() const { return w_; }
00112   inline int getM() const { return m_; }
00113   inline int getS() const { return s_; }
00114 
00115    inline bool doesCombineExclusionConstraints() const {
00116       return combineExclusionConstraints;
00117    }
00118    inline bool doesAddKnapsackMirConstraints() const {
00119       return addKnapsackMirConstraints;
00120    }
00121    inline bool doesAddKnifeMirConstraints() const {
00122       return addKnifeMirConstraints;
00123    }
00124 
00125    inline void setCombineExclusionConstraints(char yesno) {
00126       combineExclusionConstraints = yesno;
00127    }
00128    inline void setAddKnapsackMirConstraints(char yesno) {
00129       addKnapsackMirConstraints = yesno;
00130    }
00131    inline void setAddKnifeMirConstraints(char yesno) {
00132       addKnifeMirConstraints = yesno;
00133    }
00134   
00135   CSPROBLEM();
00136   CSPROBLEM(std::istream &inputStream);
00137   ~CSPROBLEM(){}
00138   
00139   void pack(BCP_buffer& buf) const {
00140     buf.pack(l_);
00141     buf.pack(demand_, m_);
00142     buf.pack(w_, m_);
00143     buf.pack(s_);
00144     buf.pack(combineExclusionConstraints);
00145     buf.pack(addKnapsackMirConstraints);
00146     buf.pack(addKnifeMirConstraints);
00147   }
00148 
00149   void unpack(BCP_buffer& buf){
00150     buf.unpack(l_);
00151     buf.unpack(demand_, m_);
00152     buf.unpack(w_, m_);
00153     buf.unpack(s_);
00154     buf.unpack(combineExclusionConstraints);
00155     buf.unpack(addKnapsackMirConstraints);
00156     buf.unpack(addKnifeMirConstraints);
00157   }
00158 
00159 private:
00160   int l_ ;            // stock roll length
00161   int* demand_;       // quanty of demanded widths
00162   int* w_;            // demanded widths
00163   int m_;             // number of demanded widths
00164   int s_;             // number of knives ("stilletto")
00165   double start_time_;
00166 
00167    char combineExclusionConstraints;
00168    char addKnapsackMirConstraints;
00169    char addKnifeMirConstraints;
00170  
00171  // upper and lower bounds on patterns (cols)
00172  // is handled by BCP variable classes
00173 };
00174 
00175 //#############################################################################
00176 
00177 class PATTERN {
00178 private:
00179   // One single, shared, CSPROBLEM for all instances of PATTERN
00180   const static CSPROBLEM* csproblem_;
00181 
00182    // The cost of the pattern, e.g. 1 for our flavor of the CSP.
00183   double cost_;
00184 
00185   // We may want to store ubs in the future
00186   // but right now, we'll always calculate
00187 
00188   // Need to know how many of each width to cut for this pattern
00189   // the integer vector  A^j*=(a^j*_1,....a^j*_m)
00190   CSP_packedVector widths_;   
00191 
00192    // at most how many of this pattern is needed
00193    double ub_;
00194 
00195 public:
00196    
00197   // CSP_VECTOR's pack method returned a BCP_buffer &. Should this too?
00198   void pack(BCP_buffer& buf) const {
00199     buf.pack(cost_).pack(ub_);
00200     widths_.pack(buf);
00201     // no need to "return" because this returns a void
00202   }
00203 
00204   // this constructor is essentially an unpack method for the pattern    
00205   PATTERN(BCP_buffer & buf)
00206   {
00207     // need a routine that unpacks an OsiShallowPackedVector (?)
00208     // Q: How do I know how long the size is? 
00209     // A: It's known by the BCP_buffer method that unpacks a C-style array.
00210     //    See ~/COIN/Bcp/include/BCP_buffer.hpp
00211 
00212     // unpack the buffers into these variables
00213     buf.unpack(cost_).unpack(ub_);
00214     widths_.unpack(buf);
00215   }
00216 
00217   // destructor needs to delete the storage for the ShallowPackedVector
00218   virtual ~PATTERN(){
00219   }
00220   
00221   // may or maynot need these...
00222   inline double getCost () const { return cost_; }
00223   inline double getUb () const { return ub_; }
00224 
00225   const CSP_packedVector& getWidths() const{
00226     return widths_;
00227   }
00228   
00229   // return d_js based on current pis
00230   double dj(const double* pi) const;
00231   
00232   // default constructor 
00233   PATTERN() : cost_(1), widths_(){
00234   }
00235 
00236 
00237   // constructor 
00238   // Note: nonzero element values are permitted
00239   //       but shouldn't be allowed.
00240   //       we are going to assume in the vars-to-cols method that 
00241   //       the widths_ elements are stricly positive.
00242   //       This is for efficiency. 
00243   PATTERN(const int numElements, const int* indices, const double * elements,
00244           const double ub) : 
00245      cost_(1), widths_(numElements, indices, elements), ub_(ub) {}
00246 
00247   // copy construct   - private for now. 
00248   PATTERN(const PATTERN& x) :
00249     cost_(x.cost_), widths_(x.widths_), ub_(x.ub_) {}
00250 
00251 
00252 
00253 
00254 };
00255 
00256 #endif
00257 

Generated on Thu Jan 15 03:00:58 2009 for coin-Bcp by  doxygen 1.4.7