00001
00002
00003
00004 #include <stdio.h>
00005 #include <math.h>
00006
00007 #include "CoinPresolveMatrix.hpp"
00008 #include "CoinPresolveFixed.hpp"
00009
00010 const char *remove_fixed_action::name() const
00011 {
00012 return ("remove_fixed_action");
00013 }
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 const remove_fixed_action *remove_fixed_action::presolve(CoinPresolveMatrix *prob,
00026 int *fcols,
00027 int nfcols,
00028 const CoinPresolveAction *next)
00029 {
00030 double *colels = prob->colels_;
00031 int *hrow = prob->hrow_;
00032 CoinBigIndex *mcstrt = prob->mcstrt_;
00033 int *hincol = prob->hincol_;
00034
00035 double *rowels = prob->rowels_;
00036 int *hcol = prob->hcol_;
00037 CoinBigIndex *mrstrt = prob->mrstrt_;
00038 int *hinrow = prob->hinrow_;
00039
00040
00041 double *clo = prob->clo_;
00042
00043 double *rlo = prob->rlo_;
00044 double *rup = prob->rup_;
00045 double *acts = prob->acts_;
00046
00047
00048
00049 presolvehlink *clink = prob->clink_;
00050
00051 action *actions = new action[nfcols+1];
00052
00053 int size=0;
00054 int ckc;
00055 for ( ckc=0; ckc<nfcols; ckc++) {
00056 int j = fcols[ckc];
00057 size += hincol[j];
00058 }
00059 double * els_action = new double[size];
00060 int * rows_action = new int[size];
00061 actions[nfcols].start=size;
00062 size=0;
00063
00064 for ( ckc=0; ckc<nfcols; ckc++) {
00065 int j = fcols[ckc];
00066
00067 double sol = clo[j];
00068 CoinBigIndex kcs = mcstrt[j];
00069 CoinBigIndex kce = kcs + hincol[j];
00070 CoinBigIndex k;
00071
00072 {
00073 action &f = actions[ckc];
00074
00075 f.col = j;
00076 f.sol = sol;
00077
00078 f.start = size;
00079
00080 }
00081
00082
00083
00084 for (k=kcs; k<kce; k++) {
00085 int row = hrow[k];
00086 double coeff = colels[k];
00087
00088 els_action[size]=coeff;
00089 rows_action[size++]=row;
00090
00091 rlo[row] -= sol * coeff;
00092 rup[row] -= sol * coeff;
00093 acts[row] -= sol * coeff;
00094
00095
00096 presolve_delete_from_row(row, j, mrstrt, hinrow, hcol, rowels);
00097
00098
00099 prob->addRow(row);
00100 CoinBigIndex krs = mrstrt[row];
00101 CoinBigIndex kre = krs + hinrow[row];
00102 for (CoinBigIndex k=krs; k<kre; k++) {
00103 int jcol = hcol[k];
00104 prob->addCol(jcol);
00105 }
00106
00107 PRESOLVE_REMOVE_LINK(clink, j);
00108 hincol[j] = 0;
00109 }
00110 }
00111 #if PRESOLVE_SUMMARY
00112 printf("NFIXED: %d\n", nfcols);
00113 #endif
00114
00115 #if 0
00116 remove_fixed_action * nextAction = new
00117 remove_fixed_action(nfcols, actions, next);
00118 delete [] (void *) actions;
00119 return nextAction;
00120 #else
00121 return (new remove_fixed_action(nfcols, actions, els_action,rows_action,next));
00122 #endif
00123 }
00124
00125 remove_fixed_action::remove_fixed_action(int nactions,
00126 action *actions,
00127 double * els_action,
00128 int * rows_action,
00129 const CoinPresolveAction *next) :
00130 CoinPresolveAction(next),
00131 colrows_(rows_action),
00132 colels_(els_action),
00133 nactions_(nactions),
00134 actions_(actions)
00135 {
00136 }
00137 remove_fixed_action::~remove_fixed_action()
00138 {
00139 deleteAction(actions_,action*);
00140 delete [] colels_;
00141 delete [] colrows_;
00142 }
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160 void remove_fixed_action::postsolve(CoinPostsolveMatrix *prob) const
00161 {
00162 action * actions = actions_;
00163 const int nactions = nactions_;
00164
00165 double *colels = prob->colels_;
00166 int *hrow = prob->hrow_;
00167 CoinBigIndex *mcstrt = prob->mcstrt_;
00168 int *hincol = prob->hincol_;
00169 int *link = prob->link_;
00170
00171 CoinBigIndex free_list = prob->free_list_;
00172
00173 double *clo = prob->clo_;
00174 double *cup = prob->cup_;
00175 double *rlo = prob->rlo_;
00176 double *rup = prob->rup_;
00177
00178 double *sol = prob->sol_;
00179 double *dcost = prob->cost_;
00180 double *rcosts = prob->rcosts_;
00181
00182 double *acts = prob->acts_;
00183 double *rowduals = prob->rowduals_;
00184
00185 unsigned char *colstat = prob->colstat_;
00186
00187
00188 const double maxmin = prob->maxmin_;
00189
00190 char *cdone = prob->cdone_;
00191
00192 double * els_action = colels_;
00193 int * rows_action = colrows_;
00194 int end = actions[nactions].start;
00195
00196 for (const action *f = &actions[nactions-1]; actions<=f; f--) {
00197 int icol = f->col;
00198 const double thesol = f->sol;
00199
00200 cdone[icol] = FIXED_VARIABLE;
00201
00202 sol[icol] = thesol;
00203 clo[icol] = thesol;
00204 cup[icol] = thesol;
00205
00206 int cs = -11111;
00207 int start = f->start;
00208 double dj = maxmin * dcost[icol];
00209
00210 for (int i=start; i<end; ++i) {
00211 int row = rows_action[i];
00212 double coeff =els_action[i];
00213
00214
00215 CoinBigIndex k = free_list;
00216 free_list = link[free_list];
00217
00218 check_free_list(free_list);
00219
00220
00221 hrow[k] = row;
00222 colels[k] = coeff;
00223 link[k] = cs;
00224 cs = k;
00225
00226 if (-PRESOLVE_INF < rlo[row])
00227 rlo[row] += coeff * thesol;
00228 if (rup[row] < PRESOLVE_INF)
00229 rup[row] += coeff * thesol;
00230 acts[row] += coeff * thesol;
00231
00232 dj -= rowduals[row] * coeff;
00233 }
00234 mcstrt[icol] = cs;
00235
00236 rcosts[icol] = dj;
00237 hincol[icol] = end-start;
00238 end=start;
00239
00240
00241
00242
00243
00244
00245
00246 if (colstat)
00247 prob->setColumnStatus(icol,CoinPrePostsolveMatrix::atUpperBound);
00248 }
00249
00250 prob->free_list_ = free_list;
00251 }
00252
00253
00254 const CoinPresolveAction *remove_fixed(CoinPresolveMatrix *prob,
00255 const CoinPresolveAction *next)
00256 {
00257 int ncols = prob->ncols_;
00258 int *fcols = new int[ncols];
00259 int nfcols = 0;
00260
00261 int *hincol = prob->hincol_;
00262
00263 double *clo = prob->clo_;
00264 double *cup = prob->cup_;
00265
00266 for (int i=0; i<ncols; i++)
00267 if (hincol[i] > 0 && clo[i] == cup[i]&&!prob->colProhibited2(i))
00268 fcols[nfcols++] = i;
00269
00270 next = remove_fixed_action::presolve(prob, fcols, nfcols, next);
00271 delete[]fcols;
00272 return (next);
00273 }
00274
00275
00276
00277 const char *make_fixed_action::name() const
00278 {
00279 return ("make_fixed_action");
00280 }
00281
00282 const CoinPresolveAction *make_fixed_action::presolve(CoinPresolveMatrix *prob,
00283 int *fcols,
00284 int nfcols,
00285 bool fix_to_lower,
00286 const CoinPresolveAction *next)
00287 {
00288 double *clo = prob->clo_;
00289 double *cup = prob->cup_;
00290 double *csol = prob->sol_;
00291
00292 double *colels = prob->colels_;
00293 int *hrow = prob->hrow_;
00294 CoinBigIndex *mcstrt = prob->mcstrt_;
00295 int *hincol = prob->hincol_;
00296
00297 double *acts = prob->acts_;
00298
00299
00300 action *actions = new action[nfcols];
00301
00302 for (int ckc=0; ckc<nfcols; ckc++) {
00303 int j = fcols[ckc];
00304 double movement;
00305
00306 action &f = actions[ckc];
00307
00308 if (fix_to_lower) {
00309 f.bound = cup[j];
00310 cup[j] = clo[j];
00311 movement = clo[j]-csol[j];
00312 csol[j] = clo[j];
00313 } else {
00314 f.bound = clo[j];
00315 clo[j] = cup[j];
00316 movement = cup[j]-csol[j];
00317 csol[j] = cup[j];
00318 }
00319 if (movement) {
00320 CoinBigIndex k;
00321 for (k=mcstrt[j];k<mcstrt[j]+hincol[j];k++) {
00322 int row = hrow[k];
00323 acts[row] += movement*colels[k];
00324 }
00325 }
00326 }
00327
00328
00329
00330
00331 return (new make_fixed_action(nfcols, actions, fix_to_lower,
00332 remove_fixed_action::presolve(prob,
00333 fcols, nfcols,
00334 0),
00335 next));
00336 }
00337
00338 void make_fixed_action::postsolve(CoinPostsolveMatrix *prob) const
00339 {
00340 const action *const actions = actions_;
00341
00342 const bool fix_to_lower = fix_to_lower_;
00343
00344 double *clo = prob->clo_;
00345 double *cup = prob->cup_;
00346
00347 faction_->postsolve(prob);
00348
00349 for (int cnt = faction_->nactions_-1; cnt>=0; cnt--) {
00350 const action *f = &actions[cnt];
00351 const remove_fixed_action::action *f1 = &faction_->actions_[cnt];
00352
00353 int icol = f1->col;
00354 if (fix_to_lower) {
00355 cup[icol] = f->bound;
00356 } else {
00357 clo[icol] = f->bound;
00358 }
00359 }
00360 }
00361
00362
00363 const CoinPresolveAction *make_fixed(CoinPresolveMatrix *prob,
00364 const CoinPresolveAction *next)
00365 {
00366 int ncols = prob->ncols_;
00367 int *fcols = new int[ncols];
00368 int nfcols = 0;
00369
00370 int *hincol = prob->hincol_;
00371
00372 double *clo = prob->clo_;
00373 double *cup = prob->cup_;
00374
00375 for (int i=0; i<ncols; i++)
00376 if (hincol[i] > 0 && fabs(cup[i] - clo[i]) < ZTOLDP&&!prob->colProhibited2(i))
00377 fcols[nfcols++] = i;
00378
00379
00380 next = make_fixed_action::presolve(prob, fcols, nfcols,
00381 true,
00382 next);
00383 delete[]fcols;
00384 return (next);
00385 }
00386
00387