00001
00002
00003 #ifndef CoinPresolveMatrix_H
00004 #define CoinPresolveMatrix_H
00005
00006 #include "CoinPragma.hpp"
00007 #include "CoinPackedMatrix.hpp"
00008 #include "CoinMessage.hpp"
00009
00010 #include <cmath>
00011 #include <cassert>
00012 #include <cfloat>
00013 #include <cassert>
00014
00015 #if defined(_MSC_VER)
00016
00017
00018 #define deleteAction(array,type) delete [] ((type) array)
00019 #else
00020 #define deleteAction(array,type) delete [] array
00021 #endif
00022
00023
00024 class ClpSimplex;
00025 class OsiSolverInterface;
00026
00027
00028 const double ZTOLDP = 1e-12;
00029
00030 double *presolve_duparray(const double *d, int n, int n2);
00031 double *presolve_duparray(const double *d, int n);
00032 int *presolve_duparray(const int *d, int n, int n2);
00033 int *presolve_duparray(const int *d, int n);
00034 char *presolve_duparray(const char *d, int n, int n2);
00035 char *presolve_duparray(const char *d, int n);
00036
00037 double * presolve_duparray(const double * element, const int * index,
00038 int length, int offset);
00039
00040 void presolve_delete_from_row(int row, int col ,
00041 const CoinBigIndex *mrstrt,
00042 int *hinrow, int *hcol, double *dels);
00043
00044 int presolve_find_row(int row, CoinBigIndex kcs, CoinBigIndex kce, const int *hrow);
00045 int presolve_find_row1(int row, CoinBigIndex kcs, CoinBigIndex kce, const int *hrow);
00046
00047
00048
00049 #ifdef DEBUG_PRESOLVE
00050 inline void DIE(const char *s) { std::cout<<s; abort(); }
00051 #else
00052 inline void DIE(const char *s) {}
00053 #endif
00054
00055 #if DEBUG_PRESOLVE
00056 #define PRESOLVE_STMT(s) s
00057 #define PRESOLVEASSERT(x) ((x) ? 1 : ((std::cerr<< "FAILED ASSERTION at line "<< __LINE__ << ": " #x "\n"), abort(), 0))
00058 #else
00059 #define PRESOLVEASSERT(x) assert(x)
00060 #define PRESOLVE_STMT(s)
00061 #endif
00062
00063 struct dropped_zero {
00064 int row;
00065 int col;
00066 };
00067
00068 inline int ALIGN(int n, int m) { return (((n + m - 1) / m) * m); }
00069 inline int ALIGN_DOUBLE(int n) { return ALIGN(n,sizeof(double)); }
00070
00071 class CoinPostsolveMatrix;
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108 class CoinPresolveAction {
00109 public:
00110
00111
00112
00113
00114 static void throwCoinError(const char *error, const char *ps_routine);
00115
00116
00117
00118 const CoinPresolveAction *next;
00119
00120 CoinPresolveAction(const CoinPresolveAction *next) : next(next) {}
00121
00122
00123
00124 virtual const char *name() const = 0;
00125
00126
00127 virtual void postsolve(CoinPostsolveMatrix *prob) const = 0;
00128
00129 virtual ~CoinPresolveAction() {}
00130 };
00131
00132
00133
00134 class CoinPrePostsolveMatrix {
00135 public:
00136 CoinPrePostsolveMatrix(const ClpSimplex * si,
00137 int ncols_,
00138 int nrows_,
00139 CoinBigIndex nelems_);
00140 CoinPrePostsolveMatrix(const OsiSolverInterface * si,
00141 int ncols_,
00142 int nrows_,
00143 CoinBigIndex nelems_);
00144
00145
00146 ~CoinPrePostsolveMatrix();
00148 enum Status {
00149 isFree = 0x00,
00150 basic = 0x01,
00151 atUpperBound = 0x02,
00152 atLowerBound = 0x03,
00153 superBasic = 0x04
00154 };
00155 double *sol_;
00156 double *rowduals_;
00157 double *acts_;
00158
00159 double *rcosts_;
00160 unsigned char *colstat_;
00161 unsigned char *rowstat_;
00162
00163
00164
00165 double originalOffset_;
00166
00167 CoinMessageHandler * handler_;
00169 CoinMessages messages_;
00170
00171 inline CoinMessageHandler * messageHandler() const
00172 { return handler_; }
00174 inline CoinMessages messages() const
00175 { return messages_; }
00176
00177 int ncols_;
00178 const int ncols0_;
00179
00180 CoinBigIndex nelems_;
00181
00182 CoinBigIndex *mcstrt_;
00183 int *hincol_;
00184 int *hrow_;
00185 double *colels_;
00186
00187 double *cost_;
00188
00189 double *clo_;
00190 double *cup_;
00191 double *rlo_;
00192 double *rup_;
00193
00194
00195 int * originalColumn_;
00196
00197 int * originalRow_;
00198
00199 const double ztolzb_;
00200 const double ztoldj_;
00201
00202 double maxmin_;
00203
00204
00205
00206 inline void setRowStatus(int sequence, Status status)
00207 {
00208 unsigned char & st_byte = rowstat_[sequence];
00209 st_byte &= ~7;
00210 st_byte |= status;
00211 };
00212 inline Status getRowStatus(int sequence) const
00213 {return static_cast<Status> (rowstat_[sequence]&7);};
00214 inline bool rowIsBasic(int sequence) const
00215 {return (static_cast<Status> (rowstat_[sequence]&7)==basic);};
00216 inline void setColumnStatus(int sequence, Status status)
00217 {
00218 unsigned char & st_byte = colstat_[sequence];
00219 st_byte &= ~7;
00220 st_byte |= status;
00221 };
00222 inline Status getColumnStatus(int sequence) const
00223 {return static_cast<Status> (colstat_[sequence]&7);};
00224 inline bool columnIsBasic(int sequence) const
00225 {return (static_cast<Status> (colstat_[sequence]&7)==basic);};
00227 void setRowStatusUsingValue(int iRow);
00228 void setColumnStatusUsingValue(int iColumn);
00229
00230 };
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250 #define NO_LINK -66666666
00251
00252 #ifndef COIN_DBL_MAX
00253 #define COIN_DBL_MAX DBL_MAX
00254 #endif
00255 #define PRESOLVE_INF COIN_DBL_MAX
00256
00257 class presolvehlink {
00258 public:
00259 int pre, suc;
00260 };
00261
00262 static inline void PRESOLVE_REMOVE_LINK(presolvehlink *link, int i)
00263 {
00264 int ipre = link[i].pre;
00265 int isuc = link[i].suc;
00266 if (ipre >= 0) {
00267 link[ipre].suc = isuc;
00268 }
00269 if (isuc >= 0) {
00270 link[isuc].pre = ipre;
00271 }
00272 link[i].pre = NO_LINK, link[i].suc = NO_LINK;
00273 }
00274
00275
00276 static inline void PRESOLVE_INSERT_LINK(presolvehlink *link, int i, int pos)
00277 {
00278 int isuc = link[pos].suc;
00279 link[pos].suc = i;
00280 link[i].pre = pos;
00281 if (isuc >= 0) {
00282 link[isuc].pre = i;
00283 }
00284 link[i].suc = isuc;
00285 }
00286
00287
00288
00289
00290
00291
00292
00293
00294 static inline void PRESOLVE_MOVE_LINK(presolvehlink *link, int i, int j)
00295 {
00296 int ipre = link[i].pre;
00297 int isuc = link[i].suc;
00298 if (ipre >= 0) {
00299 link[ipre].suc = j;
00300 }
00301 if (isuc >= 0) {
00302 link[isuc].pre = j;
00303 }
00304 link[i].pre = NO_LINK, link[i].suc = NO_LINK;
00305 }
00306
00307
00308
00309
00310
00311
00312 static inline void check_free_list(int free_list)
00313 {
00314 assert (free_list>=0);
00315
00316
00317
00318
00319 }
00320
00321
00322
00323
00324 class CoinPresolveMatrix : public CoinPrePostsolveMatrix {
00325 public:
00326
00327 CoinPresolveMatrix(int ncols0,
00328 double maxmin,
00329
00330
00331 ClpSimplex * si,
00332
00333
00334 int nrows,
00335 CoinBigIndex nelems,
00336 bool doStatus,
00337 double nonLinearVariable);
00338
00339
00340 void update_model(ClpSimplex * si,
00341 int nrows0,
00342 int ncols0,
00343 CoinBigIndex nelems0);
00344 CoinPresolveMatrix(int ncols0,
00345 double maxmin,
00346
00347
00348 OsiSolverInterface * si,
00349
00350
00351 int nrows,
00352 CoinBigIndex nelems,
00353 bool doStatus,
00354 double nonLinearVariable);
00355
00356
00357 void update_model(OsiSolverInterface * si,
00358 int nrows0,
00359 int ncols0,
00360 CoinBigIndex nelems0);
00361
00362 ~CoinPresolveMatrix();
00363
00364 presolvehlink *clink_;
00365 presolvehlink *rlink_;
00366
00367 double dobias_;
00368
00369
00370 int nrows_;
00371 CoinBigIndex *mrstrt_;
00372 int *hinrow_;
00373 double *rowels_;
00374 int *hcol_;
00375
00376 char *integerType_;
00377
00378 double feasibilityTolerance_;
00379
00380 int status_;
00381
00382
00383
00384
00385 unsigned char * rowChanged_;
00386
00387 int * rowsToDo_;
00388 int numberRowsToDo_;
00389
00390 int * nextRowsToDo_;
00391 int numberNextRowsToDo_;
00392
00393 bool anyProhibited_;
00394
00395 inline bool rowChanged(int i) const {
00396 return (rowChanged_[i]&1)!=0;
00397 }
00398 inline void setRowChanged(int i) {
00399 rowChanged_[i] |= 1;
00400 }
00401 inline void addRow(int i) {
00402 if ((rowChanged_[i]&1)==0) {
00403 rowChanged_[i] |= 1;
00404 nextRowsToDo_[numberNextRowsToDo_++] = i;
00405 }
00406 }
00407 inline void unsetRowChanged(int i) {
00408 rowChanged_[i] &= ~1;;
00409 }
00410
00411 inline bool anyProhibited() const
00412 { return anyProhibited_;};
00413
00414 inline bool rowProhibited(int i) const {
00415 return (rowChanged_[i]&2)!=0;
00416 }
00417
00418 inline bool rowProhibited2(int i) const {
00419 if (!anyProhibited_)
00420 return false;
00421 else
00422 return (rowChanged_[i]&2)!=0;
00423 }
00424 inline void setRowProhibited(int i) {
00425 rowChanged_[i] |= 2;
00426 }
00427
00428 inline bool rowUsed(int i) const {
00429 return (rowChanged_[i]&4)!=0;
00430 }
00431 inline void setRowUsed(int i) {
00432 rowChanged_[i] |= 4;
00433 }
00434 inline void unsetRowUsed(int i) {
00435 rowChanged_[i] &= ~4;;
00436 }
00437
00438
00439
00440 unsigned char * colChanged_;
00441
00442 int * colsToDo_;
00443 int numberColsToDo_;
00444
00445 int * nextColsToDo_;
00446 int numberNextColsToDo_;
00447
00448 inline bool colChanged(int i) const {
00449 return (colChanged_[i]&1)!=0;
00450 }
00451 inline void setColChanged(int i) {
00452 colChanged_[i] |= 1;
00453 }
00454 inline void addCol(int i) {
00455 if ((colChanged_[i]&1)==0) {
00456 colChanged_[i] |= 1;
00457 nextColsToDo_[numberNextColsToDo_++] = i;
00458 }
00459 }
00460 inline void unsetColChanged(int i) {
00461 colChanged_[i] &= ~1;;
00462 }
00463
00464 inline bool colProhibited(int i) const {
00465 return (colChanged_[i]&2)!=0;
00466 }
00467
00468 inline bool colProhibited2(int i) const {
00469 if (!anyProhibited_)
00470 return false;
00471 else
00472 return (colChanged_[i]&2)!=0;
00473 }
00474 inline void setColProhibited(int i) {
00475 colChanged_[i] |= 2;
00476 }
00477
00478 inline bool colUsed(int i) const {
00479 return (colChanged_[i]&4)!=0;
00480 }
00481 inline void setColUsed(int i) {
00482 colChanged_[i] |= 4;
00483 }
00484 inline void unsetColUsed(int i) {
00485 colChanged_[i] &= ~4;;
00486 }
00487 void consistent(bool testvals = true);
00488
00489 inline void change_bias(double change_amount);
00490
00491
00492 int pass_;
00493
00494 };
00495
00496
00497
00498
00499 class CoinPostsolveMatrix : public CoinPrePostsolveMatrix {
00500 public:
00501
00502 CoinPostsolveMatrix(ClpSimplex * si,
00503
00504 int ncols0,
00505 int nrows0,
00506 CoinBigIndex nelems0,
00507
00508 double maxmin_,
00509
00510
00511 double *sol,
00512 double *acts,
00513
00514 unsigned char *colstat,
00515 unsigned char *rowstat);
00516
00517 CoinPostsolveMatrix(OsiSolverInterface * si,
00518
00519 int ncols0,
00520 int nrows0,
00521 CoinBigIndex nelems0,
00522
00523 double maxmin_,
00524
00525
00526 double *sol,
00527 double *acts,
00528
00529 unsigned char *colstat,
00530 unsigned char *rowstat);
00531
00532
00533 ~CoinPostsolveMatrix();
00534
00535 CoinBigIndex free_list_;
00536 int maxlink_;
00537 int *link_;
00538
00539
00540 char *cdone_;
00541 char *rdone_;
00542 int nrows_;
00543
00544
00545 int nrows0_;
00546
00547
00548
00549 void check_nbasic();
00550
00552 };
00553
00554 void CoinPresolveMatrix::change_bias(double change_amount)
00555 {
00556 dobias_ += change_amount;
00557 #if DEBUG_PRESOLVE
00558 assert(fabs(change_amount)<1.0e50);
00559 #endif
00560 if (change_amount)
00561 PRESOLVE_STMT(printf("changing bias by %g to %g\n",
00562 change_amount, dobias_));
00563 }
00564
00565
00566 inline void swap(int &x, int &y) { int temp = x; x = y; y = temp; }
00567 inline void swap(double &x, double &y) { double temp = x; x = y; y = temp; }
00568 inline void swap(long &x, long &y) { long temp = x; x = y; y = temp; }
00569
00570 inline void swap(int *&x, int *&y) { int *temp = x; x = y; y = temp; }
00571 inline void swap(double *&x, double *&y) { double *temp = x; x = y; y = temp; }
00572
00573
00574 template <class T> inline T*
00575 copyOfArray( const T * array, const int size, T value)
00576 {
00577 T * arrayNew = new T[size];
00578 if (array) {
00579 memcpy(arrayNew,array,size*sizeof(T));
00580 } else {
00581 int i;
00582 for (i=0;i<size;i++)
00583 arrayNew[i] = value;
00584 }
00585 return arrayNew;
00586 }
00587
00588
00589 template <class T> inline T*
00590 copyOfArray( const T * array, const int size)
00591 {
00592 if (array) {
00593 T * arrayNew = new T[size];
00594 memcpy(arrayNew,array,size*sizeof(T));
00595 return arrayNew;
00596 } else {
00597 return NULL;
00598 }
00599 }
00600 #define PRESOLVEFINITE(n) (-PRESOLVE_INF < (n) && (n) < PRESOLVE_INF)
00601 int presolve_find_row2(int irow, CoinBigIndex ks, int nc, const int *hrow, const int *link);
00602 void presolve_make_memlists(CoinBigIndex *starts, int *lengths,
00603 presolvehlink *link,
00604 int n);
00605 int presolve_find_row3(int irow, CoinBigIndex ks, int nc, const int *hrow, const int *link);
00606 void presolve_delete_from_row(int row, int col ,
00607 const CoinBigIndex *mrstrt,
00608 int *hinrow, int *hcol, double *dels);
00609 void presolve_delete_from_row2(int row, int col ,
00610 CoinBigIndex *mrstrt,
00611 int *hinrow, int *hcol, double *dels, int *link, CoinBigIndex *free_listp);
00612 #endif