00001
00002
00003
00004 #include <stdio.h>
00005 #include <math.h>
00006
00007 #include "CoinPresolveMatrix.hpp"
00008
00009 #include "CoinPresolveEmpty.hpp"
00010 #include "CoinMessage.hpp"
00011
00012
00013 const CoinPresolveAction *drop_empty_cols_action::presolve(CoinPresolveMatrix *prob,
00014 int *ecols,
00015 int necols,
00016 const CoinPresolveAction *next)
00017 {
00018 int ncols = prob->ncols_;
00019 CoinBigIndex *mcstrt = prob->mcstrt_;
00020 int *hincol = prob->hincol_;
00021
00022
00023
00024
00025
00026 double *clo = prob->clo_;
00027 double *cup = prob->cup_;
00028 double *dcost = prob->cost_;
00029
00030 const double ztoldj = prob->ztoldj_;
00031
00032
00033
00034
00035 char * integerType = prob->integerType_;
00036 int * originalColumn = prob->originalColumn_;
00037
00038 const double maxmin = prob->maxmin_;
00039
00040 double * sol = prob->sol_;
00041 unsigned char * colstat = prob->colstat_;
00042
00043 action *actions = new action[necols];
00044 int * colmapping = new int [ncols];
00045
00046 memset(colmapping,0,ncols*sizeof(int));
00047 int i;
00048 for (i=necols-1; i>=0; i--) {
00049 int jcol = ecols[i];
00050 colmapping[jcol]=-1;
00051 action &e = actions[i];
00052
00053 e.jcol = jcol;
00054 e.clo = clo[jcol];
00055 e.cup = cup[jcol];
00056 e.cost = dcost[jcol];
00057
00058
00059
00060 if (fabs(dcost[jcol])<ztoldj)
00061 dcost[jcol]=0.0;
00062 if (dcost[jcol] * maxmin == 0.0) {
00063
00064
00065 e.sol = (-PRESOLVE_INF < clo[jcol]
00066 ? clo[jcol]
00067 : cup[jcol] < PRESOLVE_INF
00068 ? cup[jcol]
00069 : 0.0);
00070 } else if (dcost[jcol] * maxmin > 0.0) {
00071 if (-PRESOLVE_INF < clo[jcol])
00072 e.sol = clo[jcol];
00073 else {
00074 prob->messageHandler()->message(COIN_PRESOLVE_COLUMNBOUNDB,
00075 prob->messages())
00076 <<jcol
00077 <<CoinMessageEol;
00078 prob->status_ |= 2;
00079 break;
00080 }
00081 } else {
00082 if (cup[jcol] < PRESOLVE_INF)
00083 e.sol = cup[jcol];
00084 else {
00085 prob->messageHandler()->message(COIN_PRESOLVE_COLUMNBOUNDA,
00086 prob->messages())
00087 <<jcol
00088 <<CoinMessageEol;
00089 prob->status_ |= 2;
00090 break;
00091 }
00092 }
00093
00094 #if DEBUG_PRESOLVE
00095 if (e.sol * dcost[jcol]) {
00096
00097 }
00098 #endif
00099 prob->change_bias(e.sol * dcost[jcol]);
00100
00101
00102 }
00103 int ncols2=0;
00104
00105
00106 for (i=0;i<ncols;i++) {
00107 if (!colmapping[i]) {
00108 mcstrt[ncols2] = mcstrt[i];
00109 hincol[ncols2] = hincol[i];
00110
00111 clo[ncols2] = clo[i];
00112 cup[ncols2] = cup[i];
00113
00114 dcost[ncols2] = dcost[i];
00115 if (sol) {
00116 sol[ncols2] = sol[i];
00117 colstat[ncols2] = colstat[i];
00118 }
00119
00120 integerType[ncols2] = integerType[i];
00121 originalColumn[ncols2] = originalColumn[i];
00122 ncols2++;
00123 }
00124 }
00125
00126 delete [] colmapping;
00127 prob->ncols_ = ncols2;
00128
00129 return (new drop_empty_cols_action(necols, actions, next));
00130 }
00131
00132
00133 const CoinPresolveAction *drop_empty_cols_action::presolve(CoinPresolveMatrix *prob,
00134 const CoinPresolveAction *next)
00135 {
00136 const int *hincol = prob->hincol_;
00137
00138
00139 int ncols = prob->ncols_;
00140 int i;
00141 int nempty = 0;
00142 int * empty = new int [ncols];
00143
00144
00145 for (i=0; i<ncols; i++)
00146 if (hincol[i] == 0) {
00147 #if DEBUG_PRESOLVE
00148 if (nempty==0)
00149 printf("UNUSED COLS: ");
00150 printf("%d ", i);
00151 #endif
00152 empty[nempty++] = i;
00153 }
00154
00155 if (nempty) {
00156 #if DEBUG_PRESOLVE
00157 printf("\ndropped %d cols\n", nempty);
00158 #endif
00159 next = drop_empty_cols_action::presolve(prob, empty, nempty, next);
00160 }
00161 delete [] empty;
00162 return (next);
00163 }
00164
00165
00166 void drop_empty_cols_action::postsolve(CoinPostsolveMatrix *prob) const
00167 {
00168 const int nactions = nactions_;
00169 const action *const actions = actions_;
00170
00171 int ncols = prob->ncols_;
00172
00173
00174 CoinBigIndex *mcstrt = prob->mcstrt_;
00175 int *hincol = prob->hincol_;
00176
00177
00178 double *clo = prob->clo_;
00179 double *cup = prob->cup_;
00180
00181 double *sol = prob->sol_;
00182 double *cost = prob->cost_;
00183 double *rcosts = prob->rcosts_;
00184 unsigned char *colstat = prob->colstat_;
00185 const double maxmin = prob->maxmin_;
00186
00187 int ncols2 = ncols+nactions;
00188 int * colmapping = new int [ncols2];
00189
00190 memset(colmapping,0,ncols2*sizeof(int));
00191 char *cdone = prob->cdone_;
00192 int action_i;
00193 for (action_i = 0; action_i < nactions; action_i++) {
00194 const action *e = &actions[action_i];
00195 int jcol = e->jcol;
00196 colmapping[jcol]=-1;
00197 }
00198
00199 int i;
00200
00201
00202 for (i=ncols2-1;i>=0;i--) {
00203 if (!colmapping[i]) {
00204 ncols--;
00205 mcstrt[i] = mcstrt[ncols];
00206 hincol[i] = hincol[ncols];
00207
00208 clo[i] = clo[ncols];
00209 cup[i] = cup[ncols];
00210
00211 cost[i] = cost[ncols];
00212
00213 sol[i] = sol[ncols];
00214
00215 rcosts[i] = rcosts[ncols];
00216
00217 if (colstat)
00218 colstat[i] = colstat[ncols];
00219 cdone[i] = cdone[ncols];
00220 }
00221 }
00222 assert (!ncols);
00223
00224 delete [] colmapping;
00225
00226 for (action_i = 0; action_i < nactions; action_i++) {
00227 const action *e = &actions[action_i];
00228 int jcol = e->jcol;
00229
00230
00231 clo[jcol] = e->clo;
00232 cup[jcol] = e->cup;
00233 sol[jcol] = e->sol;
00234 cost[jcol] = e->cost;
00235
00236 rcosts[jcol] = maxmin*cost[jcol];
00237
00238 hincol[jcol] = 0;
00239
00240 cdone[jcol] = DROP_COL;
00241 if (colstat)
00242 prob->setColumnStatusUsingValue(jcol);
00243 }
00244
00245 prob->ncols_ += nactions;
00246 }
00247
00248
00249
00250 const CoinPresolveAction *drop_empty_rows_action::presolve(CoinPresolveMatrix *prob,
00251 const CoinPresolveAction *next)
00252 {
00253 int ncols = prob->ncols_;
00254 CoinBigIndex *mcstrt = prob->mcstrt_;
00255 int *hincol = prob->hincol_;
00256 int *hrow = prob->hrow_;
00257
00258 int nrows = prob->nrows_;
00259
00260
00261 int *hinrow = prob->hinrow_;
00262
00263
00264 double *rlo = prob->rlo_;
00265 double *rup = prob->rup_;
00266
00267 unsigned char *rowstat = prob->rowstat_;
00268 double *acts = prob->acts_;
00269 int * originalRow = prob->originalRow_;
00270
00271
00272
00273
00274 int i;
00275 int nactions = 0;
00276 for (i=0; i<nrows; i++)
00277 if (hinrow[i] == 0)
00278 nactions++;
00279
00280 if (nactions == 0)
00281 return next;
00282 else {
00283 action *actions = new action[nactions];
00284 int * rowmapping = new int [nrows];
00285
00286 nactions = 0;
00287 int nrows2=0;
00288 for (i=0; i<nrows; i++) {
00289 if (hinrow[i] == 0) {
00290 action &e = actions[nactions];
00291 nactions++;
00292
00293 #if DEBUG_PRESOLVE
00294 if (nactions==1)
00295 printf("unused rows: ");
00296
00297 printf("%d ", i);
00298 #endif
00299 if (rlo[i] > 0.0 || rup[i] < 0.0) {
00300 if (rlo[i]<=prob->feasibilityTolerance_ &&
00301 rup[i]>=-prob->feasibilityTolerance_) {
00302 rlo[i]=0.0;
00303 rup[i]=0.0;
00304 } else {
00305 prob->status_|= 1;
00306 prob->messageHandler()->message(COIN_PRESOLVE_ROWINFEAS,
00307 prob->messages())
00308 <<i
00309 <<rlo[i]
00310 <<rup[i]
00311 <<CoinMessageEol;
00312 break;
00313 }
00314 }
00315 e.row = i;
00316 e.rlo = rlo[i];
00317 e.rup = rup[i];
00318 rowmapping[i]=-1;
00319
00320 } else {
00321
00322 rlo[nrows2]=rlo[i];
00323 rup[nrows2]=rup[i];
00324 originalRow[nrows2]=i;
00325 if (acts) {
00326 acts[nrows2]=acts[i];
00327 rowstat[nrows2]=rowstat[i];
00328 }
00329 rowmapping[i]=nrows2++;
00330 }
00331 }
00332
00333
00334 for (i=0;i<ncols;i++) {
00335 int j;
00336 for (j=mcstrt[i];j<mcstrt[i]+hincol[i];j++)
00337 hrow[j] = rowmapping[hrow[j]];
00338 }
00339 delete [] rowmapping;
00340
00341 prob->nrows_ = nrows2;
00342
00343 #if DEBUG_PRESOLVE
00344 if (nactions)
00345 printf("\ndropped %d rows\n", nactions);
00346 #endif
00347 return (new drop_empty_rows_action(nactions, actions, next));
00348 }
00349 }
00350
00351 void drop_empty_rows_action::postsolve(CoinPostsolveMatrix *prob) const
00352 {
00353 const int nactions = nactions_;
00354 const action *const actions = actions_;
00355
00356 int ncols = prob->ncols_;
00357 CoinBigIndex *mcstrt = prob->mcstrt_;
00358 int *hincol = prob->hincol_;
00359
00360 int *hrow = prob->hrow_;
00361
00362 double *rlo = prob->rlo_;
00363 double *rup = prob->rup_;
00364 unsigned char *rowstat = prob->rowstat_;
00365 double *rowduals = prob->rowduals_;
00366 double *acts = prob->acts_;
00367 char *rdone = prob->rdone_;
00368
00369 int nrows0 = prob->nrows0_;
00370 int nrows = prob->nrows_;
00371
00372 int * rowmapping = new int [nrows0];
00373
00374 int i, action_i;
00375 for (i=0; i<nrows0; i++)
00376 rowmapping[i] = 0;
00377
00378 for (action_i = 0; action_i<nactions; action_i++) {
00379 const action *e = &actions[action_i];
00380 int hole = e->row;
00381 rowmapping[hole]=-1;
00382 }
00383
00384
00385 for (i=nrows0-1; i>=0; i--) {
00386 if (!rowmapping[i]) {
00387
00388 nrows--;
00389 rlo[i]=rlo[nrows];
00390 rup[i]=rup[nrows];
00391 acts[i]=acts[nrows];
00392 rowduals[i]=rowduals[nrows];
00393 if (rowstat)
00394 rowstat[i] = rowstat[nrows];
00395 }
00396 }
00397 assert (!nrows);
00398
00399 for (i=0;i<nrows0;i++) {
00400 if (!rowmapping[i])
00401 rowmapping[nrows++]=i;
00402 }
00403
00404 for (int j=0; j<ncols; j++) {
00405 CoinBigIndex start = mcstrt[j];
00406 CoinBigIndex end = start + hincol[j];
00407
00408 for (CoinBigIndex k=start; k<end; ++k) {
00409 hrow[k] = rowmapping[hrow[k]];
00410 }
00411 }
00412
00413
00414 delete [] rowmapping;
00415
00416 for (action_i = 0; action_i < nactions; action_i++) {
00417 const action *e = &actions[action_i];
00418 int irow = e->row;
00419
00420
00421 rlo[irow] = e->rlo;
00422 rup[irow] = e->rup;
00423
00424 if (rowstat)
00425 prob->setRowStatus(irow,CoinPrePostsolveMatrix::basic);
00426 rowduals[irow] = 0.0;
00427 acts[irow] = 0.0;
00428
00429
00430
00431
00432 rdone[irow] = DROP_ROW;
00433 }
00434
00435 prob->nrows_ = prob->nrows_+nactions;
00436 }
00437