Changeset 864
 Timestamp:
 Feb 4, 2008 10:16:50 AM (11 years ago)
 Location:
 trunk/Cbc/src
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

trunk/Cbc/src/CbcModel.cpp
r862 r864 7038 7038 } 7039 7039 int nTightened=0; 7040 #if 1 7041 if (!currentNode_(currentNode_>depth()&2)!=0) 7042 nTightened=tightenBounds(); 7043 if (nTightened) { 7044 //printf("%d bounds tightened\n",nTightened); 7045 if ((specialOptions_&1)!=0&&onOptimalPath) { 7046 const OsiRowCutDebugger *debugger = solver_>getRowCutDebugger() ; 7047 if (!debugger) { 7048 // tighten did something??? 7049 solver_>writeMps("infeas4"); 7050 printf("Not on optimalpath aaaa\n"); 7051 abort(); 7040 #ifdef COIN_HAS_CLP 7041 // Pierre pointed out that this is not valid for all solvers 7042 // so just do if Clp 7043 { 7044 OsiClpSolverInterface * clpSolver 7045 = dynamic_cast<OsiClpSolverInterface *> (solver_); 7046 if (clpSolver&&(!currentNode_(currentNode_>depth()&2)!=0)) 7047 nTightened=clpSolver>tightenBounds(); 7048 if (nTightened) { 7049 //printf("%d bounds tightened\n",nTightened); 7050 if ((specialOptions_&1)!=0&&onOptimalPath) { 7051 const OsiRowCutDebugger *debugger = solver_>getRowCutDebugger() ; 7052 if (!debugger) { 7053 // tighten did something??? 7054 solver_>writeMps("infeas4"); 7055 printf("Not on optimalpath aaaa\n"); 7056 abort(); 7057 } 7052 7058 } 7053 7059 } … … 9192 9198 setCutoff(saveCutoff); 9193 9199 return true; 9194 }9195 // Tighten bounds  lightweight9196 int9197 CbcModel::tightenBounds()9198 {9199 //CoinPackedMatrix matrixByRow(*solver_>getMatrixByRow());9200 int numberRows = solver_>getNumRows();9201 int numberColumns = solver_>getNumCols();9202 9203 int iRow,iColumn;9204 9205 // Row copy9206 //const double * elementByRow = matrixByRow.getElements();9207 //const int * column = matrixByRow.getIndices();9208 //const CoinBigIndex * rowStart = matrixByRow.getVectorStarts();9209 //const int * rowLength = matrixByRow.getVectorLengths();9210 9211 const double * columnUpper = solver_>getColUpper();9212 const double * columnLower = solver_>getColLower();9213 const double * rowUpper = solver_>getRowUpper();9214 const double * rowLower = solver_>getRowLower();9215 9216 // Column copy of matrix9217 const double * element = solver_>getMatrixByCol()>getElements();9218 const int * row = solver_>getMatrixByCol()>getIndices();9219 const CoinBigIndex * columnStart = solver_>getMatrixByCol()>getVectorStarts();9220 const int * columnLength = solver_>getMatrixByCol()>getVectorLengths();9221 const double *objective = solver_>getObjCoefficients() ;9222 double direction = solver_>getObjSense();9223 double * down = new double [numberRows];9224 double * up = new double [numberRows];9225 double * sum = new double [numberRows];9226 int * type = new int [numberRows];9227 CoinZeroN(down,numberRows);9228 CoinZeroN(up,numberRows);9229 CoinZeroN(sum,numberRows);9230 CoinZeroN(type,numberRows);9231 double infinity = solver_>getInfinity();9232 for (iColumn=0;iColumn<numberColumns;iColumn++) {9233 CoinBigIndex start = columnStart[iColumn];9234 CoinBigIndex end = start + columnLength[iColumn];9235 double lower = columnLower[iColumn];9236 double upper = columnUpper[iColumn];9237 if (lower==upper) {9238 for (CoinBigIndex j=start;j<end;j++) {9239 int iRow = row[j];9240 double value = element[j];9241 sum[iRow]+=2.0*fabs(value*lower);9242 if ((type[iRow]&1)==0)9243 down[iRow] += value*lower;9244 if ((type[iRow]&2)==0)9245 up[iRow] += value*lower;9246 }9247 } else {9248 for (CoinBigIndex j=start;j<end;j++) {9249 int iRow = row[j];9250 double value = element[j];9251 if (value>0.0) {9252 if ((type[iRow]&1)==0) {9253 if (lower!=infinity) {9254 down[iRow] += value*lower;9255 sum[iRow]+=fabs(value*lower);9256 } else {9257 type[iRow] = 1;9258 }9259 }9260 if ((type[iRow]&2)==0) {9261 if (upper!=infinity) {9262 up[iRow] += value*upper;9263 sum[iRow]+=fabs(value*upper);9264 } else {9265 type[iRow] = 2;9266 }9267 }9268 } else {9269 if ((type[iRow]&1)==0) {9270 if (upper!=infinity) {9271 down[iRow] += value*upper;9272 sum[iRow]+=fabs(value*upper);9273 } else {9274 type[iRow] = 1;9275 }9276 }9277 if ((type[iRow]&2)==0) {9278 if (lower!=infinity) {9279 up[iRow] += value*lower;9280 sum[iRow]+=fabs(value*lower);9281 } else {9282 type[iRow] = 2;9283 }9284 }9285 }9286 }9287 }9288 }9289 int nTightened=0;9290 double tolerance = 1.0e6;9291 for (iRow=0;iRow<numberRows;iRow++) {9292 if ((type[iRow]&1)!=0)9293 down[iRow]=infinity;9294 if (down[iRow]>rowUpper[iRow]) {9295 if (down[iRow]>rowUpper[iRow]+tolerance+1.0e8*sum[iRow]) {9296 // infeasible9297 #ifdef COIN_DEVELOP9298 printf("infeasible on row %d\n",iRow);9299 #endif9300 nTightened=1;9301 break;9302 } else {9303 down[iRow]=rowUpper[iRow];9304 }9305 }9306 if ((type[iRow]&2)!=0)9307 up[iRow]=infinity;9308 if (up[iRow]<rowLower[iRow]) {9309 if (up[iRow]<rowLower[iRow]tolerance1.0e8*sum[iRow]) {9310 // infeasible9311 #ifdef COIN_DEVELOP9312 printf("infeasible on row %d\n",iRow);9313 #endif9314 nTightened=1;9315 break;9316 } else {9317 up[iRow]=rowLower[iRow];9318 }9319 }9320 }9321 if (nTightened)9322 numberColumns=0; // so will skip9323 for (iColumn=0;iColumn<numberColumns;iColumn++) {9324 CoinBigIndex start = columnStart[iColumn];9325 CoinBigIndex end = start + columnLength[iColumn];9326 double lower = columnLower[iColumn];9327 double upper = columnUpper[iColumn];9328 double gap = upperlower;9329 if (!gap)9330 continue;9331 int canGo=0;9332 if (integerInfo_[iColumn]) {9333 if (lower!=floor(lower+0.5)) {9334 #ifdef COIN_DEVELOP9335 printf("increasing lower bound on %d from %g to %g\n",iColumn,9336 lower,ceil(lower));9337 #endif9338 lower=ceil(lower);9339 gap=upperlower;9340 solver_>setColLower(iColumn,lower);9341 }9342 if (upper!=floor(upper+0.5)) {9343 #ifdef COIN_DEVELOP9344 printf("decreasing upper bound on %d from %g to %g\n",iColumn,9345 upper,floor(upper));9346 #endif9347 upper=floor(upper);9348 gap=upperlower;9349 solver_>setColUpper(iColumn,upper);9350 }9351 double newLower=lower;9352 double newUpper=upper;9353 for (CoinBigIndex j=start;j<end;j++) {9354 int iRow = row[j];9355 double value = element[j];9356 if (value>0.0) {9357 if ((type[iRow]&1)==0) {9358 // has to be at most something9359 if (down[iRow] + value*gap > rowUpper[iRow]+tolerance) {9360 double newGap = (rowUpper[iRow]down[iRow])/value;9361 // adjust9362 newGap += 1.0e10*sum[iRow];9363 newGap = floor(newGap);9364 if (lower+newGap<newUpper)9365 newUpper=lower+newGap;9366 }9367 }9368 if (down[iRow]<rowLower[iRow])9369 canGo =1; // can't go down without affecting result9370 if ((type[iRow]&2)==0) {9371 // has to be at least something9372 if (up[iRow]  value*gap < rowLower[iRow]tolerance) {9373 double newGap = (up[iRow]rowLower[iRow])/value;9374 // adjust9375 newGap += 1.0e10*sum[iRow];9376 newGap = floor(newGap);9377 if (uppernewGap>newLower)9378 newLower=uppernewGap;9379 }9380 }9381 if (up[iRow]>rowUpper[iRow])9382 canGo =2; // can't go up without affecting result9383 } else {9384 if ((type[iRow]&1)==0) {9385 // has to be at least something9386 if (down[iRow]  value*gap > rowUpper[iRow]+tolerance) {9387 double newGap = (rowUpper[iRow]down[iRow])/value;9388 // adjust9389 newGap += 1.0e10*sum[iRow];9390 newGap = floor(newGap);9391 if (uppernewGap>newLower)9392 newLower=uppernewGap;9393 }9394 }9395 if (up[iRow]>rowUpper[iRow])9396 canGo =1; // can't go down without affecting result9397 if ((type[iRow]&2)==0) {9398 // has to be at most something9399 if (up[iRow] + value*gap < rowLower[iRow]tolerance) {9400 double newGap = (up[iRow]rowLower[iRow])/value;9401 // adjust9402 newGap += 1.0e10*sum[iRow];9403 newGap = floor(newGap);9404 if (lower+newGap<newUpper)9405 newUpper=lower+newGap;9406 }9407 }9408 if (down[iRow]<rowLower[iRow])9409 canGo =2; // can't go up without affecting result9410 }9411 }9412 if (newUpper<uppernewLower>lower) {9413 nTightened++;9414 if (newLower>newUpper) {9415 // infeasible9416 #if COIN_DEVELOP>19417 printf("infeasible on column %d\n",iColumn);9418 #endif9419 nTightened=1;9420 break;9421 } else {9422 solver_>setColLower(iColumn,newLower);9423 solver_>setColUpper(iColumn,newUpper);9424 }9425 for (CoinBigIndex j=start;j<end;j++) {9426 int iRow = row[j];9427 double value = element[j];9428 if (value>0.0) {9429 if ((type[iRow]&1)==0) {9430 down[iRow] += value*(newLowerlower);9431 }9432 if ((type[iRow]&2)==0) {9433 up[iRow] += value*(newUpperupper);9434 }9435 } else {9436 if ((type[iRow]&1)==0) {9437 down[iRow] += value*(newUpperupper);9438 }9439 if ((type[iRow]&2)==0) {9440 up[iRow] += value*(newLowerlower);9441 }9442 }9443 }9444 } else {9445 if (canGo!=3) {9446 double objValue = direction*objective[iColumn];9447 if (objValue>=0.0&&(canGo&1)==0) {9448 #if COIN_DEVELOP>19449 printf("dual fix down on column %d\n",iColumn);9450 #endif9451 nTightened++;;9452 solver_>setColUpper(iColumn,lower);9453 } else if (objValue<=0.0&&(canGo&2)==0) {9454 #if COIN_DEVELOP>19455 printf("dual fix up on column %d\n",iColumn);9456 #endif9457 nTightened++;;9458 solver_>setColLower(iColumn,upper);9459 }9460 }9461 }9462 } else {9463 // just do dual tests9464 for (CoinBigIndex j=start;j<end;j++) {9465 int iRow = row[j];9466 double value = element[j];9467 if (value>0.0) {9468 if (down[iRow]<rowLower[iRow])9469 canGo =1; // can't go down without affecting result9470 if (up[iRow]>rowUpper[iRow])9471 canGo =2; // can't go up without affecting result9472 } else {9473 if (up[iRow]>rowUpper[iRow])9474 canGo =1; // can't go down without affecting result9475 if (down[iRow]<rowLower[iRow])9476 canGo =2; // can't go up without affecting result9477 }9478 }9479 if (canGo!=3) {9480 double objValue = direction*objective[iColumn];9481 if (objValue>=0.0&&(canGo&1)==0) {9482 #if COIN_DEVELOP>19483 printf("dual fix down on continuous column %d\n",iColumn);9484 #endif9485 nTightened++;;9486 solver_>setColUpper(iColumn,lower);9487 } else if (objValue<=0.0&&(canGo&2)==0) {9488 #if COIN_DEVELOP>19489 printf("dual fix up on continuoe column %d\n",iColumn);9490 #endif9491 nTightened++;;9492 solver_>setColLower(iColumn,upper);9493 }9494 }9495 }9496 }9497 delete [] type;9498 delete [] down;9499 delete [] up;9500 delete [] sum;9501 return nTightened;9502 9200 } 9503 9201 /* 
trunk/Cbc/src/CbcModel.hpp
r862 r864 406 406 */ 407 407 void analyzeObjective(); 408 /// Tighten bounds  lightweight409 int tightenBounds();410 408 411 409
Note: See TracChangeset
for help on using the changeset viewer.