00001
00002
00003
00004 #include <stdio.h>
00005 #include <math.h>
00006
00007 #include "CoinHelperFunctions.hpp"
00008 #include "CoinPresolveMatrix.hpp"
00009
00010 #include "CoinPresolveEmpty.hpp"
00011 #include "CoinPresolveFixed.hpp"
00012 #include "CoinPresolveSingleton.hpp"
00013 #include "CoinMessage.hpp"
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 const CoinPresolveAction *
00024 slack_doubleton_action::presolve(CoinPresolveMatrix *prob,
00025 const CoinPresolveAction *next,
00026 bool & notFinished)
00027 {
00028 double *colels = prob->colels_;
00029 int *hrow = prob->hrow_;
00030 CoinBigIndex *mcstrt = prob->mcstrt_;
00031 int *hincol = prob->hincol_;
00032 int ncols = prob->ncols_;
00033
00034 double *clo = prob->clo_;
00035 double *cup = prob->cup_;
00036
00037 double *rowels = prob->rowels_;
00038 const int *hcol = prob->hcol_;
00039 const CoinBigIndex *mrstrt = prob->mrstrt_;
00040 int *hinrow = prob->hinrow_;
00041
00042
00043 double *rlo = prob->rlo_;
00044 double *rup = prob->rup_;
00045
00046
00047 unsigned char *rowstat = prob->rowstat_;
00048
00049 double * sol = prob->sol_;
00050
00051
00052
00053
00054 const double ztolzb = prob->ztolzb_;
00055
00056 int numberLook = prob->numberRowsToDo_;
00057 int iLook;
00058 int * look = prob->rowsToDo_;
00059
00060 action actions[MAX_SLACK_DOUBLETONS];
00061 int nactions = 0;
00062 notFinished = false;
00063
00064 int * fixed_cols = new int [ncols];
00065 int nfixed_cols = 0;
00066
00067
00068
00069
00070 for (iLook=0;iLook<numberLook;iLook++) {
00071 int irow = look[iLook];
00072 if (hinrow[irow] == 1) {
00073 int jcol = hcol[mrstrt[irow]];
00074 double coeff = rowels[mrstrt[irow]];
00075 double lo = rlo[irow];
00076 double up = rup[irow];
00077 double acoeff = fabs(coeff);
00078
00079
00080 if (acoeff < ZTOLDP)
00081 continue;
00082
00083
00084 if (fabs(cup[jcol] - clo[jcol]) < ztolzb)
00085 continue;
00086
00087 {
00088
00089 prob->addCol(jcol);
00090 action *s = &actions[nactions];
00091 nactions++;
00092
00093 s->col = jcol;
00094 s->clo = clo[jcol];
00095 s->cup = cup[jcol];
00096
00097 s->row = irow;
00098 s->rlo = rlo[irow];
00099 s->rup = rup[irow];
00100
00101 s->coeff = coeff;
00102 }
00103
00104 if (coeff < 0.0) {
00105 swap(lo, up);
00106 lo = -lo;
00107 up = -up;
00108 }
00109
00110 if (lo <= -PRESOLVE_INF)
00111 lo = -PRESOLVE_INF;
00112 else {
00113 lo /= acoeff;
00114 if (lo <= -PRESOLVE_INF)
00115 lo = -PRESOLVE_INF;
00116 }
00117
00118 if (up > PRESOLVE_INF)
00119 up = PRESOLVE_INF;
00120 else {
00121 up /= acoeff;
00122 if (up > PRESOLVE_INF)
00123 up = PRESOLVE_INF;
00124 }
00125
00126 if (clo[jcol] < lo)
00127 clo[jcol] = lo;
00128
00129 if (cup[jcol] > up)
00130 cup[jcol] = up;
00131
00132 if (fabs(cup[jcol] - clo[jcol]) < ZTOLDP) {
00133 fixed_cols[nfixed_cols++] = jcol;
00134 }
00135
00136 if (lo > up) {
00137 if (lo <= up + prob->feasibilityTolerance_) {
00138
00139 double nearest = floor(lo+0.5);
00140 if (fabs(nearest-lo)<2.0*prob->feasibilityTolerance_) {
00141 lo = nearest;
00142 up = nearest;
00143 } else {
00144 lo = up;
00145 }
00146 clo[jcol] = lo;
00147 cup[jcol] = up;
00148 } else {
00149 prob->status_ |= 1;
00150 prob->messageHandler()->message(COIN_PRESOLVE_COLINFEAS,
00151 prob->messages())
00152 <<jcol
00153 <<lo
00154 <<up
00155 <<CoinMessageEol;
00156 break;
00157 }
00158 }
00159
00160 #if 0&&DEBUG_PRESOLVE
00161 printf("SINGLETON R-%d C-%d\n", irow, jcol);
00162 #endif
00163
00164
00165
00166 hinrow[irow] = 0;
00167
00168
00169 rlo[irow] = 0.0;
00170 rup[irow] = 0.0;
00171
00172 if (rowstat) {
00173
00174 int basisChoice=0;
00175 int numberBasic=0;
00176 if (prob->columnIsBasic(jcol))
00177 numberBasic++;
00178 if (prob->rowIsBasic(irow))
00179 numberBasic++;
00180 if (sol[jcol]<=clo[jcol]+ztolzb) {
00181 sol[jcol] =clo[jcol];
00182 prob->setColumnStatus(jcol,CoinPrePostsolveMatrix::atLowerBound);
00183 } else if (sol[jcol]>=cup[jcol]-ztolzb) {
00184 sol[jcol] =cup[jcol];
00185 prob->setColumnStatus(jcol,CoinPrePostsolveMatrix::atUpperBound);
00186 } else {
00187 basisChoice=1;
00188 }
00189 if (numberBasic>1||basisChoice)
00190 prob->setColumnStatus(jcol,CoinPrePostsolveMatrix::basic);
00191 }
00192
00193
00194 presolve_delete_from_row(jcol, irow, mcstrt, hincol, hrow, colels);
00195
00196 if (nactions >= MAX_SLACK_DOUBLETONS) {
00197 notFinished=true;
00198 break;
00199 }
00200 }
00201 }
00202
00203 if (nactions) {
00204 #if PRESOLVE_SUMMARY
00205 printf("SINGLETON ROWS: %d\n", nactions);
00206 #endif
00207 action *save_actions = new action[nactions];
00208 CoinMemcpyN(actions, nactions, save_actions);
00209 next = new slack_doubleton_action(nactions, save_actions, next);
00210
00211 if (nfixed_cols)
00212 next = make_fixed_action::presolve(prob, fixed_cols, nfixed_cols,
00213 true,
00214 next);
00215 }
00216 delete [] fixed_cols;
00217 return (next);
00218 }
00219
00220 void slack_doubleton_action::postsolve(CoinPostsolveMatrix *prob) const
00221 {
00222 const action *const actions = actions_;
00223 const int nactions = nactions_;
00224
00225 double *colels = prob->colels_;
00226 int *hrow = prob->hrow_;
00227 CoinBigIndex *mcstrt = prob->mcstrt_;
00228 int *hincol = prob->hincol_;
00229 int *link = prob->link_;
00230
00231
00232 double *clo = prob->clo_;
00233 double *cup = prob->cup_;
00234
00235 double *rlo = prob->rlo_;
00236 double *rup = prob->rup_;
00237
00238 double *sol = prob->sol_;
00239 double *rcosts = prob->rcosts_;
00240
00241 double *acts = prob->acts_;
00242 double *rowduals = prob->rowduals_;
00243
00244 unsigned char *colstat = prob->colstat_;
00245
00246
00247
00248 char *rdone = prob->rdone_;
00249 CoinBigIndex free_list = prob->free_list_;
00250
00251 const double ztolzb = prob->ztolzb_;
00252
00253 for (const action *f = &actions[nactions-1]; actions<=f; f--) {
00254 int irow = f->row;
00255 double lo0 = f->clo;
00256 double up0 = f->cup;
00257 double coeff = f->coeff;
00258 int jcol = f->col;
00259
00260 rlo[irow] = f->rlo;
00261 rup[irow] = f->rup;
00262
00263 clo[jcol] = lo0;
00264 cup[jcol] = up0;
00265
00266 acts[irow] = coeff * sol[jcol];
00267
00268
00269 {
00270 CoinBigIndex k = free_list;
00271 free_list = link[free_list];
00272
00273 check_free_list(free_list);
00274
00275 hrow[k] = irow;
00276 colels[k] = coeff;
00277 link[k] = mcstrt[jcol];
00278 mcstrt[jcol] = k;
00279 }
00280 hincol[jcol]++;
00281
00282
00283
00284
00285
00286
00287
00288
00289 if (!colstat) {
00290
00291 rowduals[irow] = 0.0;
00292 } else {
00293 if (prob->columnIsBasic(jcol)) {
00294
00295 prob->setRowStatus(irow,CoinPrePostsolveMatrix::basic);
00296
00297 rowduals[irow] = 0.0;
00298
00299
00300
00301
00302 } else if ((fabs(sol[jcol] - lo0) <= ztolzb &&
00303 rcosts[jcol] >= 0) ||
00304
00305 (fabs(sol[jcol] - up0) <= ztolzb &&
00306 rcosts[jcol] <= 0)) {
00307
00308 prob->setRowStatus(irow,CoinPrePostsolveMatrix::basic);
00309
00310 rowduals[irow] = 0.0;
00311
00312 } else if (! (fabs(sol[jcol] - lo0) <= ztolzb) &&
00313 ! (fabs(sol[jcol] - up0) <= ztolzb)) {
00314
00315
00316
00317
00318
00319 prob->setColumnStatus(jcol,CoinPrePostsolveMatrix::basic);
00320 prob->setRowStatusUsingValue(irow);
00321
00322
00323
00324 rowduals[irow] = rcosts[jcol] / coeff;
00325 rcosts[jcol] = 0.0;
00326
00327
00328
00329 } else {
00330
00331
00332 prob->setColumnStatus(jcol,CoinPrePostsolveMatrix::basic);
00333 prob->setRowStatusUsingValue(irow);
00334
00335
00336 rowduals[irow] = rcosts[jcol] / coeff;
00337 rcosts[jcol] = 0.0;
00338
00339
00340
00341 }
00342 }
00343
00344 rdone[irow] = SLACK_DOUBLETON;
00345 }
00346 prob->free_list_ = free_list;
00347 }
00348