00001
00002
00003
00004
00005
00006 #include <stdio.h>
00007
00008 #include <assert.h>
00009 #include <iostream>
00010
00011 #include "CoinHelperFunctions.hpp"
00012
00013 #include "CoinPresolveMatrix.hpp"
00014 void CoinPresolveAction::throwCoinError(const char *error,
00015 const char *ps_routine)
00016 {
00017 throw CoinError(error, ps_routine, "CoinPresolve");
00018 }
00019
00020
00021 class presolvehlink;
00022
00023 void presolve_make_memlists(CoinBigIndex *starts, int *lengths,
00024 presolvehlink *link,
00025 int n);
00026
00027 void presolve_prefix(const int *starts, int *diffs, int n, int limit);
00028
00029 void presolve_prefix(const CoinBigIndex *starts, int *diffs, int n, int limit)
00030 {
00031 int i;
00032
00033 for (i=0; i<n; i++) {
00034 diffs[i] = starts[i+1] - starts[i];
00035 }
00036 }
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047 void presolve_make_memlists(CoinBigIndex *starts, int *lengths, presolvehlink *link, int n)
00048 {
00049 int i;
00050 int pre = NO_LINK;
00051
00052 for (i=0; i<n; i++) {
00053 if (lengths[i]) {
00054 link[i].pre = pre;
00055 if (pre != NO_LINK)
00056 link[pre].suc = i;
00057 pre = i;
00058 }
00059 else {
00060 link[i].pre = NO_LINK;
00061 link[i].suc = NO_LINK;
00062 }
00063 }
00064 if (pre != NO_LINK)
00065 link[pre].suc = n;
00066
00067
00068 link[n].pre = pre;
00069
00070 link[n].suc = NO_LINK;
00071 }
00072
00073
00074 double * presolve_duparray(const double * element, const int * index,
00075 int length, int offset)
00076 {
00077 int n;
00078 if (sizeof(double)==2*sizeof(int))
00079 n = (3*length+1)>>1;
00080 else
00081 n = 2*length;
00082 double * dArray = new double [n];
00083 int * iArray = (int *) (dArray+length);
00084 memcpy(dArray,element+offset,length*sizeof(double));
00085 memcpy(iArray,index+offset,length*sizeof(int));
00086 return dArray;
00087 }
00088
00089
00090 double *presolve_duparray(const double *d, int n, int n2)
00091 {
00092 double *d1 = new double[n2];
00093 memcpy(d1, d, n*sizeof(double));
00094 return (d1);
00095 }
00096 double *presolve_duparray(const double *d, int n)
00097 {
00098 return presolve_duparray(d, n, n);
00099 }
00100
00101 int *presolve_duparray(const int *d, int n, int n2)
00102 {
00103 int *d1 = new int[n2];
00104 memcpy(d1, d, n*sizeof(int));
00105 return (d1);
00106 }
00107 int *presolve_duparray(const int *d, int n)
00108 {
00109 return presolve_duparray(d, n, n);
00110 }
00111
00112 char *presolve_duparray(const char *d, int n, int n2)
00113 {
00114 char *d1 = new char[n2];
00115 memcpy(d1, d, n*sizeof(char));
00116 return (d1);
00117 }
00118 char *presolve_duparray(const char *d, int n)
00119 {
00120 return presolve_duparray(d, n, n);
00121 }
00122
00123 #if 0
00124 double *presolve_duparray(const double *d, int n, char **end_mmapp)
00125 {
00126 double *d1 = (double*)*end_mmapp;
00127 memcpy(d1, d, n*sizeof(double));
00128 *end_mmapp += ALIGN_DOUBLE(n*sizeof(double));
00129 return (d1);
00130 }
00131 int *presolve_duparray(const int *d, int n, char **end_mmapp)
00132 {
00133 int *d1 = (int*)*end_mmapp;
00134 memcpy(d1, d, n*sizeof(int));
00135 *end_mmapp += ALIGN_DOUBLE(n*sizeof(int));
00136 return (d1);
00137 }
00138
00139 double *presolve_duparray(const double *d, int n, int n2, char **end_mmapp)
00140 {
00141 double *d1 = (double*)*end_mmapp;
00142 memcpy(d1, d, n*sizeof(double));
00143 *end_mmapp += ALIGN_DOUBLE(n2*sizeof(double));
00144 return (d1);
00145 }
00146 int *presolve_duparray(const int *d, int n, int n2, char **end_mmapp)
00147 {
00148 int *d1 = (int*)*end_mmapp;
00149 memcpy(d1, d, n*sizeof(int));
00150 *end_mmapp += ALIGN_DOUBLE(n2*sizeof(int));
00151 return (d1);
00152 }
00153 #endif
00154
00155
00156 int presolve_find_row(int row, CoinBigIndex kcs, CoinBigIndex kce, const int *hrow)
00157 {
00158 CoinBigIndex k;
00159 for (k=kcs; k<kce; k++)
00160 if (hrow[k] == row)
00161 return (k);
00162 DIE("FIND_ROW");
00163 return (0);
00164 }
00165
00166 int presolve_find_row1(int row, CoinBigIndex kcs, CoinBigIndex kce, const int *hrow)
00167 {
00168 CoinBigIndex k;
00169 for (k=kcs; k<kce; k++)
00170 if (hrow[k] == row)
00171 return (k);
00172 return (kce);
00173 }
00174
00175 int presolve_find_row2(int irow, CoinBigIndex ks, int nc, const int *hrow, const int *link)
00176 {
00177 for (int i=0; i<nc; ++i) {
00178 if (hrow[ks] == irow)
00179 return (ks);
00180 ks = link[ks];
00181 }
00182 abort();
00183 return -1;
00184 }
00185
00186 int presolve_find_row3(int irow, CoinBigIndex ks, int nc, const int *hrow, const int *link)
00187 {
00188 for (int i=0; i<nc; ++i) {
00189 if (hrow[ks] == irow)
00190 return (ks);
00191 ks = link[ks];
00192 }
00193 return (-1);
00194 }
00195
00196
00197
00198
00199
00200 void presolve_delete_from_row(int row, int col ,
00201 const CoinBigIndex *mrstrt,
00202 int *hinrow, int *hcol, double *dels)
00203 {
00204 CoinBigIndex krs = mrstrt[row];
00205 CoinBigIndex kre = krs + hinrow[row];
00206
00207 CoinBigIndex kcol = presolve_find_row(col, krs, kre, hcol);
00208
00209 swap(hcol[kcol], hcol[kre-1]);
00210 swap(dels[kcol], dels[kre-1]);
00211 hinrow[row]--;
00212 }
00213
00214
00215 void presolve_delete_from_row2(int row, int col ,
00216 CoinBigIndex *mrstrt,
00217 int *hinrow, int *hcol, double *dels, int *link,
00218 CoinBigIndex *free_listp)
00219 {
00220 CoinBigIndex k = mrstrt[row];
00221
00222 if (hcol[k] == col) {
00223 mrstrt[row] = link[k];
00224 link[k] = *free_listp;
00225 *free_listp = k;
00226 check_free_list(k);
00227 hinrow[row]--;
00228 } else {
00229 int n = hinrow[row] - 1;
00230 CoinBigIndex k0 = k;
00231 k = link[k];
00232 for (int i=0; i<n; ++i) {
00233 if (hcol[k] == col) {
00234 link[k0] = link[k];
00235 link[k] = *free_listp;
00236 *free_listp = k;
00237 check_free_list(k);
00238 hinrow[row]--;
00239 return;
00240 }
00241 k0 = k;
00242 k = link[k];
00243 }
00244 abort();
00245 }
00246 }
00247
00248
00249
00250 CoinPrePostsolveMatrix::~CoinPrePostsolveMatrix()
00251 {
00252 delete[]mcstrt_;
00253 delete[]hrow_;
00254 delete[]colels_;
00255 delete[]hincol_;
00256
00257 delete[]cost_;
00258 delete[]clo_;
00259 delete[]cup_;
00260 delete[]rlo_;
00261 delete[]rup_;
00262 delete[]originalColumn_;
00263 delete[]originalRow_;
00264 delete[]rowduals_;
00265
00266 delete[]rcosts_;
00267 }
00268
00269
00270 void
00271 CoinPrePostsolveMatrix::setRowStatusUsingValue(int iRow)
00272 {
00273 double value = acts_[iRow];
00274 double lower = rlo_[iRow];
00275 double upper = rup_[iRow];
00276 if (lower<-1.0e20&&upper>1.0e20) {
00277 setRowStatus(iRow,isFree);
00278 } else if (fabs(lower-value)<=ztolzb_) {
00279 setRowStatus(iRow,atLowerBound);
00280 } else if (fabs(upper-value)<=ztolzb_) {
00281 setRowStatus(iRow,atUpperBound);
00282 } else {
00283 setRowStatus(iRow,superBasic);
00284 }
00285 }
00286 void
00287 CoinPrePostsolveMatrix::setColumnStatusUsingValue(int iColumn)
00288 {
00289 double value = sol_[iColumn];
00290 double lower = clo_[iColumn];
00291 double upper = cup_[iColumn];
00292 if (lower<-1.0e20&&upper>1.0e20) {
00293 setColumnStatus(iColumn,isFree);
00294 } else if (fabs(lower-value)<=ztolzb_) {
00295 setColumnStatus(iColumn,atLowerBound);
00296 } else if (fabs(upper-value)<=ztolzb_) {
00297 setColumnStatus(iColumn,atUpperBound);
00298 } else {
00299 setColumnStatus(iColumn,superBasic);
00300 }
00301 }
00302
00303
00304 #if DEBUG_PRESOLVE
00305 static void matrix_bounds_ok(const double *lo, const double *up, int n)
00306 {
00307 int i;
00308 for (i=0; i<n; i++) {
00309 PRESOLVEASSERT(lo[i] <= up[i]);
00310 PRESOLVEASSERT(lo[i] < PRESOLVE_INF);
00311 PRESOLVEASSERT(-PRESOLVE_INF < up[i]);
00312 }
00313 }
00314 #endif
00315
00316
00317 CoinPresolveMatrix::~CoinPresolveMatrix()
00318 {
00319 delete[]clink_;
00320 delete[]rlink_;
00321
00322 delete[]mrstrt_;
00323 delete[]hinrow_;
00324 delete[]rowels_;
00325 delete[]hcol_;
00326
00327 delete[]integerType_;
00328 delete[] rowChanged_;
00329 delete[] rowsToDo_;
00330 delete[] nextRowsToDo_;
00331 delete[] colChanged_;
00332 delete[] colsToDo_;
00333 delete[] nextColsToDo_;
00334 }
00335
00336 #if CHECK_CONSISTENCY
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352 static void matrix_consistent(const CoinBigIndex *mrstrt, const int *hinrow, const int *hcol,
00353 const CoinBigIndex *mcstrt, const int *hincol, const int *hrow,
00354 const double *rowels,
00355 const double *colels,
00356 int nrows, int testvals,
00357 const char *ROW, const char *COL)
00358 {
00359 for (int irow=0; irow<nrows; irow++) {
00360 if (hinrow[irow] > 0) {
00361 CoinBigIndex krs = mrstrt[irow];
00362 CoinBigIndex kre = krs + hinrow[irow];
00363
00364 for (CoinBigIndex k=krs; k<kre; k++) {
00365 int jcol = hcol[k];
00366 CoinBigIndex kcs = mcstrt[jcol];
00367 CoinBigIndex kce = kcs + hincol[jcol];
00368
00369 CoinBigIndex kk = presolve_find_row1(irow, kcs, kce, hrow);
00370 if (kk == kce) {
00371 printf("MATRIX INCONSISTENT: can't find %s %d in %s %d\n",
00372 ROW, irow, COL, jcol);
00373 fflush(stdout);
00374 abort();
00375 }
00376 if (testvals && colels[kk] != rowels[k]) {
00377 printf("MATRIX INCONSISTENT: value for %s %d and %s %d\n",
00378 ROW, irow, COL, jcol);
00379 fflush(stdout);
00380 abort();
00381 }
00382 }
00383 }
00384 }
00385 }
00386 #endif
00387
00388
00389 void CoinPresolveMatrix::consistent(bool testvals)
00390 {
00391 #if CHECK_CONSISTENCY
00392 matrix_consistent(mrstrt_, hinrow_, hcol_,
00393 mcstrt_, hincol_, hrow_,
00394 rowels_, colels_,
00395 nrows_, testvals,
00396 "row", "col");
00397 matrix_consistent(mcstrt_, hincol_, hrow_,
00398 mrstrt_, hinrow_, hcol_,
00399 colels_, rowels_,
00400 ncols_, testvals,
00401 "col", "row");
00402 #endif
00403 }
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00416
00417
00418 CoinPostsolveMatrix::~CoinPostsolveMatrix()
00419 {
00420 delete[]link_;
00421
00422 delete[]cdone_;
00423 delete[]rdone_;
00424 }
00425
00426
00427 void CoinPostsolveMatrix::check_nbasic()
00428 {
00429 int nbasic = 0;
00430
00431 int i;
00432 for (i=0; i<ncols_; i++)
00433 if (columnIsBasic(i))
00434 nbasic++;
00435
00436 for (i=0; i<nrows_; i++)
00437 if (rowIsBasic(i))
00438 nbasic++;
00439
00440 if (nbasic != nrows_) {
00441 printf("WRONG NUMBER NBASIC: is: %d should be: %d\n",
00442 nbasic, nrows_);
00443 fflush(stdout);
00444 }
00445 }
00446
00447
00448
00449
00450
00451