MMKP_MCKnap.h

Go to the documentation of this file.
00001 //===========================================================================//
00002 // This file is part of the Decomp Solver Framework.                         //
00003 //                                                                           //
00004 // Decomp is distributed under the Common Public License as part of the      //
00005 // COIN-OR repository (http://www.coin-or.org).                              //
00006 //                                                                           //
00007 // Author: Matthew Galati, Lehigh University                                 //
00008 //                                                                           //
00009 // Copyright (C) 2002-2015, Lehigh University, Matthew Galati, and Ted Ralphs//
00010 // All Rights Reserved.                                                      //
00011 //===========================================================================//
00012 
00013 #ifndef MMKP_MCKNAP_INCLUDED
00014 #define MMKP_MCKNAP_INCLUDED
00015 
00016 //---
00017 //--- The MMKP MCKnap -- interface class for
00018 //---     Pisinger's Multi-Choice Knapsack Solver
00019 //---       http://www.diku.dk/~pisinger/codes.html
00020 //---
00021 
00022 //---
00023 //--- Multi-Choice Knapsack Problem
00024 //---  min  sum{i in 1..n, j in 1..l[i]}  c[i,j] x[i,j]
00025 //---  s.t. sum{i in 1..n, j in 1..l[i]}  w[i,j] x[i,j] <= b
00026 //---       sum{j in 1..l[i]}                      x[i,j]  = 1   , i in 1..n
00027 //---
00028 
00029 
00030 // --------------------------------------------------------------------- //
00031 extern "C"{
00032 #include "mcknap.h"
00033 }
00034 
00035 //extern solstruct optsol;
00036 
00037 // --------------------------------------------------------------------- //
00038 #include "UtilMacros.h"
00039 using namespace std;
00040 
00041 // --------------------------------------------------------------------- //
00042 class MMKP_MCKnap{
00043  private:
00044 
00045    //---
00046    //--- typedef int           itype;   // item profits and weights 
00047    //--- typedef long          stype;   // sum of pofit or weight
00048    //--- typedef unsigned long vtype;   // solution vector
00049    //---
00050    //---
00051    //--- typedef struct {
00052    //---    itemset  *fset;
00053    //---    itemset  *lset;
00054    //---    ntype    size;
00055    //--- } isetset;
00056    //---
00057    isetset        * m_setset;        // set of itemsetsets
00058    double         * m_costDbl;       // temp storage
00059    int            * m_cost;          // cost vector (integer)
00060    int            * m_weight;        // weight vector (integer)
00061    int              m_nCols;         // size of mc-knap problem
00062    int              m_nGroupRows;
00063    int              m_nGroupCols;
00064    int              m_capacity;      // capacity (integer)
00065    int              m_cscale;        // cost vector scale factor
00066    int              m_wscale;        // weight vector scale factor
00067 
00068  public:
00069    //separate function just to reset cost...from one call to next
00070    void solveTrivialMaxSum(const double * redCost,
00071                const double * origCost,
00072                vector<int>  & solInd,
00073                double       & varRedCost,
00074                double       & varOrigCost);   
00075 
00076    inline const int getIndexIJ(const int i,
00077                                const int j) const{
00078       return (i * m_nGroupCols) + j;
00079    }
00080 
00081    inline pair<int,int> getIndexInv(const int index) const {      
00082       return make_pair(index / m_nGroupCols, index % m_nGroupCols);
00083    }
00084 
00085    void setMCKnapData(const double   capacity,
00086               const double * weight);
00087 
00088    void solveMCKnap(const double   * redCost,
00089             const double   * origCost,
00090             vector<int>    & solInd,
00091             vector<double> & solEls,
00092             double         & varRedCost,
00093             double         & varOrigCost);
00094 
00095  public:
00096    MMKP_MCKnap(const int nGroupRows,
00097            const int nGroupCols) :
00098       m_setset   (NULL),
00099       m_costDbl  (NULL),
00100       m_cost     (NULL),
00101       m_weight   (NULL),
00102       m_nCols    (nGroupRows * nGroupCols),
00103       m_nGroupRows(nGroupRows),
00104       m_nGroupCols(nGroupCols),
00105       m_capacity (0),
00106       m_cscale   (1),
00107       m_wscale   (1)      
00108       {
00109      m_costDbl = new double[m_nCols];
00110      m_cost    = new int[m_nCols];
00111      m_weight  = new int[m_nCols];
00112      assert(m_costDbl && m_cost && m_weight);       
00113       }
00114    ~MMKP_MCKnap() {      
00115       if(m_setset){         
00116          itemset * setPtr = m_setset->fset;
00117          if(setPtr){
00118             int       i;
00119             for(i = 0; i < m_setset->size; i++){
00120                if(setPtr->fset)
00121                   free(setPtr->fset);
00122                setPtr++;
00123             }
00124             free(m_setset->fset);
00125          }
00126          free(m_setset);
00127       }
00128       UTIL_DELARR(m_costDbl);
00129       UTIL_DELARR(m_cost);
00130       UTIL_DELARR(m_weight);
00131    }
00132 };
00133 
00134 
00135 #endif

Generated on 12 Mar 2015 for Dip-All by  doxygen 1.6.1