00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "CouennePrecisions.hpp"
00012 #include "CouenneSolverInterface.hpp"
00013
00014
00015
00016
00017
00018 int CouenneSolverInterface::tightenBoundsCLP (int lightweight) {
00019
00020
00021
00022 int
00023 numberRows = getNumRows(),
00024 numberColumns = getNumCols(),
00025 iRow, iColumn;
00026
00027 const double * columnUpper = getColUpper();
00028 const double * columnLower = getColLower();
00029 const double * rowUpper = getRowUpper();
00030 const double * rowLower = getRowLower();
00031
00032
00033 const double * element = getMatrixByCol()->getElements();
00034 const int * row = getMatrixByCol()->getIndices();
00035 const CoinBigIndex * columnStart = getMatrixByCol()->getVectorStarts();
00036 const int * columnLength = getMatrixByCol()->getVectorLengths();
00037 const double *objective = getObjCoefficients() ;
00038
00039 double direction = getObjSense();
00040 double * down = new double [numberRows];
00041
00042 if (lightweight)
00043 return tightenBoundsCLP_Light (lightweight);
00044
00045
00046
00047 double * up = new double [numberRows];
00048 double * sum = new double [numberRows];
00049 int * type = new int [numberRows];
00050 CoinZeroN(down,numberRows);
00051 CoinZeroN(up,numberRows);
00052 CoinZeroN(sum,numberRows);
00053 CoinZeroN(type,numberRows);
00054 double infinity = getInfinity();
00055
00056 for (iColumn=0;iColumn<numberColumns;iColumn++) {
00057 CoinBigIndex start = columnStart[iColumn];
00058 CoinBigIndex end = start + columnLength[iColumn];
00059 double lower = columnLower[iColumn];
00060 double upper = columnUpper[iColumn];
00061 if (lower==upper) {
00062 for (CoinBigIndex j=start;j<end;j++) {
00063 int iRow = row[j];
00064 double value = element[j];
00065 sum[iRow]+=2.0*fabs(value*lower);
00066 if ((type[iRow]&1)==0)
00067 down[iRow] += value*lower;
00068 if ((type[iRow]&2)==0)
00069 up[iRow] += value*lower;
00070 }
00071 } else {
00072 for (CoinBigIndex j=start;j<end;j++) {
00073 int iRow = row[j];
00074 double value = element[j];
00075 if (value>0.0) {
00076 if ((type[iRow]&1)==0) {
00077 if (lower!=-infinity) {
00078 down[iRow] += value*lower;
00079 sum[iRow]+=fabs(value*lower);
00080 } else {
00081 type[iRow] |= 1;
00082 }
00083 }
00084 if ((type[iRow]&2)==0) {
00085 if (upper!=infinity) {
00086 up[iRow] += value*upper;
00087 sum[iRow]+=fabs(value*upper);
00088 } else {
00089 type[iRow] |= 2;
00090 }
00091 }
00092 } else {
00093 if ((type[iRow]&1)==0) {
00094 if (upper!=infinity) {
00095 down[iRow] += value*upper;
00096 sum[iRow]+=fabs(value*upper);
00097 } else {
00098 type[iRow] |= 1;
00099 }
00100 }
00101 if ((type[iRow]&2)==0) {
00102 if (lower!=-infinity) {
00103 up[iRow] += value*lower;
00104 sum[iRow]+=fabs(value*lower);
00105 } else {
00106 type[iRow] |= 2;
00107 }
00108 }
00109 }
00110 }
00111 }
00112 }
00113
00114 int nTightened = 0;
00115 double tolerance = 1.0e-6;
00116
00117 for (iRow=0;iRow<numberRows;iRow++) {
00118 if ((type[iRow]&1)!=0)
00119 down[iRow]=-infinity;
00120 if (down[iRow]>rowUpper[iRow]) {
00121 if (down[iRow]>rowUpper[iRow]+tolerance+1.0e-8*sum[iRow]) {
00122
00123 #ifdef COIN_DEVELOP
00124 printf("infeasible on row %d\n",iRow);
00125 #endif
00126 nTightened=-1;
00127 break;
00128 } else {
00129 down[iRow]=rowUpper[iRow];
00130 }
00131 }
00132 if ((type[iRow]&2)!=0)
00133 up[iRow]=infinity;
00134 if (up[iRow]<rowLower[iRow]) {
00135 if (up[iRow]<rowLower[iRow]-tolerance-1.0e-8*sum[iRow]) {
00136
00137 #ifdef COIN_DEVELOP
00138 printf("infeasible on row %d\n",iRow);
00139 #endif
00140 nTightened=-1;
00141 break;
00142 } else {
00143 up[iRow]=rowLower[iRow];
00144 }
00145 }
00146 }
00147
00148 if (nTightened)
00149 numberColumns = 0;
00150
00151 for (iColumn=0;iColumn<numberColumns;iColumn++) {
00152 double lower = columnLower[iColumn];
00153 double upper = columnUpper[iColumn];
00154 double gap = upper-lower;
00155
00156 if (!gap)
00157 continue;
00158
00159 int canGo=0;
00160
00161 CoinBigIndex
00162 start = columnStart [iColumn],
00163 end = start + columnLength [iColumn];
00164
00165 if (lower < -1.0e8 && upper > 1.0e8)
00166 continue;
00167
00168
00169
00170
00171
00172
00173 {
00174 if (integerInformation_ && integerInformation_ [iColumn]) {
00175
00176 if (lower < ceil (lower - COUENNE_EPS) - COUENNE_EPS) {
00177 #ifdef COIN_DEVELOP
00178 printf("increasing lower bound on %d from %e to %e\n",iColumn,
00179 lower,ceil(lower - COUENNE_EPS));
00180 #endif
00181 lower=ceil(lower - COUENNE_EPS);
00182 gap=upper-lower;
00183 setColLower(iColumn,lower);
00184 }
00185
00186 if (upper > floor(upper + COUENNE_EPS) + COUENNE_EPS) {
00187 #ifdef COIN_DEVELOP
00188 printf("decreasing upper bound on %d from %e to %e\n",iColumn,
00189 upper,floor(upper + COUENNE_EPS));
00190 #endif
00191 upper=floor(upper + COUENNE_EPS);
00192 gap=upper-lower;
00193 setColUpper(iColumn,upper);
00194 }
00195 }
00196
00197 double newLower=lower;
00198 double newUpper=upper;
00199
00200 for (CoinBigIndex j=start;j<end;j++) {
00201 int iRow = row[j];
00202 double value = element[j];
00203 if (value>0.0) {
00204 if ((type[iRow]&1)==0) {
00205
00206 if (down[iRow] + value*gap > rowUpper[iRow]+tolerance) {
00207 double newGap = (rowUpper[iRow]-down[iRow])/value;
00208
00209 newGap += 1.0e-10*sum[iRow];
00210 if (integerInformation_ && integerInformation_ [iColumn])
00211 newGap = floor(newGap);
00212 if (lower+newGap<newUpper)
00213 newUpper=lower+newGap;
00214 }
00215 }
00216 if (down[iRow]<rowLower[iRow])
00217 canGo |=1;
00218 if ((type[iRow]&2)==0) {
00219
00220 if (up[iRow] - value*gap < rowLower[iRow]-tolerance) {
00221 double newGap = (up[iRow]-rowLower[iRow])/value;
00222
00223 newGap += 1.0e-10*sum[iRow];
00224 if (integerInformation_ && integerInformation_ [iColumn])
00225 newGap = floor(newGap);
00226 if (upper-newGap>newLower)
00227 newLower=upper-newGap;
00228 }
00229 }
00230 if (up[iRow]>rowUpper[iRow])
00231 canGo |=2;
00232 } else {
00233 if ((type[iRow]&1)==0) {
00234
00235 if (down[iRow] - value*gap > rowUpper[iRow]+tolerance) {
00236 double newGap = -(rowUpper[iRow]-down[iRow])/value;
00237
00238 newGap += 1.0e-10*sum[iRow];
00239 if (integerInformation_ && integerInformation_ [iColumn])
00240 newGap = floor(newGap);
00241 if (upper-newGap>newLower)
00242 newLower=upper-newGap;
00243 }
00244 }
00245 if (up[iRow]>rowUpper[iRow])
00246 canGo |=1;
00247 if ((type[iRow]&2)==0) {
00248
00249 if (up[iRow] + value*gap < rowLower[iRow]-tolerance) {
00250 double newGap = -(up[iRow]-rowLower[iRow])/value;
00251
00252 newGap += 1.0e-10*sum[iRow];
00253 if (integerInformation_ && integerInformation_ [iColumn])
00254 newGap = floor(newGap);
00255 if (lower+newGap<newUpper)
00256 newUpper=lower+newGap;
00257 }
00258 }
00259 if (down[iRow]<rowLower[iRow])
00260 canGo |=2;
00261 }
00262 }
00263
00264 if (newUpper<upper || newLower>lower) {
00265 nTightened++;
00266 if (newLower>newUpper) {
00267
00268 #if COIN_DEVELOP>1
00269 printf("infeasible on column %d\n",iColumn);
00270 #endif
00271 nTightened=-1;
00272 break;
00273 } else {
00274 setColLower(iColumn,newLower);
00275 setColUpper(iColumn,newUpper);
00276 }
00277 for (CoinBigIndex j=start;j<end;j++) {
00278 int iRow = row[j];
00279 double value = element[j];
00280 if (value>0.0) {
00281 if ((type[iRow]&1)==0) down [iRow] += value*(newLower-lower);
00282 if ((type[iRow]&2)==0) up [iRow] += value*(newUpper-upper);
00283 } else {
00284 if ((type[iRow]&1)==0) down [iRow] += value*(newUpper-upper);
00285 if ((type[iRow]&2)==0) up [iRow] += value*(newLower-lower);
00286 }
00287 }
00288 } else {
00289
00290 if (canGo!=3) {
00291
00292 double objValue = direction*objective[iColumn];
00293
00294 if (objValue>=0.0&&(canGo&1)==0) {
00295 #if COIN_DEVELOP>2
00296 printf("dual fix down on column %d\n",iColumn);
00297 #endif
00298 nTightened++;
00299 setColUpper(iColumn,lower);
00300 } else if (objValue<=0.0 && (canGo&2)==0) {
00301 #if COIN_DEVELOP>2
00302 printf("dual fix up on column %d\n",iColumn);
00303 #endif
00304 nTightened++;
00305 setColLower(iColumn,upper);
00306 }
00307 }
00308 }
00309 }
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354 }
00355
00356 delete [] type;
00357 delete [] down;
00358 delete [] up;
00359 delete [] sum;
00360
00361 return nTightened;
00362 }
00363