GAP_KnapPisinger.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-2007, Lehigh University, Matthew Galati, and Ted Ralphs//
00010 // All Rights Reserved.                                                      //
00011 //===========================================================================//
00012 
00013 #ifndef GAP_KNAP_PISINGER_INCLUDED
00014 #define GAP_KNAP_PISINGER_INCLUDED
00015 
00016 // --------------------------------------------------------------------- //
00061 // --------------------------------------------------------------------- //
00062 extern "C" {
00063 #include "combo.h"
00064 }
00065 
00066 // --------------------------------------------------------------------- //
00067 #include "UtilMacros.h"
00068 
00069 // --------------------------------------------------------------------- //
00070 class GAP_KnapPisinger {
00071 
00072 private:
00073    int      m_nItems;   //< number of items (== nTasks)
00074    item*    m_items;    //< array of items for Pisinger solver
00075    int      m_capacity; //< capacity of knapsack
00076    int*     m_weight;   //< weight of items
00077    int*     m_profit;   //< profit of items
00078    double* m_workDbl;   //< temp work space
00079 
00080 private:
00081    inline const int getIndexIJ(const int i,
00082                                const int j) const {
00083       return (i * m_nItems) + j;
00084    }
00085 
00086    //1.0e-6 seems to cause overflow
00087    int calcScaleFactor(const double* redCost,
00088                        const double   epsTol = 1.0e-4) {
00089       //---
00090       //--- A very simple function to scale an array of doubles to integers.
00091       //---    Note: epstol denotes the preferred accuracy,
00092       //---    so, we will scale by 1.0/epstol, unless something smaller works.
00093       //--- It returns the scale factor.
00094       //---
00095       //--- Since the knapsack solver solves the max problem, we will
00096       //--- flip the sign of the redCost first (max p == min -p).
00097       //---
00098       //--- This also means that we can look just at redCost[i] <= 0.
00099       //---
00100       int      i, scaleFactor = 1, n_aFrac = 0, factorToBig = 0;
00101       double   fractionalPart, rcFlipped;
00102       double   oneOverEps = 1.0 / epsTol;
00103 
00104       for (i = 0; i < m_nItems; i++) {
00105          if (redCost[i] >= 0) {
00106             continue;
00107          }
00108 
00109          rcFlipped = -redCost[i];
00110          fractionalPart = UtilFracPart(rcFlipped);
00111 
00112          if (!UtilIsZero(fractionalPart)) {
00113             fractionalPart     *= oneOverEps;
00114             m_workDbl[n_aFrac++]  = (int)fractionalPart * (double)epsTol;
00115          }
00116       }
00117 
00118       for (i = 0; i < n_aFrac; i++) {
00119          CoinAssertDebug(m_workDbl[i] < (COIN_INT_MAX / scaleFactor));
00120          m_workDbl[i] *= scaleFactor;
00121 
00122          while (!UtilIsZero(UtilFracPart(m_workDbl[i]))) {
00123             scaleFactor *= 10;
00124 
00125             if (scaleFactor >= oneOverEps) {
00126                factorToBig = 1;
00127                break;
00128             }
00129 
00130             CoinAssertDebug(m_workDbl[i] < (COIN_INT_MAX / 10));
00131             m_workDbl[i]    *= 10;
00132             CoinAssertDebug(m_workDbl[i] >= 0);
00133          }
00134 
00135          if (factorToBig) {
00136             break;
00137          }
00138       }
00139 
00140       return scaleFactor;
00141    }
00142 
00143 public:
00144    void solve(const int        blockB,
00145               const double*    redCost,
00146               const double*    origCost,
00147               vector<int>&     solInd,
00148               vector<double>& solEls,
00149               double&          varRedCost,
00150               double&          varOrigCost) {
00151       //---
00152       //--- Since we want to find min redCost, and the constraint is a
00153       //--- simple knapsack constraint, we know that if redCost[i] >= 0
00154       //--- then we can fix x[i]=0. It makes no sense to select.
00155       //---
00156       //--- The knapsack solver solves maximization problem, so we also
00157       //--- need to fip the sign of the redCost.
00158       //---
00159       //--- The knapsack solver also expects integers for weight and profit,
00160       //--- the weights are already integer, but since the profits are coming
00161       //--- from reduced cost, we need to scale them to integers
00162       //---
00163       int i, j;
00164       int nItems      = 0;
00165       int scaleFactor = calcScaleFactor(redCost);
00166       double      rcScaled;
00167       int         weightSum = 0;
00168       vector<int> shrunkToOrig;
00169 
00170       for (i = 0; i < m_nItems; i++) {
00171          if (redCost[i] < 0.0) {
00172             rcScaled    = (-redCost[i]) * scaleFactor;
00173             long rcLong = static_cast<long>(floor(rcScaled + 0.5));
00174             CoinAssert(rcScaled < COIN_INT_MAX);
00175             m_items[nItems].p = rcLong;
00176             CoinAssert(m_items[nItems].p >= 0);
00177             m_items[nItems].w = m_weight[i];
00178             m_items[nItems].i = nItems;
00179             m_items[nItems].x = 0;
00180             weightSum += m_weight[i];
00181             shrunkToOrig.push_back(i);
00182             nItems++;
00183          }
00184       }
00185 
00186       //---
00187       //--- print the current problem
00188       //---
00189       /*
00190       printf("COMBO Knap Max (nItems = %d, cap=%d)\n", nItems, m_capacity);
00191       for(i = 0; i < nItems; i++){
00192       j = shrunkToOrig[i];
00193       printf("[%d->%d] pOrig:%g, p:%ld, w:%ld\n",
00194       i, j, -redCost[j], m_items[i].p, m_items[i].w);
00195       }
00196       */
00197 
00198       //---
00199       //--- solve the knapsack problem
00200       //---   first deal with some trivial cases
00201       if (nItems == 1) {
00202          CoinAssert(m_items[0].w <= m_capacity);
00203          m_items[0].x = 1;
00204       } else if (weightSum <= m_capacity) {
00205          //---
00206          //--- then put all items in the knapsack (to max profit)
00207          //---
00208          for (i = 0; i < nItems; i++) {
00209             m_items[i].x = 1;
00210          }
00211       } else if (nItems == 2) {
00212          CoinAssert(m_items[0].w <= m_capacity);
00213          CoinAssert(m_items[1].w <= m_capacity);
00214          int w0 = m_items[0].w;
00215          int w1 = m_items[1].w;
00216          int p0 = m_items[0].p;
00217          int p1 = m_items[1].p;
00218          double bestObj = 0;
00219 
00220          if ( (w1 <= m_capacity) && (p1 > bestObj) ) {
00221             bestObj      = p1;
00222             m_items[0].x = 0;
00223             m_items[1].x = 1;
00224          }
00225 
00226          if ( (w0 <= m_capacity) && (p0 > bestObj) ) {
00227             bestObj      = p0;
00228             m_items[0].x = 1;
00229             m_items[1].x = 0;
00230          }
00231 
00232          if ( (w0 + w1 <= m_capacity) && (p0 + p1 > bestObj) ) {
00233             bestObj      = p0 + p1;
00234             m_items[0].x = 1;
00235             m_items[1].x = 1;
00236          }
00237       } else if (nItems > 2) {
00238          item* fItem  = m_items;
00239          item* lItem  = m_items + (nItems - 1);
00240          long   obj    = 0;
00241          obj = combo(fItem,           //first item
00242                      lItem,           //last item
00243                      m_capacity,      //capacity of knapsack
00244                      -COIN_INT_MAX,   //obj lower bound
00245                      COIN_INT_MAX,    //obj upper bound
00246                      1,               //define sol vector
00247                      0);              //do not solve relaxed prob
00248          //printf("combo obj = %ld\n", obj);
00249       }
00250 
00251       int origColIndex;
00252       /*int wtSum = 0;
00253       for(i = 0; i < nItems; i++)
00254       printf("m_items[%d].x=%d i=%d p=%ld w=%ld\n",
00255       i,
00256       m_items[i].i,
00257       m_items[i].x,
00258       m_items[i].p,
00259       m_items[i].w);*/
00260 
00261       for (i = 0; i < nItems; i++) {
00262          if (m_items[i].x == 1) {
00263             j            = shrunkToOrig[m_items[i].i];
00264             origColIndex = getIndexIJ(blockB, j);
00265             varRedCost  += redCost[j];
00266             varOrigCost += origCost[j];
00267             solInd.push_back(origColIndex);
00268             solEls.push_back(1.0);
00269          }
00270       }
00271    }
00272 
00273 public:
00274    GAP_KnapPisinger(const int   nItems,
00275                     const int   capacity,
00276                     const int* weight,
00277                     const int* profit) :
00278       m_nItems   (nItems),
00279       m_items    (0),
00280       m_capacity (capacity),
00281       m_weight   (0),
00282       m_profit   (0),
00283       m_workDbl  (0) {
00284       m_items    = new item[nItems];
00285       m_weight   = new int[nItems];
00286       m_profit   = new int[nItems];
00287       m_workDbl  = new double[nItems];
00288       CoinAssertHint(m_items && m_weight && m_profit && m_workDbl,
00289                      "Error: Out of Memory");
00290       memcpy(m_weight, weight, nItems * sizeof(int));
00291       memcpy(m_profit, profit, nItems * sizeof(int));
00292    }
00293    ~GAP_KnapPisinger() {
00294       UTIL_DELARR(m_items)
00295       UTIL_DELARR(m_weight);
00296       UTIL_DELARR(m_profit);
00297       UTIL_DELARR(m_workDbl);
00298    }
00299 };
00300 
00301 
00302 #endif

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