00001
00002
00003
00004 #include <stdio.h>
00005 #include <math.h>
00006
00007 #include "CoinHelperFunctions.hpp"
00008 #include "CoinPresolveMatrix.hpp"
00009 #include "CoinPresolveZeros.hpp"
00010
00011
00012
00013
00014
00015 static int drop_col_zeros(int ncheckcols, int *checkcols,
00016 const CoinBigIndex *mcstrt, double *colels, int *hrow,
00017 int *hincol,
00018 dropped_zero *actions)
00019 {
00020 typedef dropped_zero action;
00021 int nactions = 0;
00022 int i;
00023
00024 for (i=0; i<ncheckcols; i++) {
00025 int col = checkcols[i];
00026 CoinBigIndex kcs = mcstrt[col];
00027 CoinBigIndex kce = mcstrt[col] + hincol[col];
00028 CoinBigIndex k;
00029
00030 for (k=kcs; k<kce; ++k) {
00031 if (fabs(colels[k]) < ZTOLDP) {
00032 actions[nactions].col = col;
00033 actions[nactions].row = hrow[k];
00034 nactions++;
00035
00036 #if DEBUG_PRESOLVE
00037 if (nactions == 1)
00038 printf("ZEROS: ");
00039 printf("(%d,%d) ", hrow[k], col);
00040 #endif
00041
00042 colels[k] = colels[kce-1];
00043 hrow[k] = hrow[kce-1];
00044 kce--;
00045 hincol[col]--;
00046
00047 --k;
00048 }
00049 }
00050 }
00051
00052 #if DEBUG_PRESOLVE
00053 if (nactions)
00054 printf("\n");
00055 #endif
00056
00057 return (nactions);
00058 }
00059
00060
00061
00062 void drop_row_zeros(int nzeros, const dropped_zero *zeros,
00063 const CoinBigIndex *mcstrt, double *colels, int *hrow,
00064 int *hincol)
00065 {
00066 int i;
00067 for (i=0; i<nzeros; i++) {
00068 int col = zeros[i].row;
00069 CoinBigIndex kcs = mcstrt[col];
00070 CoinBigIndex kce = mcstrt[col] + hincol[col];
00071 CoinBigIndex k;
00072
00073 for (k=kcs; k<kce; k++) {
00074 if (fabs(colels[k]) < ZTOLDP) {
00075 colels[k] = colels[kce-1];
00076 hrow[k] = hrow[kce-1];
00077 kce--;
00078 hincol[col]--;
00079
00080 --k;
00081 }
00082 }
00083 }
00084 }
00085
00086
00087 const CoinPresolveAction *drop_zero_coefficients_action::presolve(CoinPresolveMatrix *prob,
00088 int *checkcols,
00089 int ncheckcols,
00090 const CoinPresolveAction *next)
00091 {
00092 double *colels = prob->colels_;
00093 int *hrow = prob->hrow_;
00094 CoinBigIndex *mcstrt = prob->mcstrt_;
00095 int *hincol = prob->hincol_;
00096 int ncols = prob->ncols_;
00097 int nrows = prob->nrows_;
00098
00099
00100 dropped_zero * zeros = new dropped_zero[ncols+nrows];
00101
00102 int nzeros = drop_col_zeros(ncheckcols, checkcols,
00103 mcstrt, colels, hrow, hincol,
00104 zeros);
00105
00106 if (nzeros == 0) {
00107 delete [] zeros;
00108 return (next);
00109 } else {
00110 double *rowels = prob->rowels_;
00111 int *hcol = prob->hcol_;
00112 CoinBigIndex *mrstrt = prob->mrstrt_;
00113 int *hinrow = prob->hinrow_;
00114
00115
00116 #if PRESOLVE_SUMMARY
00117 printf("NZEROS: %d\n", nzeros);
00118 #endif
00119
00120
00121 drop_row_zeros(nzeros, zeros, mrstrt, rowels, hcol, hinrow);
00122
00123 dropped_zero *zeros1 = new dropped_zero[nzeros];
00124 CoinMemcpyN(zeros, nzeros, zeros1);
00125
00126 delete [] zeros;
00127 return (new drop_zero_coefficients_action(nzeros, zeros1, next));
00128 }
00129 }
00130
00131
00132 const CoinPresolveAction *drop_zero_coefficients(CoinPresolveMatrix *prob,
00133 const CoinPresolveAction *next)
00134 {
00135 int ncheck = prob->ncols_;
00136 int *checkcols = new int[ncheck];
00137
00138 if (!prob->anyProhibited()) {
00139 for (int i=0; i<ncheck; i++)
00140 checkcols[i] = i;
00141 } else {
00142
00143 ncheck=0;
00144 for (int i=0; i<prob->ncols_; i++)
00145 if (!prob->colProhibited(i))
00146 checkcols[ncheck++] = i;
00147 }
00148
00149 const CoinPresolveAction *retval = drop_zero_coefficients_action::presolve(prob,
00150 checkcols, ncheck,
00151 next);
00152 delete[]checkcols;
00153 return (retval);
00154 }
00155
00156 void drop_zero_coefficients_action::postsolve(CoinPostsolveMatrix *prob) const
00157 {
00158 const int nzeros = nzeros_;
00159 const dropped_zero *const zeros = zeros_;
00160
00161 double *colels = prob->colels_;
00162 int *hrow = prob->hrow_;
00163 CoinBigIndex *mcstrt = prob->mcstrt_;
00164 int *hincol = prob->hincol_;
00165 int *link = prob->link_;
00166 CoinBigIndex free_list = prob->free_list_;
00167
00168 for (const dropped_zero *z = &zeros[nzeros-1]; zeros<=z; z--) {
00169 int irow = z->row;
00170 int jcol = z->col;
00171
00172 {
00173 CoinBigIndex k = free_list;
00174 free_list = link[free_list];
00175 check_free_list(free_list);
00176
00177 hrow[k] = irow;
00178 colels[k] = 0.0;
00179 link[k] = mcstrt[jcol];
00180 mcstrt[jcol] = k;
00181 }
00182
00183 hincol[jcol]++;
00184 }
00185
00186 prob->free_list_ = free_list;
00187 }