00001
00002
00003 #include <stdio.h>
00004 #include <math.h>
00005
00006 #include "CoinPresolveMatrix.hpp"
00007 #include "CoinPresolveFixed.hpp"
00008 #include "CoinPresolveTighten.hpp"
00009 #include "CoinPresolveUseless.hpp"
00010
00011 const char *do_tighten_action::name() const
00012 {
00013 return ("do_tighten_action");
00014 }
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055 const CoinPresolveAction *do_tighten_action::presolve(CoinPresolveMatrix *prob,
00056 const CoinPresolveAction *next)
00057 {
00058 double *colels = prob->colels_;
00059 int *hrow = prob->hrow_;
00060 CoinBigIndex *mcstrt = prob->mcstrt_;
00061 int *hincol = prob->hincol_;
00062 int ncols = prob->ncols_;
00063
00064 int nrows = prob->nrows_;
00065
00066 double *clo = prob->clo_;
00067 double *cup = prob->cup_;
00068
00069 double *rlo = prob->rlo_;
00070 double *rup = prob->rup_;
00071
00072 double *dcost = prob->cost_;
00073
00074
00075
00076
00077 int *fixup_cols = new int[ncols];
00078 int nfixup_cols = 0;
00079
00080 int *fixdown_cols = new int[ncols];
00081 int nfixdown_cols = 0;
00082
00083 int *useless_rows = new int[nrows];
00084 int nuseless_rows = 0;
00085
00086 action *actions = new action [ncols];
00087 int nactions = 0;
00088
00089 int numberLook = prob->numberColsToDo_;
00090 int iLook;
00091 int * look = prob->colsToDo_;
00092
00093
00094 for (iLook=0;iLook<numberLook;iLook++) {
00095 int j = look[iLook];
00096 if (dcost[j]==0.0) {
00097 int iflag=0;
00098 int nonFree=0;
00099
00100 CoinBigIndex kcs = mcstrt[j];
00101 CoinBigIndex kce = kcs + hincol[j];
00102
00103
00104 for (CoinBigIndex k=kcs; k<kce; ++k) {
00105 int i = hrow[k];
00106 double coeff = colels[k];
00107 double rlb = rlo[i];
00108 double rub = rup[i];
00109
00110 if (-1.0e28 < rlb && rub < 1.0e28) {
00111
00112 iflag=0;
00113 break;
00114 } else if (-1.0e28 < rlb || rub < 1.0e28) {
00115 nonFree++;
00116 }
00117
00118 PRESOLVEASSERT(fabs(coeff) > ZTOLDP);
00119
00120
00121
00122 int jflag = (coeff > 0.0
00123 ? (rub > 1.0e28 ? 1 : -1)
00124 : (rlb < -1.0e28 ? 1 : -1));
00125
00126 if (iflag) {
00127
00128 if (iflag!=jflag) {
00129 iflag=0;
00130 break;
00131 }
00132 } else {
00133
00134 iflag=jflag;
00135 }
00136 }
00137
00138 if (!nonFree)
00139 iflag=0;
00140 if (iflag) {
00141 if (iflag==1 && cup[j]<1.0e10) {
00142 #if DEBUG_PRESOLVE
00143 printf("TIGHTEN UP: %d\n", j);
00144 #endif
00145 fixup_cols[nfixup_cols] = j;
00146 ++nfixup_cols;
00147
00148 } else if (iflag==-1&&clo[j]>-1.0e10) {
00149
00150
00151
00152 #if DEBUG_PRESOLVE
00153 printf("TIGHTEN DOWN: %d\n", j);
00154 #endif
00155
00156 fixdown_cols[nfixdown_cols] = j;
00157 ++nfixdown_cols;
00158
00159 } else {
00160 #if 0
00161 static int limit;
00162 static int which = atoi(getenv("WZ"));
00163 if (which == -1)
00164 ;
00165 else if (limit != which) {
00166 limit++;
00167 continue;
00168 } else
00169 limit++;
00170
00171 printf("TIGHTEN STATS %d %g %g %d: \n", j, clo[j], cup[j], integerType[j]);
00172 double *rowels = prob->rowels_;
00173 int *hcol = prob->hcol_;
00174 int *mrstrt = prob->mrstrt_;
00175 int *hinrow = prob->hinrow_;
00176 for (CoinBigIndex k=kcs; k<kce; ++k) {
00177 int irow = hrow[k];
00178 CoinBigIndex krs = mrstrt[irow];
00179 CoinBigIndex kre = krs + hinrow[irow];
00180 printf("%d %g %g %g: ",
00181 irow, rlo[irow], rup[irow], colels[irow]);
00182 for (CoinBigIndex kk=krs; kk<kre; ++kk)
00183 printf("%d(%g) ", hcol[kk], rowels[kk]);
00184 printf("\n");
00185 }
00186 #endif
00187
00188 {
00189 action *s = &actions[nactions];
00190 nactions++;
00191 s->col = j;
00192 s->direction = iflag;
00193
00194 s->rows = new int[hincol[j]];
00195 s->lbound = new double[hincol[j]];
00196 s->ubound = new double[hincol[j]];
00197 #ifdef DEBUG_PRESOLVE
00198 printf("TIGHTEN FREE: %d ", j);
00199 #endif
00200 int nr = 0;
00201 prob->addCol(j);
00202 for (CoinBigIndex k=kcs; k<kce; ++k) {
00203 int irow = hrow[k];
00204
00205 if (! (rlo[irow] == -PRESOLVE_INF && rup[irow] == PRESOLVE_INF)) {
00206 prob->addRow(irow);
00207 s->rows [nr] = irow;
00208 s->lbound[nr] = rlo[irow];
00209 s->ubound[nr] = rup[irow];
00210 nr++;
00211
00212 useless_rows[nuseless_rows++] = irow;
00213
00214 rlo[irow] = -PRESOLVE_INF;
00215 rup[irow] = PRESOLVE_INF;
00216
00217 #ifdef DEBUG_PRESOLVE
00218 printf("%d ", irow);
00219 #endif
00220 }
00221 }
00222 s->nrows = nr;
00223
00224 #ifdef DEBUG_PRESOLVE
00225 printf("\n");
00226 #endif
00227 }
00228 }
00229 }
00230 }
00231 }
00232
00233
00234 #if PRESOLVE_SUMMARY
00235 if (nfixdown_cols || nfixup_cols || nuseless_rows) {
00236 printf("NTIGHTENED: %d %d %d\n", nfixdown_cols, nfixup_cols, nuseless_rows);
00237 }
00238 #endif
00239
00240 if (nuseless_rows) {
00241 next = new do_tighten_action(nactions, copyOfArray(actions,nactions), next);
00242
00243 next = useless_constraint_action::presolve(prob,
00244 useless_rows, nuseless_rows,
00245 next);
00246 }
00247 delete [] actions;
00248 delete[]useless_rows;
00249
00250 if (nfixdown_cols) {
00251 next = make_fixed_action::presolve(prob, fixdown_cols, nfixdown_cols,
00252 true,
00253 next);
00254 }
00255 delete[]fixdown_cols;
00256
00257 if (nfixup_cols) {
00258 next = make_fixed_action::presolve(prob, fixup_cols, nfixup_cols,
00259 false,
00260 next);
00261 }
00262 delete[]fixup_cols;
00263
00264 return (next);
00265 }
00266
00267 void do_tighten_action::postsolve(CoinPostsolveMatrix *prob) const
00268 {
00269 const action *const actions = actions_;
00270 const int nactions = nactions_;
00271
00272 double *colels = prob->colels_;
00273 int *hrow = prob->hrow_;
00274 CoinBigIndex *mcstrt = prob->mcstrt_;
00275 int *hincol = prob->hincol_;
00276 int *link = prob->link_;
00277
00278
00279 double *clo = prob->clo_;
00280 double *cup = prob->cup_;
00281 double *rlo = prob->rlo_;
00282 double *rup = prob->rup_;
00283
00284 double *sol = prob->sol_;
00285
00286
00287
00288 double *acts = prob->acts_;
00289
00290
00291
00292
00293
00294
00295
00296
00297 for (const action *f = &actions[nactions-1]; actions<=f; f--) {
00298 int jcol = f->col;
00299
00300 int nr = f->nrows;
00301 const int *rows = f->rows;
00302 const double *lbound = f->lbound;
00303 const double *ubound = f->ubound;
00304
00305 PRESOLVEASSERT(prob->getColumnStatus(jcol)!=CoinPrePostsolveMatrix::basic);
00306 int i;
00307 for (i=0;i<nr; ++i) {
00308 int irow = rows[i];
00309
00310 rlo[irow] = lbound[i];
00311 rup[irow] = ubound[i];
00312
00313 PRESOLVEASSERT(prob->getRowStatus(irow)==CoinPrePostsolveMatrix::basic);
00314 }
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325 double correction = 0.0;
00326
00327 int last_corrected = -1;
00328 CoinBigIndex k = mcstrt[jcol];
00329 int nk = hincol[jcol];
00330 for (i=0; i<nk; ++i) {
00331 int irow = hrow[k];
00332 double coeff = colels[k];
00333 k = link[k];
00334 double newrlo = rlo[irow];
00335 double newrup = rup[irow];
00336 double activity = acts[irow];
00337
00338 if (activity + correction * coeff < newrlo) {
00339
00340 PRESOLVEASSERT( ! (activity + correction * coeff > newrup) );
00341
00342 last_corrected = irow;
00343
00344
00345 double new_correction = (newrlo - activity) / coeff;
00346 correction = new_correction;
00347 } else if (activity + correction * coeff > newrup) {
00348 last_corrected = irow;
00349
00350 double new_correction = (newrup - activity) / coeff;
00351 correction = new_correction;
00352 }
00353 }
00354
00355 if (last_corrected>=0) {
00356 sol[jcol] += correction;
00357
00358
00359
00360
00361
00362
00363
00364 k = mcstrt[jcol];
00365 for (i=0; i<nk; ++i) {
00366 int irow = hrow[k];
00367 double coeff = colels[k];
00368 k = link[k];
00369
00370
00371 acts[irow] += correction * coeff;
00372 }
00373 }
00374
00375
00376
00377 if (fabs(sol[jcol] - clo[jcol]) > ZTOLDP &&
00378 fabs(sol[jcol] - cup[jcol]) > ZTOLDP) {
00379
00380 prob->setRowStatus(last_corrected,CoinPrePostsolveMatrix::atLowerBound);
00381 prob->setColumnStatus(jcol,CoinPrePostsolveMatrix::basic);
00382 }
00383 }
00384 }