00001
00002
00003
00004 #if defined(_MSC_VER)
00005
00006 # pragma warning(disable:4786)
00007 #endif
00008 #include <cstdlib>
00009 #include <cstdio>
00010 #include <cmath>
00011 #include <cfloat>
00012 #include <cassert>
00013 #include <iostream>
00014
00015 #include "CoinHelperFunctions.hpp"
00016 #include "CoinPackedVector.hpp"
00017 #include "CoinPackedMatrix.hpp"
00018 #include "CoinFinite.hpp"
00019 #include "OsiRowCutDebugger.hpp"
00020 #include "CglProbing.hpp"
00021
00022 typedef struct {double infeasibility;int sequence;} double_int_pair;
00023 class double_int_pair_compare {
00024 public:
00025 bool operator() (double_int_pair x , double_int_pair y) const
00026 {
00027 return ( x.infeasibility < y.infeasibility);
00028 }
00029 };
00030
00031 #ifdef CGL_DEBUG
00032
00033 static void checkBounds(const OsiRowCutDebugger * debugger,OsiColCut & cut)
00034 {
00035 if (debugger) {
00036
00037 const double * optimal = debugger->optimalSolution();
00038 int i;
00039 int nIndex;
00040 const double * values;
00041 const int * index;
00042 const CoinPackedVector & lbs = cut.lbs();
00043 values = lbs.getElements();
00044 nIndex = lbs.getNumElements();
00045 index = lbs.getIndices();
00046 for (i=0;i<nIndex;i++) {
00047 double value=values[i];
00048 int iColumn = index[i];
00049 printf("%d optimal %g lower %g\n",iColumn,optimal[iColumn],value);
00050 assert(value<=optimal[iColumn]+1.0e-5);
00051 }
00052 const CoinPackedVector & ubs = cut.ubs();
00053 values = ubs.getElements();
00054 nIndex = ubs.getNumElements();
00055 index = ubs.getIndices();
00056 for (i=0;i<nIndex;i++) {
00057 double value=values[i];
00058 int iColumn = index[i];
00059 printf("%d optimal %g upper %g\n",iColumn,optimal[iColumn],value);
00060 assert(value>=optimal[iColumn]-1.0e-5);
00061 }
00062 }
00063 }
00064 #endif
00065
00066
00067 static int tighten(double *colLower, double * colUpper,
00068 const int *column, const double *rowElements,
00069 const int *rowStart, const int * rowLength,
00070 double *rowLower, double *rowUpper,
00071 int nRows,int nCols,char * intVar,int maxpass,
00072 double tolerance)
00073 {
00074 int i, j, k, kre;
00075 int krs;
00076 int dolrows;
00077 int iflagu, iflagl;
00078 int ntotal=0,nchange=1,jpass=0;
00079 double dmaxup, dmaxdown, dbound;
00080 int ninfeas=0;
00081
00082 while(nchange) {
00083 int ilbred = 0;
00084 int iubred = 0;
00085 int nrwdrp = 0;
00086 if (jpass==maxpass) break;
00087 jpass++;
00088 dolrows = (jpass & 1) == 1;
00089
00090 for (i = 0; i < nRows; ++i) {
00091 if (rowLower[i]>-1.0e20||rowUpper[i]<1.0e20) {
00092 iflagu = 0;
00093 iflagl = 0;
00094 dmaxup = 0.0;
00095 dmaxdown = 0.0;
00096 krs = rowStart[i];
00097 kre = rowStart[i]+rowLength[i];
00098
00099
00100
00101
00102 for (k = krs; k < kre; ++k) {
00103 double value=rowElements[k];
00104 j = column[k];
00105 if (value > 0.0) {
00106 if (colUpper[j] >= 1e15) {
00107 dmaxup = 1e31;
00108 ++iflagu;
00109 } else {
00110 dmaxup += colUpper[j] * value;
00111 }
00112 if (colLower[j] <= -1e15) {
00113 dmaxdown = -1e31;
00114 ++iflagl;
00115 } else {
00116 dmaxdown += colLower[j] * value;
00117 }
00118 } else if (value<0.0) {
00119 if (colUpper[j] >= 1e15) {
00120 dmaxdown = -1e31;
00121 ++iflagl;
00122 } else {
00123 dmaxdown += colUpper[j] * value;
00124 }
00125 if (colLower[j] <= -1e15) {
00126 dmaxup = 1e31;
00127 ++iflagu;
00128 } else {
00129 dmaxup += colLower[j] * value;
00130 }
00131 }
00132 }
00133 if (dmaxup <= rowUpper[i] + tolerance && dmaxdown >= rowLower[i] - tolerance) {
00134
00135
00136
00137
00138
00139
00140
00141
00142 ++nrwdrp;
00143 rowLower[i]=-DBL_MAX;
00144 rowUpper[i]=DBL_MAX;
00145 } else {
00146 if (dmaxup < rowLower[i] -tolerance || dmaxdown > rowUpper[i]+tolerance) {
00147 ninfeas++;
00148 break;
00149 }
00150
00151
00152
00153
00154 if (iflagu == 0 && rowLower[i] > 0.0 && iflagl == 0 && rowUpper[i] < 1e15)
00155 {
00156 if (dolrows) {
00157 iflagu = 1;
00158 } else {
00159 iflagl = 1;
00160 }
00161 }
00162 if (iflagu == 0 && rowLower[i] > -1e15) {
00163 for (k = krs; k < kre; ++k) {
00164 double value=rowElements[k];
00165 j = column[k];
00166 if (value > 0.0) {
00167 if (colUpper[j] < 1e15) {
00168 dbound = colUpper[j] + (rowLower[i] - dmaxup) / value;
00169 if (dbound > colLower[j] + 1.0e-12) {
00170
00171
00172 colLower[j] = dbound;
00173 ++ilbred;
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188 if (colUpper[j] - colLower[j] <= tolerance) {
00189
00190
00191
00192 if (colUpper[j] - colLower[j] < -100.0*tolerance) {
00193 ninfeas++;
00194 }
00195 }
00196 }
00197 }
00198 } else {
00199 if (colLower[j] > -1e15) {
00200 dbound = colLower[j] + (rowLower[i] - dmaxup) / value;
00201 if (dbound < colUpper[j] - 1.0e-12) {
00202 colUpper[j] = dbound;
00203 ++iubred;
00204 if (colUpper[j] - colLower[j] <= tolerance) {
00205
00206
00207
00208 if (colUpper[j] - colLower[j] < -100.0*tolerance) {
00209 ninfeas++;
00210 }
00211 }
00212 }
00213 }
00214 }
00215 }
00216 }
00217
00218
00219
00220
00221 if (iflagl == 0 && rowUpper[i] < 1e15) {
00222 for (k = krs; k < kre; ++k) {
00223 double value=rowElements[k];
00224 j = column[k];
00225 if (value < 0.0) {
00226 if (colUpper[j] < 1e15) {
00227 dbound = colUpper[j] + (rowUpper[i] - dmaxdown) / value;
00228 if (dbound > colLower[j] + 1.0e-12) {
00229 colLower[j] = dbound;
00230 ++ilbred;
00231 if (! (colUpper[j] - colLower[j] > tolerance)) {
00232
00233
00234
00235 if (colUpper[j] - colLower[j] < -100.0*tolerance) {
00236 ninfeas++;
00237 }
00238 }
00239 }
00240 }
00241 } else {
00242 if (colLower[j] > -1e15) {
00243 dbound = colLower[j] + (rowUpper[i] - dmaxdown) / value;
00244 if (dbound < colUpper[j] - 1.0e-12) {
00245 colUpper[j] = dbound;
00246 ++iubred;
00247 if (! (colUpper[j] - colLower[j] > tolerance)) {
00248
00249
00250
00251 if (colUpper[j] - colLower[j] < -100.0*tolerance) {
00252 ninfeas++;
00253 }
00254 }
00255 }
00256 }
00257 }
00258 }
00259 }
00260 }
00261 }
00262 }
00263 for (j = 0; j < nCols; ++j) {
00264 if (intVar[j]) {
00265 if (colUpper[j]-colLower[j]>1.0e-8) {
00266 if (floor(colUpper[j]+1.0e-4)<colUpper[j])
00267 nchange++;
00268
00269 colUpper[j]=floor(colUpper[j]+1.0e-4);
00270 if (ceil(colLower[j]-1.0e-4)>colLower[j])
00271 nchange++;
00272
00273 colLower[j]=ceil(colLower[j]-1.0e-4);
00274 if (colUpper[j]<colLower[j]) {
00275
00276 ninfeas++;
00277 }
00278 }
00279 }
00280 }
00281 nchange=ilbred+iubred+nrwdrp;
00282 ntotal += nchange;
00283 if (ninfeas) break;
00284 }
00285 return (ninfeas);
00286 }
00287
00288 static void tighten2(double *colLower, double * colUpper,
00289 const int *column, const double *rowElements,
00290 const int *rowStart, const int * rowLength,
00291 double *rowLower, double *rowUpper,
00292 double * minR, double * maxR, int * markR,
00293 int nRows,int nCols)
00294 {
00295 int i, j, k, kre;
00296 int krs;
00297 int iflagu, iflagl;
00298 double dmaxup, dmaxdown, value;
00299
00300 for (i = 0; i < nRows; ++i) {
00301 if (rowLower[i]>-1.0e20||rowUpper[i]<1.0e20) {
00302 iflagu = 0;
00303 iflagl = 0;
00304 dmaxup = 0.0;
00305 dmaxdown = 0.0;
00306 krs = rowStart[i];
00307 kre = rowStart[i]+rowLength[i];
00308
00309
00310
00311
00312 for (k = krs; k < kre; ++k) {
00313 value=rowElements[k];
00314 j = column[k];
00315 if (value > 0.0) {
00316 if (colUpper[j] >= 1e15) {
00317 dmaxup = 1e31;
00318 ++iflagu;
00319 } else {
00320 dmaxup += colUpper[j] * value;
00321 }
00322 if (colLower[j] <= -1e15) {
00323 dmaxdown = -1e31;
00324 ++iflagl;
00325 } else {
00326 dmaxdown += colLower[j] * value;
00327 }
00328 } else if (value<0.0) {
00329 if (colUpper[j] >= 1e15) {
00330 dmaxdown = -1e31;
00331 ++iflagl;
00332 } else {
00333 dmaxdown += colUpper[j] * value;
00334 }
00335 if (colLower[j] <= -1e15) {
00336 dmaxup = 1e31;
00337 ++iflagu;
00338 } else {
00339 dmaxup += colLower[j] * value;
00340 }
00341 }
00342 }
00343 if (iflagu)
00344 maxR[i]=1.0e60;
00345 else
00346 maxR[i]=dmaxup;
00347 if (iflagl)
00348 minR[i]=-1.0e60;
00349 else
00350 minR[i]=dmaxdown;
00351 if (minR[i]<-1.0e10&&maxR[i]>1.0e10) {
00352 markR[i]=-2;
00353 } else {
00354 markR[i]=-1;
00355 }
00356 } else {
00357 minR[i]=-1.0e60;
00358 maxR[i]=1.0e60;
00359 markR[i]=-2;
00360 }
00361 }
00362 }
00363 #ifdef CGL_DEBUG
00364 static int nPath=0;
00365 #endif
00366
00367
00368
00369 void CglProbing::generateCuts(const OsiSolverInterface & si,
00370 OsiCuts & cs ) const
00371 {
00372 #ifdef CGL_DEBUG
00373 const OsiRowCutDebugger * debugger = si.getRowCutDebugger();
00374 if (debugger&&debugger->onOptimalPath(si)) {
00375 printf("On optimal path %d\n",nPath);
00376 nPath++;
00377 int nCols=si.getNumCols();
00378 int i;
00379 const double * solution = si.getColSolution();
00380 const double * lower = si.getColLower();
00381 const double * upper = si.getColUpper();
00382 const double * optimal = debugger->optimalSolution();
00383 const double * objective = si.getObjCoefficients();
00384 double objval1=0.0,objval2=0.0;
00385 for (i=0;i<nCols;i++) {
00386 printf("%d %g %g %g %g\n",i,lower[i],solution[i],upper[i],optimal[i]);
00387 objval1 += solution[i]*objective[i];
00388 objval2 += optimal[i]*objective[i];
00389 assert(optimal[i]>=lower[i]&&optimal[i]<=upper[i]);
00390 }
00391 printf("current obj %g, integer %g\n",objval1,objval2);
00392 }
00393 #endif
00394 int nRows=si.getNumRows();
00395 double * rowLower = new double[nRows+1];
00396 double * rowUpper = new double[nRows+1];
00397
00398 int nCols=si.getNumCols();
00399 double * colLower = new double[nCols];
00400 double * colUpper = new double[nCols];
00401
00402 int ninfeas=gutsOfGenerateCuts(si,cs,rowLower,rowUpper,colLower,colUpper);
00403 if (ninfeas) {
00404
00405 OsiRowCut rc;
00406 rc.setLb(DBL_MAX);
00407 rc.setUb(0.0);
00408 cs.insert(rc);
00409 #ifdef CGL_DEBUG
00410 const OsiRowCutDebugger * debugger = si.getRowCutDebugger();
00411 if (debugger&&debugger->onOptimalPath(si))
00412 assert(!debugger->invalidCut(rc));
00413 #endif
00414 }
00415 delete [] rowLower;
00416 delete [] rowUpper;
00417 delete [] colLower;
00418 delete [] colUpper;
00419 }
00420 int CglProbing::generateCutsAndModify(const OsiSolverInterface & si,
00421 OsiCuts & cs )
00422 {
00423 #ifdef CGL_DEBUG
00424 const OsiRowCutDebugger * debugger = si.getRowCutDebugger();
00425 if (debugger&&debugger->onOptimalPath(si)) {
00426 printf("On optimal path %d\n",nPath);
00427 nPath++;
00428 int nCols=si.getNumCols();
00429 int i;
00430 const double * solution = si.getColSolution();
00431 const double * lower = si.getColLower();
00432 const double * upper = si.getColUpper();
00433 const double * optimal = debugger->optimalSolution();
00434 const double * objective = si.getObjCoefficients();
00435 double objval1=0.0,objval2=0.0;
00436 for (i=0;i<nCols;i++) {
00437 printf("%d %g %g %g %g\n",i,lower[i],solution[i],upper[i],optimal[i]);
00438 objval1 += solution[i]*objective[i];
00439 objval2 += optimal[i]*objective[i];
00440 assert(optimal[i]>=lower[i]&&optimal[i]<=upper[i]);
00441 }
00442 printf("current obj %g, integer %g\n",objval1,objval2);
00443 }
00444 #endif
00445 int saveMode = mode_;
00446 if (!mode_)
00447 mode_=1;
00448 int nRows=si.getNumRows();
00449 double * rowLower = new double[nRows+1];
00450 double * rowUpper = new double[nRows+1];
00451
00452 int nCols=si.getNumCols();
00453 double * colLower = new double[nCols];
00454 double * colUpper = new double[nCols];
00455
00456 int ninfeas=gutsOfGenerateCuts(si,cs,rowLower,rowUpper,colLower,colUpper);
00457 if (ninfeas) {
00458
00459 OsiRowCut rc;
00460 rc.setLb(DBL_MAX);
00461 rc.setUb(0.0);
00462 cs.insert(rc);
00463 #ifdef CGL_DEBUG
00464 const OsiRowCutDebugger * debugger = si.getRowCutDebugger();
00465 if (debugger&&debugger->onOptimalPath(si))
00466 assert(!debugger->invalidCut(rc));
00467 #endif
00468 }
00469
00470 mode_=saveMode;
00471
00472 delete [] rowLower_;
00473 delete [] rowUpper_;
00474 delete [] colLower_;
00475 delete [] colUpper_;
00476 rowLower_ = rowLower;
00477 rowUpper_ = rowUpper;
00478 colLower_ = colLower;
00479 colUpper_ = colUpper;
00480 return ninfeas;
00481 }
00482 int CglProbing::gutsOfGenerateCuts(const OsiSolverInterface & si,
00483 OsiCuts & cs ,
00484 double * rowLower, double * rowUpper,
00485 double * colLower, double * colUpper) const
00486 {
00487
00488 int nRows;
00489
00490 CoinPackedMatrix * rowCopy=NULL;
00491
00492
00493 double cutoff;
00494 si.getDblParam(OsiDualObjectiveLimit,cutoff);
00495 cutoff *= si.getObjSense();
00496 if (fabs(cutoff)>1.0e30)
00497 assert (cutoff>1.0e30);
00498 int mode=mode_;
00499
00500 int nCols=si.getNumCols();
00501
00502
00503 char * intVar = new char[nCols];
00504 int i;
00505 int numberIntegers=0;
00506 for (i=0;i<nCols;i++) {
00507 if (si.isInteger(i)) {
00508 intVar[i]=1;
00509 numberIntegers++;
00510 } else {
00511 intVar[i]=0;
00512 }
00513 }
00514
00515 int ninfeas=0;
00516
00517
00518 if (!numberRows_) {
00519
00520 nRows=si.getNumRows();
00521
00522
00523 if (mode==0)
00524 mode=1;
00525 rowCopy = new CoinPackedMatrix(*si.getMatrixByRow());
00526
00527 if (cutoff<1.0e30&&usingObjective_) {
00528 int * columns = new int[nCols];
00529 double * elements = new double[nCols];
00530 int n=0;
00531 const double * objective = si.getObjCoefficients();
00532 bool maximize = (si.getObjSense()==-1);
00533 for (i=0;i<nCols;i++) {
00534 if (objective[i]) {
00535 elements[n]= (maximize) ? -objective[i] : objective[i];
00536 columns[n++]=i;
00537 }
00538 }
00539 rowCopy->appendRow(n,columns,elements);
00540 delete [] columns;
00541 delete [] elements;
00542 memcpy(rowLower,si.getRowLower(),nRows*sizeof(double));
00543 memcpy(rowUpper,si.getRowUpper(),nRows*sizeof(double));
00544 rowLower[nRows]=-DBL_MAX;
00545 rowUpper[nRows]=cutoff;
00546 nRows++;
00547 } else {
00548 memcpy(rowLower,si.getRowLower(),nRows*sizeof(double));
00549 memcpy(rowUpper,si.getRowUpper(),nRows*sizeof(double));
00550 }
00551 memcpy(colLower,si.getColLower(),nCols*sizeof(double));
00552 memcpy(colUpper,si.getColUpper(),nCols*sizeof(double));
00553 } else {
00554
00555 nRows=numberRows_;
00556 assert(nCols==numberColumns_);
00557
00558 rowCopy = rowCopy_;
00559 rowLower = new double[nRows];
00560 rowUpper = new double[nRows];
00561 memcpy(rowLower,rowLower_,nRows*sizeof(double));
00562 memcpy(rowUpper,rowUpper_,nRows*sizeof(double));
00563 rowLower[nRows-1]=-DBL_MAX;
00564 if (usingObjective_) {
00565 rowUpper[nRows-1]=cutoff;
00566 } else {
00567 rowUpper[nRows-1]=DBL_MAX;
00568 }
00569 memcpy(colLower,colLower_,nCols*sizeof(double));
00570 memcpy(colUpper,colUpper_,nCols*sizeof(double));
00571 if (mode) {
00572
00573 const double * lower = si.getColLower();
00574 const double * upper = si.getColUpper();
00575 for (i=0;i<nCols;i++) {
00576 if (colLower[i]<lower[i])
00577 colLower[i]=lower[i];
00578 if (colUpper[i]>upper[i])
00579 colUpper[i]=upper[i];
00580 }
00581 }
00582 }
00583 #ifdef CGL_DEBUG
00584 const OsiRowCutDebugger * debugger = si.getRowCutDebugger();
00585 if (debugger&&!debugger->onOptimalPath(si))
00586 debugger = NULL;
00587 #else
00588 const OsiRowCutDebugger * debugger = NULL;
00589 #endif
00590
00591 const int * column = rowCopy->getIndices();
00592 const int * rowStart = rowCopy->getVectorStarts();
00593 const int * rowLength = rowCopy->getVectorLengths();
00594 const double * rowElements = rowCopy->getElements();
00595
00596 if (mode) {
00597 ninfeas= tighten(colLower, colUpper, column, rowElements,
00598 rowStart, rowLength, rowLower, rowUpper,
00599 nRows, nCols, intVar, 2, primalTolerance_);
00600 if (!ninfeas) {
00601
00602 {
00603 const double * lower = si.getColLower();
00604 const double * upper = si.getColUpper();
00605 const double * colsol = si.getColSolution();
00606 int numberChanged=0,ifCut=0;
00607 CoinPackedVector lbs;
00608 CoinPackedVector ubs;
00609 for (i = 0; i < nCols; ++i) {
00610 if (intVar[i]) {
00611 colUpper[i] = min(upper[i],floor(colUpper[i]+1.0e-4));
00612 if (colUpper[i]<upper[i]-1.0e-8) {
00613 if (colUpper[i]<colsol[i]-1.0e-8)
00614 ifCut=1;
00615 ubs.insert(i,colUpper[i]);
00616 numberChanged++;
00617 }
00618 colLower[i] = max(lower[i],ceil(colLower[i]-1.0e-4));
00619 if (colLower[i]>lower[i]+1.0e-8) {
00620 if (colLower[i]>colsol[i]+1.0e-8)
00621 ifCut=1;
00622 lbs.insert(i,colLower[i]);
00623 numberChanged++;
00624 }
00625 }
00626 }
00627 if (numberChanged) {
00628 OsiColCut cc;
00629 cc.setUbs(ubs);
00630 cc.setLbs(lbs);
00631 if (ifCut) {
00632 cc.setEffectiveness(100.0);
00633 } else {
00634 cc.setEffectiveness(1.0e-5);
00635 }
00636 #ifdef CGL_DEBUG
00637 checkBounds(debugger,cc);
00638 #endif
00639 cs.insert(cc);
00640 }
00641 }
00642 int * markR = new int [nRows];
00643 double * minR = new double [nRows];
00644 double * maxR = new double [nRows];
00645 int * look = new int[nCols];
00646 int nLook=0;
00647
00648 tighten2(colLower, colUpper, column, rowElements,
00649 rowStart, rowLength, rowLower, rowUpper,
00650 minR , maxR , markR, nRows, nCols);
00651
00652 if (mode==1) {
00653 const double * colsol = si.getColSolution();
00654 double_int_pair * array = new double_int_pair [nCols];
00655 for (i=0;i<nCols;i++) {
00656 if (intVar[i]&&colUpper[i]-colLower[i]>1.0e-8) {
00657 double away = fabs(0.5-(colsol[i]-floor(colsol[i])));
00658 if (away<0.49999) {
00659 array[nLook].infeasibility=away;
00660 array[nLook++].sequence=i;
00661 }
00662 }
00663 }
00664 std::sort(array,array+nLook,double_int_pair_compare());
00665 nLook=min(nLook,maxProbe_);
00666 for (i=0;i<nLook;i++) {
00667 look[i]=array[i].sequence;
00668 }
00669 delete [] array;
00670 } else {
00671 for (i=0;i<nCols;i++) {
00672 if (intVar[i]&&colUpper[i]-colLower[i]>1.0e-8) {
00673 look[nLook++]=i;
00674 }
00675 }
00676 }
00677 ninfeas= probe(si, debugger, cs, colLower, colUpper, rowCopy,
00678 rowLower, rowUpper,
00679 intVar, minR, maxR, markR,
00680 look,nLook);
00681 delete [] look;
00682 delete [] markR;
00683 delete [] minR;
00684 delete [] maxR;
00685 }
00686 } else {
00687
00688
00689 assert(numberIntegers==numberIntegers_);
00690
00691 int * markR = new int [nRows];
00692 double * minR = new double [nRows];
00693 double * maxR = new double [nRows];
00694 int * look = new int[nCols];
00695 int nLook=0;
00696 const double * colsol = si.getColSolution();
00697 for (i=0;i<numberIntegers_;i++) {
00698 int j=cutVector_[i].sequence;
00699 if (!cutVector_[i].newValue&&colUpper[j]-colLower[j]>1.0e-8) {
00700 double away = fabs(0.5-(colsol[j]-floor(colsol[j])));
00701 if (away<0.4999999) {
00702 look[nLook++]=j;
00703 }
00704 }
00705 }
00706
00707 tighten2(colLower, colUpper, column, rowElements,
00708 rowStart, rowLength, rowLower, rowUpper,
00709 minR , maxR , markR, nRows, nCols);
00710 OsiCuts csNew;
00711 ninfeas= probe(si, debugger, csNew, colLower, colUpper, rowCopy,
00712 rowLower, rowUpper,
00713 intVar, minR, maxR, markR,
00714 look,nLook);
00715 if (!ninfeas) {
00716
00717 int nCuts = csNew.sizeRowCuts();
00718 int iCut;
00719
00720
00721 int * backward = new int [2*nCols];
00722 int * onList = backward + nCols;
00723 for (i=0;i<numberIntegers_;i++) {
00724 int j=cutVector_[i].sequence;
00725 backward[j]=i;
00726 onList[j]=0;
00727 }
00728 for (i=0;i<nLook;i++) {
00729 onList[look[i]]=1;
00730 }
00731
00732
00733 for (iCut=0;iCut<nCuts;iCut++) {
00734 OsiRowCut rcut;
00735 CoinPackedVector rpv;
00736 rcut = csNew.rowCut(iCut);
00737 rpv = rcut.row();
00738 assert(rpv.getNumElements()==2);
00739 const int * indices = rpv.getIndices();
00740 double* elements = rpv.getElements();
00741 double lb=rcut.lb();
00742
00743 i=backward[indices[1]];
00744 if (lb==-DBL_MAX) {
00745
00746 if (elements[1]<0.0) {
00747 cutVector_[i].lastUBWhenAt0++;
00748 } else {
00749 cutVector_[i].lastUBWhenAt1++;
00750 }
00751 } else {
00752
00753 if (elements[1]>0.0) {
00754 cutVector_[i].lastLBWhenAt0++;
00755 } else {
00756 cutVector_[i].lastLBWhenAt1++;
00757 }
00758 }
00759 }
00760
00761 for (i=0;i<numberIntegers_;i++) {
00762 int j=cutVector_[i].sequence;
00763 if (onList[j]&&!cutVector_[i].newValue) {
00764 disaggregation thisOne=cutVector_[i];
00765 int total;
00766
00767 cutVector_[i].lastUBWhenAt0 =0;
00768 total = thisOne.lastUBWhenAt0;
00769 cutVector_[i].lastUBWhenAt1 = total;
00770 total += thisOne.lastUBWhenAt1;
00771 cutVector_[i].lastLBWhenAt0 = total;
00772 total += thisOne.lastLBWhenAt0;
00773 cutVector_[i].lastLBWhenAt1 = total;
00774 total += thisOne.lastLBWhenAt1;
00775 cutVector_[i].newValue=new double[total];
00776 cutVector_[i].index=new int[total];
00777 }
00778 }
00779
00780 for (iCut=0;iCut<nCuts;iCut++) {
00781 OsiRowCut rcut;
00782 CoinPackedVector rpv;
00783 int iput;
00784 rcut = csNew.rowCut(iCut);
00785 rpv = rcut.row();
00786 assert(rpv.getNumElements()==2);
00787 const int * indices = rpv.getIndices();
00788 double* elements = rpv.getElements();
00789 double lb=rcut.lb();
00790
00791 i=backward[indices[1]];
00792 if (lb==-DBL_MAX) {
00793
00794 if (elements[1]<0.0) {
00795 iput=cutVector_[i].lastUBWhenAt0;
00796 cutVector_[i].newValue[iput]=elements[1];
00797 cutVector_[i].index[iput]=indices[0];
00798 cutVector_[i].lastUBWhenAt0++;
00799 } else {
00800 iput=cutVector_[i].lastUBWhenAt1;
00801 cutVector_[i].newValue[iput]=elements[1];
00802 cutVector_[i].index[iput]=indices[0];
00803 cutVector_[i].lastUBWhenAt1++;
00804 }
00805 } else {
00806
00807 if (elements[1]>0.0) {
00808 iput=cutVector_[i].lastLBWhenAt0;
00809 cutVector_[i].newValue[iput]=elements[1];
00810 cutVector_[i].index[iput]=indices[0];
00811 cutVector_[i].lastLBWhenAt0++;
00812 } else {
00813 iput=cutVector_[i].lastLBWhenAt1;
00814 cutVector_[i].newValue[iput]=elements[1];
00815 cutVector_[i].index[iput]=indices[0];
00816 cutVector_[i].lastLBWhenAt1++;
00817 }
00818 }
00819 }
00820
00821 for (i=0;i<numberIntegers_;i++) {
00822 int j=cutVector_[i].sequence;
00823 double upperInt=colUpper_[j];
00824 double lowerInt=colLower_[j];
00825 double solInt=colsol[j];
00826 double down = solInt-lowerInt;
00827 double up = upperInt-solInt;
00828 double lower, upper, solValue;
00829 int icol;
00830 double newSol,value,newValue;
00831 int index[2];
00832 double element[2];
00833 if (colUpper[j]-colLower[j]>1.0e-8) {
00834 double away = fabs(0.5-(colsol[j]-floor(colsol[j])));
00835 if (away<0.4999999) {
00836 disaggregation thisOne=cutVector_[i];
00837 int k;
00838 OsiRowCut rc;
00839
00840 for (k=0;k<thisOne.lastUBWhenAt0;k++) {
00841 icol = thisOne.index[k];
00842 value = thisOne.newValue[k];
00843 solValue=colsol[icol];
00844 upper=colUpper_[icol];
00845 newValue= value + upper;
00846 if (solValue > newValue - value * down + primalTolerance_) {
00847 rc.setLb(-DBL_MAX);
00848 rc.setUb(newValue + lowerInt*value);
00849 index[0]=icol;
00850 element[0]=1.0;
00851 index[1]=j;
00852 element[1]= value;
00853
00854 newSol = (rc.ub()-solValue)/element[1];
00855 if (mode_)
00856 assert(newSol>solInt);
00857 rc.setEffectiveness(newSol-solInt);
00858 if (rc.effectiveness()>1.0e-3) {
00859 rc.setRow(2,index,element);
00860 #ifdef CGL_DEBUG
00861 if (debugger) assert(!debugger->invalidCut(rc));
00862 #endif
00863 cs.insert(rc);
00864 }
00865 }
00866 }
00867
00868 for (k=thisOne.lastUBWhenAt0;k<thisOne.lastUBWhenAt1;k++) {
00869 icol = thisOne.index[k];
00870 value = thisOne.newValue[k];
00871 solValue=colsol[icol];
00872 upper=colUpper_[icol];
00873 newValue= value + upper;
00874 if (solValue > newValue - value * up + primalTolerance_) {
00875 rc.setLb(-DBL_MAX);
00876 rc.setUb(newValue - upperInt*value);
00877 index[0]=icol;
00878 element[0]=1.0;
00879 index[1]=j;
00880 element[1]= value;
00881
00882 newSol = (rc.ub()-solValue)/element[1];
00883 if (mode_)
00884 assert(newSol>solInt);
00885 rc.setEffectiveness(newSol-solInt);
00886 if (rc.effectiveness()>1.0e-3) {
00887 rc.setRow(2,index,element);
00888 #ifdef CGL_DEBUG
00889 if (debugger) assert(!debugger->invalidCut(rc));
00890 #endif
00891 cs.insert(rc);
00892 }
00893 }
00894 }
00895
00896 for (k=thisOne.lastUBWhenAt1;k<thisOne.lastLBWhenAt0;k++) {
00897 icol = thisOne.index[k];
00898 value = thisOne.newValue[k];
00899 solValue=colsol[icol];
00900 lower=colLower_[icol];
00901 newValue= value + lower;
00902 if (solValue < newValue - value * down - primalTolerance_) {
00903 rc.setLb(newValue + lowerInt*value);
00904 rc.setUb(DBL_MAX);
00905 index[0]=icol;
00906 element[0]=1.0;
00907 index[1]=j;
00908 element[1]= value;
00909
00910 newSol = (rc.lb()-solValue)/element[1];
00911 if (mode_)
00912 assert(newSol>solInt);
00913 rc.setEffectiveness(newSol-solInt);
00914 if (rc.effectiveness()>1.0e-3) {
00915 rc.setRow(2,index,element);
00916 #ifdef CGL_DEBUG
00917 if (debugger) assert(!debugger->invalidCut(rc));
00918 #endif
00919 cs.insert(rc);
00920 }
00921 }
00922 }
00923
00924 for (k=thisOne.lastLBWhenAt0;k<thisOne.lastLBWhenAt1;k++) {
00925 icol = thisOne.index[k];
00926 value = thisOne.newValue[k];
00927 solValue=colsol[icol];
00928 lower=colLower_[icol];
00929 newValue= value + lower;
00930 if (solValue < newValue - value * up - primalTolerance_) {
00931 rc.setLb(newValue - upperInt*value);
00932 rc.setUb(DBL_MAX);
00933 index[0]=icol;
00934 element[0]=1.0;
00935 index[1]=j;
00936 element[1]= value;
00937
00938 newSol = (rc.lb()-solValue)/element[1];
00939 if (mode_)
00940 assert(newSol>solInt);
00941 rc.setEffectiveness(newSol-solInt);
00942 if (rc.effectiveness()>1.0e-3) {
00943 rc.setRow(2,index,element);
00944 #ifdef CGL_DEBUG
00945 if (debugger) assert(!debugger->invalidCut(rc));
00946 #endif
00947 cs.insert(rc);
00948 }
00949 }
00950 }
00951 }
00952 }
00953 }
00954 delete [] backward;
00955 }
00956 delete [] look;
00957 delete [] markR;
00958 delete [] minR;
00959 delete [] maxR;
00960 }
00961
00962 if (!numberRows_) {
00963 delete rowCopy;
00964 } else {
00965 delete [] rowLower;
00966 delete [] rowUpper;
00967 }
00968 delete [] intVar;
00969 return ninfeas;
00970 }
00971
00972 int CglProbing::probe( const OsiSolverInterface & si,
00973 const OsiRowCutDebugger * debugger,
00974 OsiCuts & cs,
00975 double * colLower, double * colUpper,
00976 CoinPackedMatrix *rowCopy,
00977 double * rowLower, double * rowUpper,
00978 char * intVar, double * minR, double * maxR,
00979 int * markR,
00980 int * look, int nLook) const
00981 {
00982 int nRows=rowCopy->getNumRows();
00983 int nCols=rowCopy->getNumCols();
00984 double * colsol = new double[nCols];
00985 double * djs = new double[nCols];
00986 const double * currentColLower = si.getColLower();
00987 const double * currentColUpper = si.getColUpper();
00988 double * tempL = new double [nCols];
00989 double * tempU = new double [nCols];
00990 int * markC = new int [nCols];
00991 int * stackC = new int [2*nCols];
00992 int * stackR = new int [nRows];
00993 double * saveL = new double [2*nCols];
00994 double * saveU = new double [2*nCols];
00995 double * saveMin = new double [nRows];
00996 double * saveMax = new double [nRows];
00997 double * element = new double[nCols];
00998 int * index = new int[nCols];
00999 CoinPackedMatrix columnCopy = * rowCopy;
01000 columnCopy.reverseOrdering();
01001 const int * column = rowCopy->getIndices();
01002 const int * rowStart = rowCopy->getVectorStarts();
01003 const int * rowLength = rowCopy->getVectorLengths();
01004 const double * rowElements = rowCopy->getElements();
01005 const int * row = columnCopy.getIndices();
01006 const int * columnStart = columnCopy.getVectorStarts();
01007 const int * columnLength = columnCopy.getVectorLengths();
01008 const double * columnElements = columnCopy.getElements();
01009 double movement;
01010 int i, j, k,kk,jj;
01011 int jcol,kcol,irow,krow;
01012 bool anyColumnCuts=false;
01013 double dbound, value, value2;
01014 int ninfeas=0;
01015 int rowCuts;
01016 double disaggEffectiveness;
01017 if (mode_) {
01018
01019 memcpy(djs,si.getReducedCost(),nCols*sizeof(double));
01020 memcpy(colsol, si.getColSolution(),nCols*sizeof(double));
01021 disaggEffectiveness=1.0e-3;
01022 rowCuts=rowCuts_;
01023 } else {
01024
01025 memset(djs,0,nCols*sizeof(double));
01026 memcpy(colsol, si.getColSolution(),nCols*sizeof(double));
01027 disaggEffectiveness=-1.0e10;
01028 rowCuts=1;
01029 }
01030 for (i = 0; i < nCols; ++i) {
01031
01032 if (1) {
01033 if (colUpper[i]-colLower[i]>1.0e-8) {
01034 if (colsol[i]<colLower[i]+primalTolerance_) {
01035 colsol[i]=colLower[i];
01036 djs[i] = max(0.0,djs[i]);
01037 } else if (colsol[i]>colUpper[i]-primalTolerance_) {
01038 colsol[i]=colUpper[i];
01039 djs[i] = min(0.0,djs[i]);
01040 } else {
01041 djs[i]=0.0;
01042 }
01043
01044
01045 }
01046 }
01047 }
01048
01049 int ipass=0,nfixed=-1;
01050
01051 double cutoff;
01052 si.getDblParam(OsiDualObjectiveLimit,cutoff);
01053 cutoff *= si.getObjSense();
01054 if (fabs(cutoff)>1.0e30)
01055 assert (cutoff>1.0e30);
01056 double current = si.getObjValue();
01057
01058 if (!mode_)
01059 cutoff=DBL_MAX;
01060
01061 int nstackC0=-1;
01062 int * stackC0 = new int[maxStack_];
01063 double * lo0 = new double[maxStack_];
01064 double * up0 = new double[maxStack_];
01065 int nstackR,nstackC;
01066 for (i=0;i<nCols;i++) {
01067 if (colUpper[i]-colLower[i]<1.0e-8) {
01068 markC[i]=3;
01069 } else {
01070 markC[i]=0;
01071 }
01072 }
01073 double tolerance = 1.0e1*primalTolerance_;
01074 while (ipass<maxPass_&&nfixed) {
01075 int iLook;
01076 ipass++;
01077 nfixed=0;
01078 for (iLook=0;iLook<nLook;iLook++) {
01079 double solval;
01080 double down;
01081 double up;
01082 int awayFromBound=1;
01083 j=look[iLook];
01084 solval=colsol[j];
01085 down = floor(solval+tolerance);
01086 up = ceil(solval-tolerance);
01087 if(colUpper[j]-colLower[j]<1.0e-8) markC[j]=3;
01088 if (markC[j]||!intVar[j]) continue;
01089 if (solval>colUpper[j]-tolerance||solval<colLower[j]+tolerance) {
01090 awayFromBound=0;
01091 if (solval<colLower[j]+tolerance) {
01092 solval = colLower[j]+1.0e-1;
01093 down=colLower[j];
01094 up=down+1.0;
01095 } else if (solval>colUpper[j]-tolerance) {
01096 solval = colUpper[j]-1.0e-1;
01097 up=colUpper[j];
01098 down=up-1;
01099 }
01100 }
01101 if ((solval-down>1.0e-6&&up-solval>1.0e-6)||mode_!=1) {
01102 int istackC,iway, istackR;
01103 int way[]={1,2,1};
01104 int feas[]={1,2,4};
01105 int feasible=0;
01106 int notFeasible;
01107 for (iway=0;iway<3;iway ++) {
01108 int fixThis=0;
01109 double objVal=current;
01110 int goingToTrueBound=0;
01111 stackC[0]=j;
01112 markC[j]=way[iway];
01113 if (way[iway]==1) {
01114 movement=down-colUpper[j];
01115 assert(movement<-0.99999);
01116 if (fabs(down-colLower[j])<1.0e-7) {
01117 goingToTrueBound=2;
01118 down=colLower[j];
01119 }
01120 } else {
01121 movement=up-colLower[j];
01122 assert(movement>0.99999);
01123 if (fabs(up-colUpper[j])<1.0e-7) {
01124 goingToTrueBound=2;
01125 up=colUpper[j];
01126 }
01127 }
01128 if (goingToTrueBound&&(colUpper[j]-colLower[j]>1.5||colLower[j]))
01129 goingToTrueBound=1;
01130
01131 if ((rowCuts&1)==0)
01132 goingToTrueBound=0;
01133 #ifdef PRINT_DEBUG
01134 if (fabs(movement)>1.01) {
01135 printf("big %d %g %g %g\n",j,colLower[j],solval,colUpper[j]);
01136 }
01137 #endif
01138 if (movement*djs[j]>0.0)
01139 objVal += movement*djs[j];
01140 nstackC=1;
01141 nstackR=0;
01142 saveL[0]=colLower[j];
01143 saveU[0]=colUpper[j];
01144 notFeasible=0;
01145 if (movement<0.0) {
01146 colUpper[j] += movement;
01147 colUpper[j] = floor(colUpper[j]+0.5);
01148 #ifdef PRINT_DEBUG
01149 printf("** Trying %d down to 0\n",j);
01150 #endif
01151 } else {
01152 colLower[j] += movement;
01153 colLower[j] = floor(colLower[j]+0.5);
01154 #ifdef PRINT_DEBUG
01155 printf("** Trying %d up to 1\n",j);
01156 #endif
01157 }
01158 if (fabs(colUpper[j]-colLower[j])<1.0e-6)
01159 markC[j]=3;
01160 istackC=0;
01161
01162 for (k=columnStart[j];k<columnStart[j]+columnLength[j];k++) {
01163 irow = row[k];
01164 value = columnElements[k];
01165 if (markR[irow]==-1) {
01166 stackR[nstackR]=irow;
01167 markR[irow]=nstackR;
01168 saveMin[nstackR]=minR[irow];
01169 saveMax[nstackR]=maxR[irow];
01170 nstackR++;
01171 } else if (markR[irow]==-2) {
01172 continue;
01173 }
01174
01175 if (movement>0.0) {
01176
01177 if (value>0.0) {
01178
01179 minR[irow] += value;
01180 if (minR[irow]>rowUpper[irow]+1.0e-5) {
01181 notFeasible=1;
01182 istackC=1;
01183 break;
01184 }
01185 } else {
01186
01187 maxR[irow] += value;
01188 if (maxR[irow]<rowLower[irow]-1.0e-5) {
01189 notFeasible=1;
01190 istackC=1;
01191 break;
01192 }
01193 }
01194 } else {
01195
01196 if (value<0.0) {
01197
01198 minR[irow] -= value;
01199 if (minR[irow]>rowUpper[irow]+1.0e-5) {
01200 notFeasible=1;
01201 istackC=1;
01202 break;
01203 }
01204 } else {
01205
01206 maxR[irow] -= value;
01207 if (maxR[irow]<rowLower[irow]-1.0e-5) {
01208 notFeasible=1;
01209 istackC=1;
01210 break;
01211 }
01212 }
01213 }
01214 }
01215 while (istackC<nstackC&&nstackC<maxStack_) {
01216 int jway;
01217 jcol=stackC[istackC];
01218 jway=markC[jcol];
01219
01220 if (jway==3&&istackC) {
01221 istackC++;
01222 continue;
01223 }
01224 for (k=columnStart[jcol];k<columnStart[jcol]+columnLength[jcol];k++) {
01225
01226 if (notFeasible)
01227 break;
01228 irow = row[k];
01229
01230 if (markR[irow]!=-2) {
01231
01232 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];kk++) {
01233 double moveUp=0.0;
01234 double moveDown=0.0;
01235 double newUpper=-1.0,newLower=1.0;
01236 kcol=column[kk];
01237 bool onList = (markC[kcol]!=0);
01238 if (markC[kcol]!=3) {
01239 value2=rowElements[kk];
01240 if (value2 < 0.0) {
01241 if (colUpper[kcol] < 1e10 && (markC[kcol]&2)==0 &&
01242 rowUpper[irow]<1.0e10) {
01243 dbound = colUpper[kcol]+
01244 (rowUpper[irow]-minR[irow])/value2;
01245 if (dbound > colLower[kcol] + primalTolerance_) {
01246 if (intVar[kcol]) {
01247 markC[kcol] |= 2;
01248 newLower = ceil(dbound-primalTolerance_);
01249 } else {
01250 markC[kcol]=3;
01251 newLower=dbound;
01252 if (newLower>colUpper[kcol]&&
01253 newLower-primalTolerance_<=colUpper[kcol]) {
01254 newLower=colUpper[kcol];
01255 }
01256 }
01257 moveUp = newLower-colLower[kcol];
01258 }
01259 }
01260 if (colLower[kcol] > -1e10 && (markC[kcol]&1)==0 &&
01261 rowLower[irow]>-1.0e10) {
01262 dbound = colLower[kcol] +
01263 (rowLower[irow]-maxR[irow])/value2;
01264 if (dbound < colUpper[kcol] - primalTolerance_) {
01265 if (intVar[kcol]) {
01266 markC[kcol] |= 1;
01267 newUpper = floor(dbound+primalTolerance_);
01268 } else {
01269 markC[kcol]=3;
01270 newUpper=dbound;
01271 if (newUpper<colLower[kcol]&&
01272 newUpper+primalTolerance_>=colLower[kcol]) {
01273 newUpper=colLower[kcol];
01274 }
01275 }
01276 moveDown = newUpper-colUpper[kcol];
01277 }
01278 }
01279 } else {
01280
01281 if (colUpper[kcol] < 1e10 && (markC[kcol]&2)==0 &&
01282 rowLower[irow]>-1.0e10) {
01283 dbound = colUpper[kcol] +
01284 (rowLower[irow]-maxR[irow])/value2;
01285 if (dbound > colLower[kcol] + primalTolerance_) {
01286 if (intVar[kcol]) {
01287 markC[kcol] |= 2;
01288 newLower = ceil(dbound-primalTolerance_);
01289 } else {
01290 markC[kcol]=3;
01291 newLower=dbound;
01292 if (newLower>colUpper[kcol]&&
01293 newLower-primalTolerance_<=colUpper[kcol]) {
01294 newLower=colUpper[kcol];
01295 }
01296 }
01297 moveUp = newLower-colLower[kcol];
01298 }
01299 }
01300 if (colLower[kcol] > -1e10 && (markC[kcol]&1)==0 &&
01301 rowUpper[irow]<1.0e10) {
01302 dbound = colLower[kcol] +
01303 (rowUpper[irow]-minR[irow])/value2;
01304 if (dbound < colUpper[kcol] - primalTolerance_) {
01305 if (intVar[kcol]) {
01306 markC[kcol] |= 1;
01307 newUpper = floor(dbound+primalTolerance_);
01308 } else {
01309 markC[kcol]=3;
01310 newUpper=dbound;
01311 if (newUpper<colLower[kcol]&&
01312 newUpper+primalTolerance_>=colLower[kcol]) {
01313 newUpper=colLower[kcol];
01314 }
01315 }
01316 moveDown = newUpper-colUpper[kcol];
01317 }
01318 }
01319 }
01320 if (moveUp&&nstackC<2*maxStack_) {
01321 fixThis++;
01322 #ifdef PRINT_DEBUG
01323 printf("lower bound on %d increased from %g to %g by row %d %g %g\n",kcol,colLower[kcol],newLower,irow,rowLower[irow],rowUpper[irow]);
01324 value=0.0;
01325 for (jj=rowStart[irow];jj<rowStart[irow]+rowLength[irow];jj++) {
01326 int ii=column[jj];
01327 if (colUpper[ii]-colLower[ii]>primalTolerance_) {
01328 printf("(%d, %g) ",ii,rowElements[jj]);
01329 } else {
01330 value += rowElements[jj]*colLower[ii];
01331 }
01332 }
01333 printf(" - fixed %g\n",value);
01334 for (jj=rowStart[irow];jj<rowStart[irow]+rowLength[irow];jj++) {
01335 int ii=column[jj];
01336 if (colUpper[ii]-colLower[ii]<primalTolerance_) {
01337 printf("(%d, %g, %g) ",ii,rowElements[jj],colLower[ii]);
01338 }
01339 }
01340 printf("\n");
01341 #endif
01342 if (!onList) {
01343 stackC[nstackC]=kcol;
01344 saveL[nstackC]=colLower[kcol];
01345 saveU[nstackC]=colUpper[kcol];
01346 nstackC++;
01347 onList=true;
01348 }
01349 if (newLower>colsol[kcol]) {
01350 if (djs[kcol]<0.0) {
01351
01352 assert (newLower>colUpper[kcol]+primalTolerance_);
01353 } else {
01354 objVal += moveUp*djs[kcol];
01355 }
01356 }
01357 if (intVar[kcol])
01358 newLower = max(colLower[kcol],ceil(newLower-1.0e-4));
01359 colLower[kcol]=newLower;
01360 if (fabs(colUpper[kcol]-colLower[kcol])<1.0e-6)
01361 markC[kcol]=3;
01362
01363 for (jj=columnStart[kcol];jj<columnStart[kcol]+columnLength[kcol];jj++) {
01364 krow = row[jj];
01365 value = columnElements[jj];
01366 if (markR[krow]==-1) {
01367 stackR[nstackR]=krow;
01368 markR[krow]=nstackR;
01369 saveMin[nstackR]=minR[krow];
01370 saveMax[nstackR]=maxR[krow];
01371 nstackR++;
01372 } else if (markR[krow]==-2) {
01373 continue;
01374 }
01375
01376
01377 if (value>0.0) {
01378
01379 minR[krow] += value*moveUp;
01380 } else {
01381
01382 maxR[krow] += value*moveUp;
01383 if (maxR[krow]<rowLower[krow]-1.0e-5) {
01384 colUpper[kcol]=-1.0e50;
01385 break;
01386 }
01387 }
01388 }
01389 }
01390 if (moveDown&&nstackC<2*maxStack_) {
01391 fixThis++;
01392 #ifdef PRINT_DEBUG
01393 printf("upper bound on %d decreased from %g to %g by row %d %g %g\n",kcol,colUpper[kcol],newUpper,irow,rowLower[irow],rowUpper[irow]);
01394 value=0.0;
01395 for (jj=rowStart[irow];jj<rowStart[irow]+rowLength[irow];jj++) {
01396 int ii=column[jj];
01397 if (colUpper[ii]-colLower[ii]>primalTolerance_) {
01398 printf("(%d, %g) ",ii,rowElements[jj]);
01399 } else {
01400 value += rowElements[jj]*colLower[ii];
01401 }
01402 }
01403 printf(" - fixed %g\n",value);
01404 for (jj=rowStart[irow];jj<rowStart[irow]+rowLength[irow];jj++) {
01405 int ii=column[jj];
01406 if (colUpper[ii]-colLower[ii]<primalTolerance_) {
01407 printf("(%d, %g, %g) ",ii,rowElements[jj],colLower[ii]);
01408 }
01409 }
01410 printf("\n");
01411 #endif
01412 if (!onList) {
01413 stackC[nstackC]=kcol;
01414 saveL[nstackC]=colLower[kcol];
01415 saveU[nstackC]=colUpper[kcol];
01416 nstackC++;
01417 onList=true;
01418 }
01419 if (newUpper<colsol[kcol]) {
01420 if (djs[kcol]>0.0) {
01421
01422 assert (colLower[kcol]>newUpper+primalTolerance_);
01423 } else {
01424 objVal += moveDown*djs[kcol];
01425 }
01426 }
01427 if (intVar[kcol])
01428 newUpper = min(colUpper[kcol],floor(newUpper+1.0e-4));
01429 colUpper[kcol]=newUpper;
01430 if (fabs(colUpper[kcol]-colLower[kcol])<1.0e-6)
01431 markC[kcol]=3;
01432
01433 for (jj=columnStart[kcol];jj<columnStart[kcol]+columnLength[kcol];jj++) {
01434 krow = row[jj];
01435 value = columnElements[jj];
01436 if (markR[krow]==-1) {
01437 stackR[nstackR]=krow;
01438 markR[krow]=nstackR;
01439 saveMin[nstackR]=minR[krow];
01440 saveMax[nstackR]=maxR[krow];
01441 nstackR++;
01442 } else if (markR[krow]==-2) {
01443 continue;
01444 }
01445
01446
01447 if (value<0.0) {
01448
01449 minR[krow] += value*moveDown;
01450 if (minR[krow]>rowUpper[krow]+1.0e-5) {
01451 colUpper[kcol]=-1.0e50;
01452 break;
01453 }
01454 } else {
01455
01456 maxR[krow] += value*moveDown;
01457 if (maxR[krow]<rowLower[krow]-1.0e-5) {
01458 colUpper[kcol]=-1.0e50;
01459 break;
01460 }
01461 }
01462 }
01463 }
01464 if (colLower[kcol]>colUpper[kcol]+primalTolerance_) {
01465 notFeasible=1;;
01466 k=columnStart[jcol]+columnLength[jcol];
01467 istackC=nstackC+1;
01468 #ifdef PRINT_DEBUG
01469 printf("** not feasible this way\n");
01470 #endif
01471 break;
01472 }
01473 }
01474 }
01475 }
01476 }
01477 istackC++;
01478 }
01479 if (!notFeasible) {
01480 if (objVal<=cutoff) {
01481 feasible |= feas[iway];
01482 } else {
01483 #ifdef PRINT_DEBUG
01484 printf("not feasible on dj\n");
01485 #endif
01486 notFeasible=1;
01487 if (iway==1&&feasible==0) {
01488
01489 ninfeas=1;
01490 j=nCols-1;
01491 break;
01492 }
01493 }
01494 } else if (iway==1&&feasible==0) {
01495
01496 ninfeas=1;
01497 j=nCols-1;
01498 iLook=nLook;
01499 ipass=maxPass_;
01500 break;
01501 }
01502 if (notFeasible)
01503 goingToTrueBound=0;
01504 if (iway==2||(iway==1&&feasible==2)) {
01505
01506 iway=3;
01507 nfixed++;
01508 if (mode_) {
01509 OsiColCut cc;
01510 int nTot=0,nFix=0,nInt=0;
01511 bool ifCut=false;
01512 for (istackC=0;istackC<nstackC;istackC++) {
01513 int icol=stackC[istackC];
01514 if (intVar[icol]) {
01515 if (colUpper[icol]<currentColUpper[icol]-1.0e-4) {
01516 element[nFix]=colUpper[icol];
01517 index[nFix++]=icol;
01518 nInt++;
01519 if (colsol[icol]>colUpper[icol]+primalTolerance_) {
01520 ifCut=true;
01521 anyColumnCuts=true;
01522 }
01523 }
01524 }
01525 }
01526 if (nFix) {
01527 nTot=nFix;
01528 cc.setUbs(nFix,index,element);
01529 nFix=0;
01530 }
01531 for (istackC=0;istackC<nstackC;istackC++) {
01532 int icol=stackC[istackC];
01533 if (intVar[icol]) {
01534 if (colLower[icol]>currentColLower[icol]+1.0e-4) {
01535 element[nFix]=colLower[icol];
01536 index[nFix++]=icol;
01537 nInt++;
01538 if (colsol[icol]<colLower[icol]-primalTolerance_) {
01539 ifCut=true;
01540 anyColumnCuts=true;
01541 }
01542 }
01543 }
01544 }
01545 if (nFix) {
01546 nTot+=nFix;
01547 cc.setLbs(nFix,index,element);
01548 }
01549
01550 if (nInt) {
01551 if (ifCut) {
01552 cc.setEffectiveness(100.0);
01553 } else {
01554 cc.setEffectiveness(1.0e-5);
01555 }
01556 #ifdef CGL_DEBUG
01557 checkBounds(debugger,cc);
01558 #endif
01559 cs.insert(cc);
01560 }
01561 }
01562 for (istackC=0;istackC<nstackC;istackC++) {
01563 int icol=stackC[istackC];
01564 if (colUpper[icol]-colLower[icol]>primalTolerance_) {
01565 markC[icol]=0;
01566 } else {
01567 markC[icol]=3;
01568 }
01569 }
01570 for (istackR=0;istackR<nstackR;istackR++) {
01571 int irow=stackR[istackR];
01572 markR[irow]=-1;
01573 }
01574 } else {
01575
01576
01577 if (iway==0) {
01578 nstackC0=min(nstackC,maxStack_);
01579 double solMove = solval-down;
01580 double boundChange;
01581 if (notFeasible) {
01582 nstackC0=0;
01583 } else {
01584 for (istackC=0;istackC<nstackC0;istackC++) {
01585 int icol=stackC[istackC];
01586 stackC0[istackC]=icol;
01587 lo0[istackC]=colLower[icol];
01588 up0[istackC]=colUpper[icol];
01589 }
01590 }
01591
01592 for (istackC=nstackC-1;istackC>=0;istackC--) {
01593 int icol=stackC[istackC];
01594 double oldU=saveU[istackC];
01595 double oldL=saveL[istackC];
01596 if(goingToTrueBound==2&&istackC) {
01597
01598
01599 boundChange = oldU-colUpper[icol];
01600 if (boundChange>0.0&&oldU<1.0e10&&
01601 (!mode_||colsol[icol]>colUpper[icol]
01602 + boundChange*solMove+primalTolerance_)) {
01603
01604 OsiRowCut rc;
01605 rc.setLb(-DBL_MAX);
01606 rc.setUb(colUpper[icol]-down*boundChange);
01607 index[0]=icol;
01608 element[0]=1.0;
01609 index[1]=j;
01610 element[1]= - boundChange;
01611
01612 double newSol = (colsol[icol]-colUpper[icol])/
01613 boundChange;
01614 if (mode_)
01615 assert(newSol>solMove);
01616 rc.setEffectiveness(newSol-solMove);
01617 if (rc.effectiveness()>disaggEffectiveness) {
01618 rc.setRow(2,index,element);
01619 #ifdef CGL_DEBUG
01620 if (debugger) assert(!debugger->invalidCut(rc));
01621 #endif
01622 cs.insert(rc);
01623 }
01624 }
01625
01626
01627 boundChange = oldL-colLower[icol];
01628 if (boundChange<0.0&&oldL>-1.0e10&&
01629 (!mode_||colsol[icol]<colLower[icol]
01630 + boundChange*solMove-primalTolerance_)) {
01631
01632 OsiRowCut rc;
01633 rc.setLb(colLower[icol]-down*boundChange);
01634 rc.setUb(DBL_MAX);
01635 index[0]=icol;
01636 element[0]=1.0;
01637 index[1]=j;
01638 element[1]=- boundChange;
01639
01640 double newSol = (colsol[icol]-colLower[icol])/
01641 boundChange;
01642 if (mode_)
01643 assert(newSol>solMove);
01644 rc.setEffectiveness(newSol-solMove);
01645 if (rc.effectiveness()>disaggEffectiveness) {
01646 rc.setRow(2,index,element);
01647 #ifdef CGL_DEBUG
01648 if (debugger) assert(!debugger->invalidCut(rc));
01649 #endif
01650 cs.insert(rc);
01651 #if 0
01652 printf("%d original bounds %g, %g new Lo %g sol= %g int %d sol= %g\n",icol,oldL,oldU,colLower[icol],colsol[icol], j, colsol[j]);
01653 printf("-1.0 * x(%d) + %g * y(%d) <= %g\n",
01654 icol,boundChange,j,rc.ub());
01655 #endif
01656 }
01657 }
01658 }
01659 colUpper[icol]=oldU;
01660 colLower[icol]=oldL;
01661 markC[icol]=0;
01662 }
01663 for (istackR=0;istackR<nstackR;istackR++) {
01664 int irow=stackR[istackR];
01665
01666 if ((rowCuts&2)!=0&&goingToTrueBound) {
01667 bool ifCut=anyColumnCuts;
01668 double gap = rowUpper[irow]-maxR[irow];
01669 double sum=0.0;
01670 if (!ifCut&&(gap>primalTolerance_&&gap<1.0e8)) {
01671
01672 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];
01673 kk++) {
01674 sum += rowElements[kk]*colsol[column[kk]];
01675 }
01676 if (sum-gap*colsol[j]>maxR[irow]+primalTolerance_) {
01677
01678
01679
01680 int * index = (int *)saveL;
01681 double * element = saveU;
01682 int n=0;
01683 bool coefficientExists=false;
01684 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];
01685 kk++) {
01686 if (column[kk]!=j) {
01687 index[n]=column[kk];
01688 element[n++]=rowElements[kk];
01689 } else {
01690 double value=rowElements[kk]-gap;
01691 if (fabs(value)>1.0e-12) {
01692 index[n]=column[kk];
01693 element[n++]=value;
01694 }
01695 coefficientExists=true;
01696 }
01697 }
01698 if (!coefficientExists) {
01699 index[n]=j;
01700 element[n++]=-gap;
01701 }
01702 OsiRowCut rc;
01703 rc.setLb(-DBL_MAX);
01704 rc.setUb(rowUpper[irow]-gap*(colLower[j]+1.0));
01705
01706 rc.setEffectiveness((sum-gap*colsol[j]-maxR[irow])/gap);
01707 if (rc.effectiveness()>1.0e-3) {
01708 rc.setRow(n,index,element);
01709 #ifdef CGL_DEBUG
01710 if (debugger) assert(!debugger->invalidCut(rc));
01711 #endif
01712 cs.insert(rc);
01713 }
01714 }
01715 }
01716 gap = minR[irow]-rowLower[irow];
01717 if (!ifCut&&(gap>primalTolerance_&&gap<1.0e8)) {
01718
01719 if (!sum) {
01720 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];
01721 kk++) {
01722 sum += rowElements[kk]*colsol[column[kk]];
01723 }
01724 }
01725 if (sum+gap*colsol[j]<minR[irow]+primalTolerance_) {
01726
01727
01728
01729 int * index = (int *)saveL;
01730 double * element = saveU;
01731 int n=0;
01732 bool coefficientExists=false;
01733 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];
01734 kk++) {
01735 if (column[kk]!=j) {
01736 index[n]=column[kk];
01737 element[n++]=rowElements[kk];
01738 } else {
01739 double value=rowElements[kk]+gap;
01740 if (fabs(value)>1.0e-12) {
01741 index[n]=column[kk];
01742 element[n++]=value;
01743 }
01744 coefficientExists=true;
01745 }
01746 }
01747 if (!coefficientExists) {
01748 index[n]=j;
01749 element[n++]=gap;
01750 }
01751 OsiRowCut rc;
01752 rc.setLb(rowLower[irow]+gap*(colLower[j]+1.0));
01753 rc.setUb(DBL_MAX);
01754
01755 rc.setEffectiveness((minR[irow]-sum-gap*colsol[j])/gap);
01756 if (rc.effectiveness()>1.0e-3) {
01757 rc.setRow(n,index,element);
01758 #ifdef CGL_DEBUG
01759 if (debugger) assert(!debugger->invalidCut(rc));
01760 #endif
01761 cs.insert(rc);
01762 }
01763 }
01764 }
01765 }
01766 minR[irow]=saveMin[istackR];
01767 maxR[irow]=saveMax[istackR];
01768 markR[irow]=-1;
01769 }
01770 } else {
01771 if (iway==1&&feasible==3) {
01772 iway=3;
01773
01774 for (istackC=nstackC-1;istackC>=0;istackC--) {
01775 int icol=stackC[istackC];
01776 markC[icol]=istackC+1000;
01777 }
01778 if (mode_) {
01779 OsiColCut cc;
01780 int nTot=0,nFix=0,nInt=0;
01781 bool ifCut=false;
01782 for (istackC=0;istackC<nstackC0;istackC++) {
01783 int icol=stackC0[istackC];
01784 int istackC1=markC[icol]-1000;
01785 if (istackC1>=0) {
01786 if (min(lo0[istackC],colLower[icol])>saveL[istackC1]+1.0e-4) {
01787 saveL[istackC1]=min(lo0[istackC],colLower[icol]);
01788 if (intVar[icol]) {
01789 element[nFix]=saveL[istackC1];
01790 index[nFix++]=icol;
01791 nInt++;
01792 if (colsol[icol]<saveL[istackC1]-primalTolerance_)
01793 ifCut=true;
01794 }
01795 nfixed++;
01796 }
01797 }
01798 }
01799 if (nFix) {
01800 nTot=nFix;
01801 cc.setLbs(nFix,index,element);
01802 nFix=0;
01803 }
01804 for (istackC=0;istackC<nstackC0;istackC++) {
01805 int icol=stackC0[istackC];
01806 int istackC1=markC[icol]-1000;
01807 if (istackC1>=0) {
01808 if (max(up0[istackC],colUpper[icol])<saveU[istackC1]-1.0e-4) {
01809 saveU[istackC1]=max(up0[istackC],colUpper[icol]);
01810 if (intVar[icol]) {
01811 element[nFix]=saveU[istackC1];
01812 index[nFix++]=icol;
01813 nInt++;
01814 if (colsol[icol]>saveU[istackC1]+primalTolerance_)
01815 ifCut=true;
01816 }
01817 nfixed++;
01818 }
01819 }
01820 }
01821 if (nFix) {
01822 nTot+=nFix;
01823 cc.setUbs(nFix,index,element);
01824 }
01825
01826 if (nInt) {
01827 if (ifCut) {
01828 cc.setEffectiveness(100.0);
01829 } else {
01830 cc.setEffectiveness(1.0e-5);
01831 }
01832 #ifdef CGL_DEBUG
01833 checkBounds(debugger,cc);
01834 #endif
01835 cs.insert(cc);
01836 }
01837 }
01838 } else {
01839 goingToTrueBound=0;
01840 }
01841 double solMove = up-solval;
01842 double boundChange;
01843
01844 for (istackC=nstackC-1;istackC>=0;istackC--) {
01845 int icol=stackC[istackC];
01846 double oldU=saveU[istackC];
01847 double oldL=saveL[istackC];
01848 if(goingToTrueBound==2&&istackC) {
01849
01850
01851 boundChange = oldU-colUpper[icol];
01852 if (boundChange>0.0&&oldU<1.0e10&&
01853 (!mode_||colsol[icol]>colUpper[icol]
01854 + boundChange*solMove+primalTolerance_)) {
01855
01856 OsiRowCut rc;
01857 rc.setLb(-DBL_MAX);
01858 rc.setUb(colUpper[icol]+up*boundChange);
01859 index[0]=icol;
01860 element[0]=1.0;
01861 index[1]=j;
01862 element[1]= + boundChange;
01863
01864 double newSol = (colsol[icol]-colUpper[icol])/
01865 boundChange;
01866 if (mode_)
01867 assert(newSol>solMove);
01868 rc.setEffectiveness(newSol-solMove);
01869 if (rc.effectiveness()>disaggEffectiveness) {
01870 rc.setRow(2,index,element);
01871 #ifdef CGL_DEBUG
01872 if (debugger) assert(!debugger->invalidCut(rc));
01873 #endif
01874 cs.insert(rc);
01875 }
01876 }
01877
01878
01879 boundChange = oldL-colLower[icol];
01880 if (boundChange<0.0&&oldL>-1.0e10&&
01881 (!mode_||colsol[icol]<colLower[icol]
01882 + boundChange*solMove-primalTolerance_)) {
01883
01884 OsiRowCut rc;
01885 rc.setLb(colLower[icol]+up*boundChange);
01886 rc.setUb(DBL_MAX);
01887 index[0]=icol;
01888 element[0]=1.0;
01889 index[1]=j;
01890 element[1]= + boundChange;
01891
01892 double newSol = (colsol[icol]-colLower[icol])/
01893 boundChange;
01894 if (mode_)
01895 assert(newSol>solMove);
01896 rc.setEffectiveness(newSol-solMove);
01897 if (rc.effectiveness()>disaggEffectiveness) {
01898 rc.setRow(2,index,element);
01899 #ifdef CGL_DEBUG
01900 if (debugger) assert(!debugger->invalidCut(rc));
01901 #endif
01902 cs.insert(rc);
01903 }
01904 }
01905 }
01906 colUpper[icol]=oldU;
01907 colLower[icol]=oldL;
01908 markC[icol]=0;
01909 }
01910 for (istackR=0;istackR<nstackR;istackR++) {
01911 int irow=stackR[istackR];
01912
01913 if ((rowCuts&2)!=0&&goingToTrueBound) {
01914 bool ifCut=anyColumnCuts;
01915 double gap = rowUpper[irow]-maxR[irow];
01916 double sum=0.0;
01917 if (!ifCut&&(gap>primalTolerance_&&gap<1.0e8)) {
01918
01919 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];
01920 kk++) {
01921 sum += rowElements[kk]*colsol[column[kk]];
01922 }
01923 if (sum+gap*colsol[j]>rowUpper[irow]+primalTolerance_) {
01924
01925
01926
01927 int * index = (int *)saveL;
01928 double * element = saveU;
01929 int n=0;
01930 bool coefficientExists=false;
01931 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];
01932 kk++) {
01933 if (column[kk]!=j) {
01934 index[n]=column[kk];
01935 element[n++]=rowElements[kk];
01936 } else {
01937 double value=rowElements[kk]+gap;
01938 if (fabs(value)>1.0e-12) {
01939 index[n]=column[kk];
01940 element[n++]=value;
01941 }
01942 coefficientExists=true;
01943 }
01944 }
01945 if (!coefficientExists) {
01946 index[n]=j;
01947 element[n++]=gap;
01948 }
01949 OsiRowCut rc;
01950 rc.setLb(-DBL_MAX);
01951 rc.setUb(rowUpper[irow]+gap*(colUpper[j]-1.0));
01952
01953 rc.setEffectiveness((sum+gap*colsol[j]-rowUpper[irow])/gap);
01954 if (rc.effectiveness()>1.0e-3) {
01955 rc.setRow(n,index,element);
01956 #ifdef CGL_DEBUG
01957 if (debugger) assert(!debugger->invalidCut(rc));
01958 #endif
01959 cs.insert(rc);
01960 }
01961 }
01962 }
01963 gap = minR[irow]-rowLower[irow];
01964 if (!ifCut&&(gap>primalTolerance_&&gap<1.0e8)) {
01965
01966 if (!sum) {
01967 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];
01968 kk++) {
01969 sum += rowElements[kk]*colsol[column[kk]];
01970 }
01971 }
01972 if (sum-gap*colsol[j]<rowLower[irow]+primalTolerance_) {
01973
01974
01975
01976 int * index = (int *)saveL;
01977 double * element = saveU;
01978 int n=0;
01979 bool coefficientExists=false;
01980 for (kk=rowStart[irow];kk<rowStart[irow]+rowLength[irow];
01981 kk++) {
01982 if (column[kk]!=j) {
01983 index[n]=column[kk];
01984 element[n++]=rowElements[kk];
01985 } else {
01986 double value=rowElements[kk]-gap;
01987 if (fabs(value)>1.0e-12) {
01988 index[n]=column[kk];
01989 element[n++]=value;
01990 }
01991 coefficientExists=true;
01992 }
01993 }
01994 if (!coefficientExists) {
01995 index[n]=j;
01996 element[n++]=-gap;
01997 }
01998 OsiRowCut rc;
01999 rc.setLb(rowLower[irow]-gap*(colUpper[j]-1));
02000 rc.setUb(DBL_MAX);
02001
02002 rc.setEffectiveness((rowLower[irow]-sum+gap*colsol[j])/gap);
02003 if (rc.effectiveness()>1.0e-3) {
02004 rc.setRow(n,index,element);
02005 #ifdef CGL_DEBUG
02006 if (debugger) assert(!debugger->invalidCut(rc));
02007 #endif
02008 cs.insert(rc);
02009 }
02010 }
02011 }
02012 }
02013 minR[irow]=saveMin[istackR];
02014 maxR[irow]=saveMax[istackR];
02015 markR[irow]=-1;
02016 }
02017 }
02018 }
02019 }
02020 }
02021 }
02022 }
02023 delete [] stackC0;
02024 delete [] lo0;
02025 delete [] up0;
02026 delete [] tempL;
02027 delete [] tempU;
02028 delete [] markC;
02029 delete [] stackC;
02030 delete [] stackR;
02031 delete [] saveL;
02032 delete [] saveU;
02033 delete [] saveMin;
02034 delete [] saveMax;
02035 delete [] index;
02036 delete [] element;
02037 delete [] djs;
02038 delete [] colsol;
02039 return (ninfeas);
02040 }
02041
02042
02043
02044
02045
02046 void CglProbing::snapshot ( const OsiSolverInterface & si,
02047 char * possible)
02048 {
02049 deleteSnapshot();
02050
02051
02052 numberColumns_=si.getNumCols();
02053 numberRows_=si.getNumRows();
02054 colLower_ = new double[numberColumns_];
02055 colUpper_ = new double[numberColumns_];
02056 memcpy(colLower_,si.getColLower(),numberColumns_*sizeof(double));
02057 memcpy(colUpper_,si.getColUpper(),numberColumns_*sizeof(double));
02058 rowLower_= new double [numberRows_+1];
02059 rowUpper_= new double [numberRows_+1];
02060 memcpy(rowLower_,si.getRowLower(),numberRows_*sizeof(double));
02061 memcpy(rowUpper_,si.getRowUpper(),numberRows_*sizeof(double));
02062
02063 int i;
02064 if (possible) {
02065 for (i=0;i<numberRows_;i++) {
02066 if (!possible[i]) {
02067 rowLower_[i]=-DBL_MAX;
02068 rowUpper_[i]=DBL_MAX;
02069 }
02070 }
02071 }
02072
02073
02074 char * intVar = new char[numberColumns_];
02075 numberIntegers_=0;
02076 for (i=0;i<numberColumns_;i++) {
02077 if (si.isInteger(i)) {
02078 intVar[i]=1;
02079 numberIntegers_++;
02080 } else {
02081 intVar[i]=0;
02082 }
02083 }
02084
02085 rowCopy_ = new CoinPackedMatrix(*si.getMatrixByRow());
02086
02087 const int * column = rowCopy_->getIndices();
02088 const int * rowStart = rowCopy_->getVectorStarts();
02089 const int * rowLength = rowCopy_->getVectorLengths();
02090 const double * rowElements = rowCopy_->getElements();
02091
02092 int ninfeas= tighten(colLower_, colUpper_, column, rowElements,
02093 rowStart, rowLength, rowLower_, rowUpper_,
02094 numberRows_, numberColumns_, intVar, 5, primalTolerance_);
02095 assert (!ninfeas);
02096
02097
02098 cutVector_ = new disaggregation [numberIntegers_];
02099 memset(cutVector_,0,numberIntegers_*sizeof(disaggregation));
02100 numberIntegers_=0;
02101 for (i=0;i<numberColumns_;i++) {
02102 if (intVar[i]) {
02103 cutVector_[numberIntegers_++].sequence=i;
02104 }
02105 }
02106 delete [] intVar;
02107
02108
02109 if (possible) {
02110 for (i=0;i<numberRows_;i++) {
02111 if (rowLower_[i]<-1.0e30&&rowUpper_[i]>1.0e30)
02112 possible[i]=0;
02113 }
02114 }
02115 int * index = new int[numberRows_];
02116 int nDrop=0,nKeep=0;
02117 for (i=0;i<numberRows_;i++) {
02118 if (rowLower_[i]<-1.0e30&&rowUpper_[i]>1.0e30) {
02119 index[nDrop++]=i;
02120 } else {
02121 rowLower_[nKeep]=rowLower_[i];
02122 rowUpper_[nKeep++]=rowUpper_[i];
02123 }
02124 }
02125 numberRows_=nKeep;
02126 if (nDrop)
02127 rowCopy_->deleteRows(nDrop,index);
02128 delete [] index;
02129
02130 int * columns = new int[numberColumns_];
02131 double * elements = new double[numberColumns_];
02132 int n=0;
02133 const double * objective = si.getObjCoefficients();
02134 bool maximize = (si.getObjSense()==-1);
02135 for (i=0;i<numberColumns_;i++) {
02136 if (objective[i]) {
02137 elements[n]= (maximize) ? -objective[i] : objective[i];
02138 columns[n++]=i;
02139 }
02140 }
02141 rowCopy_->appendRow(n,columns,elements);
02142 delete [] columns;
02143 delete [] elements;
02144 numberRows_++;
02145
02146 }
02147
02148 void CglProbing::deleteSnapshot()
02149 {
02150 delete [] rowLower_;
02151 delete [] rowUpper_;
02152 delete [] colLower_;
02153 delete [] colUpper_;
02154 delete rowCopy_;
02155 numberRows_=0;
02156 numberColumns_=0;
02157 rowCopy_=NULL;
02158 rowLower_=NULL;
02159 rowUpper_=NULL;
02160 colLower_=NULL;
02161 colUpper_=NULL;
02162 int i;
02163 for (i=0;i<numberIntegers_;i++) {
02164 delete cutVector_[i].newValue;
02165 delete cutVector_[i].index;
02166 }
02167 delete [] cutVector_;
02168 numberIntegers_=0;
02169 cutVector_=NULL;
02170 }
02171
02172 void CglProbing::setMode(int mode)
02173 {
02174 if (mode>=0&&mode<3)
02175 mode_=mode;
02176 }
02177 int CglProbing::getMode() const
02178 {
02179 return mode_;
02180 }
02181
02182 void CglProbing::setMaxPass(int value)
02183 {
02184 if (value>0)
02185 maxPass_=value;
02186 }
02187
02188 int CglProbing::getMaxPass() const
02189 {
02190 return maxPass_;
02191 }
02192
02193 void CglProbing::setMaxProbe(int value)
02194 {
02195 if (value>0)
02196 maxProbe_=value;
02197 }
02198
02199 int CglProbing::getMaxProbe() const
02200 {
02201 return maxProbe_;
02202 }
02203
02204 void CglProbing::setMaxLook(int value)
02205 {
02206 if (value>0)
02207 maxStack_=value;
02208 }
02209
02210 int CglProbing::getMaxLook() const
02211 {
02212 return maxStack_;
02213 }
02214
02215 void CglProbing::setUsingObjective(bool yesNo)
02216 {
02217 usingObjective_=yesNo;
02218 }
02219
02220 int CglProbing::getUsingObjective() const
02221 {
02222 return usingObjective_;
02223 }
02224
02225 void CglProbing::setRowCuts(int type)
02226 {
02227 if (type>=0&&type<4)
02228 rowCuts_=type;
02229 }
02230
02231 int CglProbing::rowCuts() const
02232 {
02233 return rowCuts_;
02234 }
02235
02236 const double * CglProbing::tightLower() const
02237 {
02238 return colLower_;
02239 }
02240
02241 const double * CglProbing::tightUpper() const
02242 {
02243 return colUpper_;
02244 }
02245
02246 const double * CglProbing::relaxedRowLower() const
02247 {
02248 return rowLower_;
02249 }
02250
02251 const double * CglProbing::relaxedRowUpper() const
02252 {
02253 return rowUpper_;
02254 }
02255
02256
02257
02258
02259
02260 CglProbing::CglProbing ()
02261 :
02262 CglCutGenerator(),
02263 primalTolerance_(1.0e-07),
02264 mode_(1),
02265 rowCuts_(1),
02266 maxPass_(3),
02267 maxProbe_(100),
02268 maxStack_(50),
02269 usingObjective_(false)
02270 {
02271
02272 numberRows_=0;
02273 numberColumns_=0;
02274 rowCopy_=NULL;
02275 rowLower_=NULL;
02276 rowUpper_=NULL;
02277 colLower_=NULL;
02278 colUpper_=NULL;
02279 numberIntegers_=0;
02280 cutVector_=NULL;
02281 }
02282
02283
02284
02285
02286 CglProbing::CglProbing ( const CglProbing & source)
02287 :
02288 CglCutGenerator(source),
02289 primalTolerance_(source.primalTolerance_),
02290 mode_(source.mode_),
02291 rowCuts_(source.rowCuts_),
02292 maxPass_(source.maxPass_),
02293 maxProbe_(source.maxProbe_),
02294 maxStack_(source.maxStack_),
02295 usingObjective_(source.usingObjective_)
02296 {
02297 numberRows_=source.numberRows_;
02298 numberColumns_=source.numberColumns_;
02299 if (numberRows_>0) {
02300 rowCopy_= new CoinPackedMatrix(*(source.rowCopy_));
02301 rowLower_=new double[numberRows_];
02302 memcpy(rowLower_,source.rowLower_,numberRows_*sizeof(double));
02303 rowUpper_=new double[numberRows_];
02304 memcpy(rowUpper_,source.rowUpper_,numberRows_*sizeof(double));
02305 colLower_=new double[numberColumns_];
02306 memcpy(colLower_,source.colLower_,numberColumns_*sizeof(double));
02307 colUpper_=new double[numberColumns_];
02308 memcpy(colUpper_,source.colUpper_,numberColumns_*sizeof(double));
02309 int i;
02310 numberIntegers_=source.numberIntegers_;
02311 cutVector_=new disaggregation [numberIntegers_];
02312 memcpy(cutVector_,source.cutVector_,numberIntegers_*sizeof(disaggregation));
02313 for (i=0;i<numberIntegers_;i++) {
02314 if (cutVector_[i].newValue) {
02315 cutVector_[i].newValue = new double [cutVector_[i].lastLBWhenAt1];
02316 memcpy(cutVector_[i].newValue,source.cutVector_[i].newValue,
02317 cutVector_[i].lastLBWhenAt1*sizeof(double));
02318 cutVector_[i].index = new int [cutVector_[i].lastLBWhenAt1];
02319 memcpy(cutVector_[i].index,source.cutVector_[i].index,
02320 cutVector_[i].lastLBWhenAt1*sizeof(int));
02321 }
02322 }
02323 } else {
02324 rowCopy_=NULL;
02325 rowLower_=NULL;
02326 rowUpper_=NULL;
02327 colLower_=NULL;
02328 colUpper_=NULL;
02329 numberIntegers_=0;
02330 cutVector_=NULL;
02331 }
02332 }
02333
02334
02335
02336
02337 CglProbing::~CglProbing ()
02338 {
02339
02340 delete [] rowLower_;
02341 delete [] rowUpper_;
02342 delete [] colLower_;
02343 delete [] colUpper_;
02344 delete rowCopy_;
02345 int i;
02346 for (i=0;i<numberIntegers_;i++) {
02347 delete cutVector_[i].newValue;
02348 delete cutVector_[i].index;
02349 }
02350 delete [] cutVector_;
02351 }
02352
02353
02354
02355
02356 CglProbing &
02357 CglProbing::operator=(
02358 const CglProbing& rhs)
02359 {
02360 if (this != &rhs) {
02361 CglCutGenerator::operator=(rhs);
02362 primalTolerance_=rhs.primalTolerance_;
02363 numberRows_=rhs.numberRows_;
02364 numberColumns_=rhs.numberColumns_;
02365 delete [] rowLower_;
02366 delete [] rowUpper_;
02367 delete [] colLower_;
02368 delete [] colUpper_;
02369 delete rowCopy_;
02370 mode_=rhs.mode_;
02371 rowCuts_=rhs.rowCuts_;
02372 maxPass_=rhs.maxPass_;
02373 maxProbe_=rhs.maxProbe_;
02374 maxStack_=rhs.maxStack_;
02375 usingObjective_=rhs.usingObjective_;
02376 if (numberRows_>0) {
02377 rowCopy_= new CoinPackedMatrix(*(rhs.rowCopy_));
02378 rowLower_=new double[numberRows_];
02379 memcpy(rowLower_,rhs.rowLower_,numberRows_*sizeof(double));
02380 rowUpper_=new double[numberRows_];
02381 memcpy(rowUpper_,rhs.rowUpper_,numberRows_*sizeof(double));
02382 colLower_=new double[numberColumns_];
02383 memcpy(colLower_,rhs.colLower_,numberColumns_*sizeof(double));
02384 colUpper_=new double[numberColumns_];
02385 memcpy(colUpper_,rhs.colUpper_,numberColumns_*sizeof(double));
02386 int i;
02387 numberIntegers_=rhs.numberIntegers_;
02388 cutVector_=new disaggregation [numberIntegers_];
02389 memcpy(cutVector_,rhs.cutVector_,numberIntegers_*sizeof(disaggregation));
02390 for (i=0;i<numberIntegers_;i++) {
02391 if (cutVector_[i].newValue) {
02392 cutVector_[i].newValue = new double [cutVector_[i].lastLBWhenAt1];
02393 memcpy(cutVector_[i].newValue,rhs.cutVector_[i].newValue,
02394 cutVector_[i].lastLBWhenAt1*sizeof(double));
02395 cutVector_[i].index = new int [cutVector_[i].lastLBWhenAt1];
02396 memcpy(cutVector_[i].index,rhs.cutVector_[i].index,
02397 cutVector_[i].lastLBWhenAt1*sizeof(int));
02398 }
02399 }
02400 } else {
02401 rowCopy_=NULL;
02402 rowLower_=NULL;
02403 rowUpper_=NULL;
02404 colLower_=NULL;
02405 colUpper_=NULL;
02406 numberIntegers_=0;
02407 cutVector_=NULL;
02408 }
02409 }
02410 return *this;
02411 }
02412
02414 void
02415 CglProbing::refreshSolver(OsiSolverInterface * solver)
02416 {
02417 }