GAP_KnapPisinger.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
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;
00074 item* m_items;
00075 int m_capacity;
00076 int* m_weight;
00077 int* m_profit;
00078 double* m_workDbl;
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
00087 int calcScaleFactor(const double* redCost,
00088 const double epsTol = 1.0e-4) {
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
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
00153
00154
00155
00156
00157
00158
00159
00160
00161
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
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
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
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,
00242 lItem,
00243 m_capacity,
00244 -COIN_INT_MAX,
00245 COIN_INT_MAX,
00246 1,
00247 0);
00248
00249 }
00250
00251 int origColIndex;
00252
00253
00254
00255
00256
00257
00258
00259
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