00001
00002
00003 #if defined(_MSC_VER)
00004
00005 # pragma warning(disable:4786)
00006 #endif
00007 #include <cstdlib>
00008 #include <cstdio>
00009 #include <cmath>
00010 #include <cassert>
00011 #include <cfloat>
00012 #include <iostream>
00013
00014 #include "CoinHelperFunctions.hpp"
00015 #include "CglKnapsackCover.hpp"
00016 #include "CoinPackedVector.hpp"
00017 #include "CoinSort.hpp"
00018 #include "CoinPackedMatrix.hpp"
00019 #include "OsiRowCutDebugger.hpp"
00020
00021
00022
00023
00024
00025 void CglKnapsackCover::generateCuts(const OsiSolverInterface & si,
00026 OsiCuts & cs ) const
00027 {
00028
00029 int nRows=si.getNumRows();
00030 int nCols=si.getNumCols();
00031
00032
00033
00034
00035
00036
00037
00038 CoinPackedVector krow;
00039 double b=0.0;
00040 int * complement= new int[nCols];
00041
00042
00043
00044
00045
00046 double * xstar= new double[nCols];
00047
00048
00049 int * thisColumnIndex = new int [nCols];
00050 double * thisElement = new double[nCols];
00051 int * back = new int[nCols];
00052
00053 const double *colsol = si.getColSolution();
00054 int k;
00055
00056
00057
00058
00059 int * vub = new int [nRows];
00060
00061
00062 int * vubRow = new int [nCols];
00063 double * vubValue = new double [nRows];
00064
00065
00066 double * effectiveUpper = new double [nRows];
00067 double * effectiveLower = new double [nRows];
00068 const double * colUpper = si.getColUpper();
00069 const double * colLower = si.getColLower();
00070 for (k=0; k<nCols; k++){
00071 back[k]=-1;
00072 xstar[k]=colsol[k];
00073 complement[k]=0;
00074 vubRow[k]=-1;
00075 if (si.isBinary(k)) {
00076 if (si.isFreeBinary(k)) {
00077 vubRow[k]=-2;
00078 } else {
00079 vubRow[k]=-10;
00080 }
00081 } else if (colUpper[k]==colLower[k]) {
00082 vubRow[k]=-10;
00083 }
00084 }
00085
00086 int rowIndex;
00087 int numberVub=0;
00088
00089 const CoinPackedMatrix * matrixByRow = si.getMatrixByRow();
00090 const double * elementByRow = matrixByRow->getElements();
00091 const int * column = matrixByRow->getIndices();
00092 const int * rowStart = matrixByRow->getVectorStarts();
00093 const int * rowLength = matrixByRow->getVectorLengths();
00094 const double * rowUpper = si.getRowUpper();
00095 const double * rowLower = si.getRowLower();
00096
00097
00098
00099 for (rowIndex=0;rowIndex<nRows;rowIndex++) {
00100 int start = rowStart[rowIndex];
00101 int end = start + rowLength[rowIndex];
00102 double upRhs = rowUpper[rowIndex];
00103 double loRhs = rowLower[rowIndex];
00104 int numberContinuous=0;
00105 int numberBinary=0;
00106 int iCont=-1;
00107 double sum = 0.0;
00108 double valueContinuous=0.0;
00109 double valueBinary=0.0;
00110 int iBinary=-1;
00111 int j;
00112 for (j=start;j<end;j++) {
00113 int iColumn=column[j];
00114 if (colUpper[iColumn]>colLower[iColumn]) {
00115 sum += colsol[iColumn]*elementByRow[j];
00116 if (vubRow[iColumn]==-2) {
00117
00118 numberBinary++;
00119 valueBinary=elementByRow[j];
00120 iBinary=iColumn;
00121 } else if (vubRow[iColumn]==-1) {
00122
00123 if (colsol[iColumn]<colUpper[iColumn]-1.0e-6&&
00124 colsol[iColumn]>colLower[iColumn]+1.0e-6) {
00125
00126 iCont=iColumn;
00127 numberContinuous++;
00128 valueContinuous=elementByRow[j];
00129 } else {
00130
00131 numberContinuous ++;
00132 iCont=-1;
00133 }
00134 } else {
00135
00136 numberContinuous ++;
00137 iCont=-1;
00138 if (colsol[iColumn]<colUpper[iColumn]-1.0e-6&&
00139 colsol[iColumn]>colLower[iColumn]+1.0e-6) {
00140
00141 numberContinuous ++;
00142 iCont=-1;
00143 }
00144 }
00145 } else {
00146
00147 upRhs -= colLower[iColumn]*elementByRow[j];
00148 loRhs -= colLower[iColumn]*elementByRow[j];
00149 }
00150 }
00151
00152 effectiveUpper[rowIndex] = upRhs;
00153 effectiveLower[rowIndex] = loRhs;
00154 vubValue[rowIndex] = valueContinuous;
00155 bool possible = false;
00156 if (fabs(sum-upRhs)<1.0e-5) {
00157 possible=true;
00158 } else {
00159 effectiveUpper[rowIndex]=DBL_MAX;
00160 }
00161 if (fabs(sum-loRhs)<1.0e-5) {
00162 possible=true;
00163 } else {
00164 effectiveLower[rowIndex]=-DBL_MAX;
00165 }
00166 if (!numberBinary||numberBinary+numberContinuous>maxInKnapsack_)
00167 possible=false;
00168 if (possible) {
00169
00170 if(numberContinuous==1&&iCont>=0) {
00171
00172 if (numberBinary==1)
00173 #ifdef PRINT_DEBUG
00174 printf("vub (by row %d) %g <= 0-1 %g * %d + %g * %d <= %g\n",
00175 rowIndex,effectiveLower[rowIndex],valueBinary,iBinary,
00176 valueContinuous,iCont,effectiveUpper[rowIndex]);
00177 #endif
00178 vubRow[iCont]=rowIndex;
00179 vub[rowIndex]=iCont;
00180 numberVub++;
00181 } else if (numberBinary>1) {
00182
00183 vub[rowIndex]=-1;
00184 } else {
00185
00186 vub[rowIndex]=-2;
00187 }
00188 } else {
00189
00190 vub[rowIndex]=-2;
00191 }
00192 }
00193
00194 int numCheck = 0;
00195 int* toCheck = 0;
00196 if (!rowsToCheck_) {
00197 toCheck = new int[nRows];
00198 CoinIotaN(toCheck, nRows, 0);
00199 numCheck = nRows;
00200 } else {
00201 numCheck = numRowsToCheck_;
00202 toCheck = rowsToCheck_;
00203 }
00204
00205
00206 int ntry;
00207 if (numberVub)
00208 ntry=4;
00209 else
00210 ntry=2;
00211
00212 for (int ii=0; ii < numCheck; ++ii){
00213 rowIndex = toCheck[ii];
00214 if (rowIndex < 0 || rowIndex >= nRows)
00215 continue;
00216 if (vub[rowIndex]==-2)
00217 continue;
00218
00219 #ifdef PRINT_DEBUG
00220 std::cout << "CGL: Processing row " << rowIndex << std::endl;
00221 #endif
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00234
00235
00236
00238 #ifdef CGL_DEBUG
00239 assert(!krow.getNumElements());
00240 #endif
00241 double effectiveRhs[4];
00242 double rhs[4];
00243 double sign[]={0.0,0.0,-1.0,1.0};
00244 bool rowType[] = {false,true,false,true};
00245 effectiveRhs[0] = effectiveLower[rowIndex];
00246 rhs[0]=rowLower[rowIndex];
00247 effectiveRhs[2] = effectiveRhs[0];
00248 rhs[2]= effectiveRhs[0];
00249 effectiveRhs[1] = effectiveUpper[rowIndex];
00250 rhs[1]=rowUpper[rowIndex];
00251 effectiveRhs[3] = effectiveRhs[1];
00252 rhs[3]= effectiveRhs[1];
00253 int itry;
00254 #ifdef CGL_DEBUG
00255 int kcuts[4];
00256 memset(kcuts,0,4*sizeof(int));
00257 #endif
00258 for (itry=0;itry<ntry;itry++) {
00259 #ifdef CGL_DEBUG
00260 int nlast=cs.sizeRowCuts();
00261 #endif
00262
00263 if (fabs(effectiveRhs[itry])>1.0e20)
00264 continue;
00265 int length = rowLength[rowIndex];
00266 memcpy(thisColumnIndex,column+rowStart[rowIndex],length*sizeof(int));
00267 memcpy(thisElement,elementByRow+rowStart[rowIndex],
00268 length*sizeof(double));
00269 b=rhs[itry];
00270 if (itry>1) {
00271
00272 int i;
00273
00274 int length2=length;
00275 int numberReplaced=0;
00276 for (i=0;i<length;i++) {
00277 int iColumn = thisColumnIndex[i];
00278 back[thisColumnIndex[i]]=i;
00279 if (vubRow[iColumn]==-10) {
00280
00281 thisElement[i]=0.0;
00282 }
00283 }
00284 for (i=0;i<length;i++) {
00285 int iColumn = thisColumnIndex[i];
00286 int iRow = vubRow[iColumn];
00287 if (iRow>=0&&vub[iRow]==iColumn&&iRow!=rowIndex) {
00288 double useRhs=0.0;
00289 double vubCoefficient = vubValue[iRow];
00290 double thisCoefficient = thisElement[i];
00291 int replace = 0;
00292
00293 if (sign[itry]*thisCoefficient>0.0) {
00294
00295 if (effectiveLower[iRow]>-1.0e20&&vubCoefficient>0.0)
00296 replace=-1;
00297 else if (effectiveUpper[iRow]<1.0e20&&vubCoefficient<0.0)
00298 replace=1;
00299 } else {
00300
00301 if (effectiveLower[iRow]>-1.0e20&&vubCoefficient<0.0)
00302 replace=-1;
00303 else if (effectiveUpper[iRow]<1.0e20&&vubCoefficient>0.0)
00304 replace=1;
00305 }
00306 if (replace) {
00307 numberReplaced++;
00308 if (replace<0)
00309 useRhs = effectiveLower[iRow];
00310 else
00311 useRhs = effectiveUpper[iRow];
00312
00313
00314 thisElement[i]=0.0;
00315 double scale = thisCoefficient/vubCoefficient;
00316
00317 b -= scale*useRhs;
00318 int start = rowStart[iRow];
00319 int end = start+rowLength[iRow];
00320 int j;
00321 for (j=start;j<end;j++) {
00322 int iColumn = column[j];
00323 if (vubRow[iColumn]==-2) {
00324 double change = scale*elementByRow[j];
00325 int iBack = back[iColumn];
00326 if (iBack<0) {
00327
00328 back[iColumn]=length2;
00329 thisElement[length2]=-change;
00330 thisColumnIndex[length2++]=iColumn;
00331 } else {
00332
00333 thisElement[iBack] -= change;
00334 }
00335 }
00336 }
00337 }
00338 }
00339 }
00340 if (numberReplaced) {
00341 length=0;
00342 for (i=0;i<length2;i++) {
00343 int iColumn = thisColumnIndex[i];
00344 back[iColumn]=-1;
00345 if (thisElement[i]) {
00346 thisElement[length]=thisElement[i];
00347 thisColumnIndex[length++]=iColumn;
00348 }
00349 }
00350 if (length>maxInKnapsack_)
00351 continue;
00352 } else {
00353 for (i=0;i<length;i++) {
00354 int iColumn = thisColumnIndex[i];
00355 back[iColumn]=-1;
00356 }
00357 continue;
00358 }
00359 }
00360 if (!deriveAKnapsack(si, cs, krow, rowType[itry], b, complement,
00361 xstar, rowIndex,
00362 length,thisColumnIndex,thisElement)) {
00363
00364
00365
00366 for(k=0; k<krow.getNumElements(); k++) {
00367 if (complement[krow.getIndices()[k]]){
00368 xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]];
00369 complement[krow.getIndices()[k]]=0;
00370 }
00371 }
00372 krow.setVector(0,NULL,NULL);
00373 continue;
00374 }
00375 #ifdef PRINT_DEBUG
00376 {
00377
00378 int i;
00379 printf("rhs sense %c rhs %g\n",si.getRowSense()[rowIndex],
00380 si.getRightHandSide()[rowIndex]);
00381 const int * indices = si.getMatrixByRow()->getVector(rowIndex).getIndices();
00382 const double * elements = si.getMatrixByRow()->getVector(rowIndex).getElements();
00383
00384 for (i=0; i<si.getMatrixByRow()->getVector(rowIndex).getNumElements(); i++){
00385 printf("%d (s=%g) %g, ",indices[i],colsol[indices[i]],elements[i]);
00386 }
00387 printf("\n");
00388 }
00389 #endif
00390
00392
00393
00394
00395
00396
00397
00398
00399
00401
00403
00404
00406
00407 CoinPackedVector cover, remainder;
00408
00409
00410 if (findGreedyCover(rowIndex, krow, b, xstar, cover, remainder) == 1){
00411
00412
00413 if (!liftAndUncomplementAndAdd(rowUpper[rowIndex], krow, b,
00414 complement, rowIndex, cover,
00415 remainder, cs)) {
00416
00417
00418
00419 for(k=0; k<krow.getNumElements(); k++) {
00420 if (complement[krow.getIndices()[k]]){
00421 xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]];
00422 complement[krow.getIndices()[k]]=0;
00423 }
00424 }
00425 krow.setVector(0,NULL,NULL);
00426 continue;
00427 }
00428 }
00429
00430
00432
00433
00435
00436
00437 cover.setVector(0,NULL,NULL);
00438 remainder.setVector(0,NULL,NULL);
00439
00440 if (findPseudoJohnAndEllisCover(rowIndex, krow, b,
00441 xstar, cover, remainder) == 1){
00442
00443
00444 if (!liftAndUncomplementAndAdd(rowUpper[rowIndex], krow, b,
00445 complement, rowIndex, cover,
00446 remainder, cs)) {
00447
00448
00449
00450 for(k=0; k<krow.getNumElements(); k++) {
00451 if (complement[krow.getIndices()[k]]){
00452 xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]];
00453 complement[krow.getIndices()[k]]=0;
00454 }
00455 }
00456 krow.setVector(0,NULL,NULL);
00457 continue;
00458 }
00459
00460
00461 #if 0
00462
00463
00464 seqLiftAndUncomplementAndAdd(nCols, xstar, complement, rowIndex,
00465 krow.getNumElements(), b, cover, remainder,
00466 cs);
00467 #endif
00468 }
00469
00470
00471
00473
00474
00476 CoinPackedVector atOnes;
00477 CoinPackedVector fracCover;
00478
00479
00480 remainder.setVector(0,NULL,NULL);
00481
00482
00483 if (findJohnAndEllisCover(rowIndex, krow, b,
00484 xstar, fracCover, atOnes, remainder) == 1){
00485
00486
00487
00488
00489 liftUpDownAndUncomplementAndAdd(nCols, xstar, complement, rowIndex,
00490 krow.getNumElements(), b, fracCover,
00491 atOnes, remainder, cs);
00492 }
00493
00494
00496
00497
00498
00500
00501
00502
00503 cover.setVector(0,NULL,NULL);
00504 remainder.setVector(0,NULL,NULL);
00505
00506
00507
00508
00509
00510 if(krow.getNumElements()<=15){
00511 if (findExactMostViolatedMinCover(nCols, rowIndex, krow, b,
00512 xstar, cover, remainder) == 1){
00513
00514
00515 if (!liftAndUncomplementAndAdd(rowUpper[rowIndex], krow, b,
00516 complement, rowIndex, cover, remainder, cs)) {
00517
00518
00519
00520 for(k=0; k<krow.getNumElements(); k++) {
00521 if (complement[krow.getIndices()[k]]){
00522 xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]];
00523 complement[krow.getIndices()[k]]=0;
00524 }
00525 }
00526 krow.setVector(0,NULL,NULL);
00527 continue;
00528 }
00529 }
00530 }
00531 else {
00532 if (findLPMostViolatedMinCover(nCols, rowIndex, krow, b,
00533 xstar, cover, remainder) == 1){
00534
00535
00536 if (!liftAndUncomplementAndAdd(rowUpper[rowIndex], krow, b,
00537 complement, rowIndex, cover, remainder, cs)) {
00538
00539
00540
00541 for(k=0; k<krow.getNumElements(); k++) {
00542 if (complement[krow.getIndices()[k]]){
00543 xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]];
00544 complement[krow.getIndices()[k]]=0;
00545 }
00546 }
00547 krow.setVector(0,NULL,NULL);
00548 continue;
00549 }
00550 }
00551 }
00552
00553
00554
00555
00556
00557 int k;
00558 if (fabs(b-rowUpper[rowIndex]) > epsilon_) {
00559 for(k=0; k<krow.getNumElements(); k++) {
00560 if (complement[krow.getIndices()[k]]){
00561 xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]];
00562 complement[krow.getIndices()[k]]=0;
00563 }
00564 }
00565 }
00566 krow.setVector(0,NULL,NULL);
00567 #ifdef CGL_DEBUG
00568 int nnow = cs.sizeRowCuts();
00569 if (nnow>nlast) {
00570 const OsiRowCutDebugger * debugger = si.getRowCutDebugger();
00571 if (debugger&&debugger->onOptimalPath(si)) {
00572
00573 int k;
00574 for (k=nlast;k<nnow;k++) {
00575 OsiRowCut rc=cs.rowCut(k);
00576 if(debugger->invalidCut(rc)) {
00577 printf("itry %d, rhs %g, length %d\n",itry,rhs[itry],length);
00578 int i;
00579 for (i=0;i<length;i++) {
00580 int iColumn = thisColumnIndex[i];
00581 printf("column %d, coefficient %g, value %g, bounds %g %g\n",iColumn,
00582 thisElement[i],colsol[iColumn],colLower[iColumn],
00583 colUpper[iColumn]);
00584 }
00585 if (itry>1) {
00586 int length = rowLength[rowIndex];
00587 memcpy(thisColumnIndex,column+rowStart[rowIndex],
00588 length*sizeof(int));
00589 memcpy(thisElement,elementByRow+rowStart[rowIndex],
00590 length*sizeof(double));
00591 printf("Original row had rhs %g and length %d\n",
00592 (itry==2 ? rowLower[rowIndex] :rowUpper[rowIndex]),
00593 length);
00594 for (i=0;i<length;i++) {
00595 int iColumn = thisColumnIndex[i];
00596 printf("column %d, coefficient %g, value %g, bounds %g %g\n",iColumn,
00597 thisElement[i],colsol[iColumn],colLower[iColumn],
00598 colUpper[iColumn]);
00599 }
00600 }
00601 assert(!debugger->invalidCut(rc));
00602 }
00603 }
00604 }
00605 if (itry>1&&nnow-nlast>kcuts[itry-2]) {
00606 printf("itry %d gave %d cuts as against %d for itry %d\n",
00607 itry,nnow-nlast,kcuts[itry-2],itry-2);
00608 }
00609 kcuts[itry]=nnow-nlast;
00610 nlast=nnow;
00611 }
00612 #endif
00613 }
00614 }
00615
00616 if (toCheck != rowsToCheck_)
00617 delete[] toCheck;
00618 delete[] xstar;
00619 delete[] complement;
00620 delete [] thisColumnIndex;
00621 delete [] thisElement;
00622 delete [] back;
00623 delete [] vub;
00624 delete [] vubRow;
00625 delete [] vubValue;
00626 delete [] effectiveLower;
00627 delete [] effectiveUpper;
00628 }
00629
00630 void
00631 CglKnapsackCover::setTestedRowIndices(int num, const int* ind)
00632 {
00633 if (rowsToCheck_)
00634 delete[] rowsToCheck_;
00635 numRowsToCheck_ = num;
00636 if (num > 0) {
00637 rowsToCheck_ = new int[num];
00638 CoinCopyN(ind, num, rowsToCheck_);
00639 }
00640 }
00641
00642
00643
00644
00645 int
00646 CglKnapsackCover::liftAndUncomplementAndAdd(
00647 double rowub,
00648 CoinPackedVector & krow,
00649 double & b,
00650 int * complement,
00651 int row,
00652 CoinPackedVector & cover,
00653 CoinPackedVector & remainder,
00654 OsiCuts & cs ) const
00655 {
00656 CoinPackedVector cut;
00657 double cutRhs = cover.getNumElements() - 1.0;
00658 int goodCut=1;
00659
00660 if (remainder.getNumElements() > 0){
00661
00662 if (!liftCoverCut(
00663 b, krow.getNumElements(),
00664 cover, remainder,
00665 cut ))
00666 goodCut= 0;
00667 }
00668
00669
00670 else {
00671 cut.reserve(cover.getNumElements());
00672 cut.setConstant(cover.getNumElements(),cover.getIndices(),1.0);
00673 }
00674
00675
00676 int k;
00677 if (fabs(b-rowub)> epsilon_) {
00678 double * elements = cut.getElements();
00679 int * indices = cut.getIndices();
00680 for (k=0; k<cut.getNumElements(); k++){
00681 if (complement[indices[k]]) {
00682
00683
00684 elements[k] *= -1;
00685 cutRhs += elements[k];
00686 }
00687 }
00688 }
00689 if (goodCut) {
00690
00691 OsiRowCut rc;
00692 rc.setRow(cut);
00693 #ifdef CGL_DEBUG
00694 {
00695 double * elements = cut.getElements();
00696 int * indices = cut.getIndices();
00697 int n=cut.getNumElements();
00698 for (k=0; k<n; k++){
00699 assert(indices[k]>=0);
00700 assert(elements[k]);
00701 }
00702 }
00703 #endif
00704 rc.setLb(-DBL_MAX);
00705 rc.setUb(cutRhs);
00706
00707
00708
00709
00710 #ifdef PRINT_DEBUG
00711 {
00712 int k;
00713 printf("cutrhs %g %d elements\n",cutRhs,cut.getNumElements());
00714 double * elements = cut.getElements();
00715 int * indices = cut.getIndices();
00716 for (k=0; k<cut.getNumElements(); k++){
00717 printf("%d %g\n",indices[k],elements[k]);
00718 }
00719 }
00720 #endif
00721 cs.insert(rc);
00722
00723 return 1;
00724 } else {
00725 return 0;
00726 }
00727 }
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737 int
00738 CglKnapsackCover::deriveAKnapsack(
00739 const OsiSolverInterface & si,
00740 OsiCuts & cs,
00741 CoinPackedVector & krow,
00742 bool treatAsLRow,
00743 double & b,
00744 int * complement,
00745 double * xstar,
00746 int rowIndex,
00747 int numberElements,
00748 const int * index,
00749 const double * element) const
00750 {
00751 int i;
00752
00753 krow.clear();
00754
00755
00756
00757
00758
00759 CoinPackedVector leMatrixRow(numberElements,index,element);
00760
00761 double maxKrowElement = -DBL_MAX;
00762 double minKrowElement = DBL_MAX;
00763
00764
00765 if (treatAsLRow) {
00766
00767 } else {
00768
00769 b=-b;
00770 std::transform(leMatrixRow.getElements(),
00771 leMatrixRow.getElements() + leMatrixRow.getNumElements(),
00772 leMatrixRow.getElements(),
00773 std::negate<double>());
00774 }
00775
00776
00777
00778 int nBinUnsat =0;
00779 const double * colupper = si.getColUpper();
00780 const double * collower = si.getColLower();
00781
00782
00783
00784
00785
00786
00787
00788
00789 const int * indices = leMatrixRow.getIndices();
00790 const double * elements = leMatrixRow.getElements();
00791
00792 for (i=0; i<leMatrixRow.getNumElements(); i++){
00793
00794 if ( !si.isFreeBinary(indices[i]) ) {
00795
00796 if(elements[i]<-epsilon_){
00797
00798 if (colupper[indices[i]] < si.getInfinity()){
00799
00800 b=b-elements[i]*colupper[indices[i]];
00801 }
00802 else {
00803 return 0;
00804 }
00805 }
00806
00807 else if(elements[i]>epsilon_){
00808
00809 if (collower[indices[i]] > -si.getInfinity()){
00810
00811 b=b-elements[i]*collower[indices[i]];
00812 }
00813 else {
00814 return 0;
00815 }
00816 }
00817
00818
00819 }
00820
00821
00822
00823
00824 else{
00825 krow.insert(indices[i], elements[i]);
00826
00827
00828
00829 if(xstar[indices[i]] > epsilon_ && xstar[indices[i]] < onetol_)
00830 nBinUnsat++;
00831
00832
00833
00834
00835
00836 if (fabs(elements[i]) > maxKrowElement)
00837 maxKrowElement = fabs(elements[i]);
00838 if (fabs(elements[i]) < minKrowElement)
00839 minKrowElement = fabs(elements[i]);
00840 }
00841 }
00842
00843
00844
00845
00846
00847
00848
00849 if (krow.getNumElements() < 3 ||
00850 nBinUnsat == 0 ||
00851 maxKrowElement-minKrowElement < 1.0e-3*maxKrowElement ) {
00852 return 0;
00853 }
00854
00855
00856 if (krow.getNumElements()==2) {
00857 const int * indices = krow.getIndices();
00858 double * elements = krow.getElements();
00859 double sum=0.0;
00860 for(i=0; i<2; i++){
00861 int iColumn = indices[i];
00862 sum += elements[i]*xstar[iColumn];
00863 }
00864 if (sum<b-1.0e-4) {
00865 return 0;
00866 } else {
00867 printf("*** Doubleton Row is ");
00868 for(i=0; i<2; i++){
00869 int iColumn = indices[i];
00870 sum += elements[i]*xstar[iColumn];
00871 printf("%d (coeff = %g, value = %g} ",indices[i],
00872 elements[i],xstar[iColumn]);
00873 }
00874 printf("<= %g - go for it\n",b);
00875 }
00876 }
00877
00878
00879
00880
00881
00882
00883
00884 {
00885 const int s = krow.getNumElements();
00886 const int * indices = krow.getIndices();
00887 double * elements = krow.getElements();
00888 for(i=0; i<s; i++){
00889 if (elements[i] < -epsilon_) {
00890 complement[indices[i]]= 1;
00891 elements[i] *= -1;
00892 b+=elements[i];
00893 xstar[indices[i]]=1.0-xstar[indices[i]];
00894 }
00895 }
00896 }
00897
00898
00899
00900
00901
00902 if (b < 0 ){
00903 OsiColCut cc;
00904 int index = krow.getIndices()[0];
00905 const double fakeLb = colupper[index] + 1.0;;
00906 const double fakeUb = collower[index];
00907 assert( fakeUb < fakeLb );
00908 cc.setLbs( 1, &index, &fakeLb);
00909 cc.setUbs( 1, &index, &fakeLb);
00910 cc.setEffectiveness(DBL_MAX);
00911 cs.insert(cc);
00912 #ifdef PRINT_DEBUG
00913 printf("Cgl: Problem is infeasible\n");
00914 #endif
00915 }
00916
00917
00918
00919
00920
00921 int fixed = 0;
00922 CoinPackedVector fixedBnd;
00923 for(i=0; i<krow.getNumElements(); i++){
00924 if (krow.getElements()[i]> b){
00925 fixedBnd.insert(krow.getIndices()[i],complement[krow.getIndices()[i]]);
00926 #ifdef PRINT_DEBUG
00927 printf("Variable %i being fixed to %i due to row %i.\n",
00928 krow.getIndices()[i],complement[krow.getIndices()[i]],rowIndex);
00929 #endif
00930 fixed = 1;
00931 }
00932 }
00933
00934
00935
00936 if (fixed) {
00937 OsiColCut cc;
00938 cc.setLbs(fixedBnd);
00939 cc.setUbs(fixedBnd);
00940 cc.setEffectiveness(DBL_MAX);
00941 return 0;
00942 }
00943
00944 return 1;
00945 }
00946
00947
00948
00949
00950
00951
00952
00953
00954
00955
00956 int
00957 CglKnapsackCover::deriveAKnapsack(
00958 const OsiSolverInterface & si,
00959 OsiCuts & cs,
00960 CoinPackedVector & krow,
00961 double & b,
00962 int * complement,
00963 double * xstar,
00964 int rowIndex,
00965 const CoinPackedVectorBase & matrixRow ) const
00966 {
00967
00968 const char rowsense = si.getRowSense()[rowIndex];
00969
00970
00971 if (rowsense=='E' || rowsense=='N') {
00972 return 0;
00973 }
00974
00975 bool treatAsLRow = (rowsense=='L');
00976 const int * indices = matrixRow.getIndices();
00977 const double * elements = matrixRow.getElements();
00978 int numberElements = matrixRow.getNumElements();
00979 return deriveAKnapsack( si, cs, krow, treatAsLRow, b, complement,
00980 xstar, rowIndex, numberElements, indices,
00981 elements);
00982 }
00983
00984
00985
00986
00987
00988
00989
00990
00991 int
00992 CglKnapsackCover::findLPMostViolatedMinCover(
00993 int nCols,
00994 int row,
00995 CoinPackedVector & krow,
00996 double & b,
00997 double * xstar,
00998 CoinPackedVector & cover,
00999 CoinPackedVector & remainder) const
01000 {
01001
01002
01003
01004
01005
01006
01007
01008
01009
01010
01011
01012
01013
01014
01015
01016
01017
01018
01019
01020
01021
01022
01023
01024
01025
01026
01027
01028
01029
01030
01031
01032
01033
01034
01035
01036
01037
01038
01039 double elementSum = krow.sum();
01040
01041
01042
01043 if (elementSum < b + epsilon_) {
01044 return -1;
01045 }
01046
01047
01048
01049
01050 double * ratio= new double[nCols];
01051 memset(ratio, 0, (nCols*sizeof(double)));
01052
01053 int i;
01054 for (i=0; i<krow.getNumElements(); i++){
01055 if (fabs(krow.getElements()[i])> epsilon_ ){
01056 ratio[krow.getIndices()[i]]=
01057 (1.0-xstar[krow.getIndices()[i]]) / (krow.getElements()[i]);
01058 }
01059 else {
01060 ratio[krow.getIndices()[i]] = 0.0;
01061 }
01062 }
01063
01064
01065 CoinDecrSolutionOrdered dso(ratio);
01066 krow.sort(dso);
01067
01068
01069 int r = 0;
01070 double sum = krow.getElements()[0];
01071 while ( sum <= (elementSum - b - epsilon_ ) ){
01072 r++;
01073 sum += krow.getElements()[r];
01074 }
01075
01076
01077
01078
01079
01080
01081
01082
01083
01084
01085
01086
01087
01088
01089
01090
01091
01092
01093
01094 int nCover;
01095
01096 double lpoofv=0.0;
01097 for (i=r+1; i<krow.getNumElements(); i++){
01098 lpoofv += (1-xstar[krow.getIndices()[i]]);
01099 }
01100 double ipofv = lpoofv + (1-xstar[krow.getIndices()[r]]);
01101
01102
01103 if (ipofv > 1.0 - epsilon_){
01104 delete [] ratio;
01105 return -1;
01106 }
01107 else {
01108
01109
01110 nCover = krow.getNumElements() - r;
01111 double coverSum =0.0;
01112 cover.reserve(nCover);
01113 remainder.reserve(r);
01114
01115 for (i=r; i<krow.getNumElements(); i++){
01116 cover.insert(krow.getIndices()[i],krow.getElements()[i]);
01117 coverSum += krow.getElements()[i];
01118 }
01119 for (i=0; i<r; i++){
01120 remainder.insert(krow.getIndices()[i],krow.getElements()[i]);
01121 }
01122
01123 #ifdef PRINT_DEBUG
01124 if (coverSum <= b){
01125 printf("The identified cover is NOT a cover\n");
01126 abort();
01127 }
01128 #endif
01129
01130
01131 cover.sortDecrElement();
01132
01133
01134
01135
01136
01137
01138 double oneLessCoverSum = coverSum - cover.getElements()[nCover-1];
01139 while (oneLessCoverSum > b){
01140
01141 remainder.insert(cover.getIndices()[nCover-1],
01142 cover.getElements()[nCover-1]);
01143 cover.truncate(nCover-1);
01144 nCover--;
01145 oneLessCoverSum -= cover.getElements()[nCover-1];
01146 }
01147
01148 if (nCover<2){
01149 #ifdef PRINT_DEBUG
01150 printf("nCover < 2...aborting\n");
01151 #endif
01152 abort();
01153 }
01154
01155 #ifdef PRINT_DEBUG
01156 printf("\
01157 Lp relax of most violated minimal cover: row %i has cover of size %i.\n",
01158 row,nCover);
01159
01160 for (i=0; i<cover.getNumElements(); i++){
01161 printf("index %i, element %g, xstar value % g \n",
01162 cover.getIndices()[i],cover.getElements()[i],
01163 xstar[cover.getIndices()[i]]);
01164
01165 }
01166 printf("The b = %g, and the cover sum is %g\n\n", b, cover.sum());
01167 #endif
01168
01169 #ifdef P0201
01170 double ppsum=0.0;
01171 for (i=0; i<nCover; i++){
01172 ppsum += p0201[krow.getIndices()[i]];
01173 }
01174
01175 if (ppsum > nCover-1){
01176 printf("\
01177 \nBad cover from lp relax of most violated cover..aborting\n");
01178 abort();
01179 }
01180 #endif
01181
01182
01183 delete [] ratio;
01184 return 1;
01185 }
01186 }
01187
01188
01189
01190
01191
01192
01193
01194
01195 int
01196 CglKnapsackCover::findExactMostViolatedMinCover(
01197 int nCols,
01198 int row,
01199 CoinPackedVector & krow,
01200 double b,
01201 double * xstar,
01202 CoinPackedVector & cover,
01203 CoinPackedVector & remainder) const
01204 {
01205
01206
01207
01208
01209
01210
01211
01212
01213
01214
01215
01216
01217
01218
01219
01220
01221
01222
01223
01224
01225
01226
01227
01228
01229
01230
01231
01232
01233
01234 double elementSum = krow.sum();
01235
01236
01237
01238 if (elementSum < b + epsilon_) {
01239 #ifdef PRINT_DEBUG
01240 printf("Redundant/useless adjusted row\n");
01241 #endif
01242 return -1;
01243 }
01244
01245
01246
01247
01248 double * ratio= new double[nCols];
01249 memset(ratio, 0, (nCols*sizeof(double)));
01250
01251 int i;
01252 {
01253 const int * indices = krow.getIndices();
01254 const double * elements = krow.getElements();
01255 for (i=0; i<krow.getNumElements(); i++){
01256 if (fabs(elements[i])> epsilon_ ){
01257 ratio[indices[i]]= (1.0-xstar[indices[i]]) / elements[i];
01258 }
01259 else {
01260 ratio[indices[i]] = 0.0;
01261 }
01262 }
01263 }
01264
01265
01266 CoinDecrSolutionOrdered dso(ratio);
01267 krow.sort(dso);
01268
01269 #ifdef CGL_DEBUG
01270
01271 for ( i=1; i<krow.getNumElements(); i++ ) {
01272 double ratioim1 = ratio[krow.getIndices()[i-1]];
01273 double ratioi= ratio[krow.getIndices()[i]];
01274 assert( ratioim1 >= ratioi );
01275 }
01276 #endif
01277
01278
01279
01280
01281
01282
01283 double objConst = 0.0;
01284 double exactOptVal = -1.0;
01285 int * exactOptSol = new int[krow.getNumElements()];
01286 double * p = new double[krow.getNumElements()];
01287 double * w = new double[krow.getNumElements()];
01288 int kk;
01289 for (kk=0; kk<krow.getNumElements(); kk++){
01290 p[kk]=1.0-xstar[krow.getIndices()[kk]];
01291 w[kk]=krow.getElements()[kk];
01292 objConst+=p[kk];
01293 }
01294
01295
01296 exactSolveKnapsack(krow.getNumElements(), (elementSum-b-epsilon_), p, w,
01297 exactOptVal, exactOptSol);
01298
01299 if(objConst-exactOptVal < 1){
01300 cover.reserve(krow.getNumElements());
01301 remainder.reserve(krow.getNumElements());
01302
01303
01304
01305 double coverElementSum = 0;
01306 for(kk=0;kk<krow.getNumElements();kk++){
01307 if(exactOptSol[kk]==0){
01308 cover.insert(krow.getIndices()[kk],krow.getElements()[kk]);
01309 coverElementSum += krow.getElements()[kk];
01310 }
01311 else {
01312 remainder.insert(krow.getIndices()[kk],krow.getElements()[kk]);
01313 }
01314 }
01315
01316 cover.sortDecrElement();
01317
01318
01319
01320
01321
01322 double oneLessCoverElementSum =
01323 coverElementSum - cover.getElements()[cover.getNumElements()-1];
01324 while (oneLessCoverElementSum > b){
01325
01326 remainder.insert(cover.getIndices()[cover.getNumElements()-1],
01327 cover.getElements()[cover.getNumElements()-1]);
01328 cover.truncate(cover.getNumElements()-1);
01329 oneLessCoverElementSum -= cover.getElements()[cover.getNumElements()-1];
01330 }
01331
01332 #ifdef PRINT_DEBUG
01333 printf("Exact Most Violated Cover: row %i has cover of size %i.\n",
01334 row,cover.getNumElements());
01335
01336 for (i=0; i<cover.getNumElements(); i++){
01337 printf("index %i, element %g, xstar value % g \n",
01338 cover.getIndices()[i], cover.getElements()[i],
01339 xstar[cover.getIndices()[i]]);
01340
01341 }
01342 printf("The b = %g, and the cover sum is %g\n\n", b, cover.sum() );
01343 #endif
01344
01345
01346 delete [] exactOptSol;
01347 delete [] p;
01348 delete [] w;
01349 delete [] ratio;
01350
01351 return 1;
01352 }
01353
01354
01355 delete [] exactOptSol;
01356 delete [] p;
01357 delete [] w;
01358 delete [] ratio;
01359
01360 return 0;
01361
01362 }
01363
01364
01365
01366
01367
01368
01369 int
01370 CglKnapsackCover::findPseudoJohnAndEllisCover(
01371 int row,
01372 CoinPackedVector & krow,
01373 double & b,
01374 double * xstar,
01375 CoinPackedVector & cover,
01376 CoinPackedVector & remainder) const
01377
01378 {
01379
01380
01381
01382
01383
01384
01385
01386
01387
01388
01389
01390
01391
01392
01393
01394
01395
01396
01397
01398
01399
01400
01401
01402
01403
01404
01405
01406
01407
01408
01409
01410
01411
01412
01413
01414
01415
01416
01417
01418
01419
01420 cover.reserve(krow.getNumElements());
01421 remainder.reserve(krow.getNumElements());
01422
01423 double unsatRhs = b;
01424
01425
01426 CoinPackedVector unsat;
01427 unsat.reserve(krow.getNumElements());
01428
01429
01430 CoinPackedVector atOne;
01431 atOne.reserve(krow.getNumElements());
01432
01433
01434
01435
01436
01437
01438
01439 int i;
01440 for (i=0; i<krow.getNumElements(); i++){
01441
01442 if (xstar[krow.getIndices()[i]] > onetol_){
01443 atOne.insert(krow.getIndices()[i],krow.getElements()[i]);
01444 unsatRhs -= krow.getElements()[i];
01445 }
01446 else if (xstar[krow.getIndices()[i]] >= epsilon_){
01447 unsat.insert(krow.getIndices()[i],krow.getElements()[i]) ;
01448 }
01449 else {
01450 remainder.insert(krow.getIndices()[i],krow.getElements()[i]);
01451 }
01452 }
01453
01454
01455 CoinDecrSolutionOrdered decrSol(xstar);
01456 unsat.sort(decrSol);
01457
01458 #ifdef CGL_DEBUG
01459
01460 for (i=1; i<unsat.getNumElements(); i++){
01461 double xstarim1= xstar[unsat.getIndices()[i-1]];
01462 double xstari= xstar[unsat.getIndices()[i]];
01463 assert( xstarim1 >= xstari );
01464 }
01465 #endif
01466
01467
01468 double bigCoef= 0.0;
01469
01470 int bigIndex = 0;
01471 for (i=0; i<unsat.getNumElements(); i++){
01472 if (unsat.getElements()[i]>bigCoef){
01473 bigCoef = unsat.getElements()[i];
01474 bigIndex = i;
01475 }
01476 }
01477
01478
01479 i=0;
01480 double margin = unsatRhs;
01481 int gotCover=0;
01482 int j;
01483
01484
01485
01486 while (i<unsat.getNumElements() && !gotCover){
01487 margin -= unsat.getElements()[i];
01488
01489
01490 if (i == bigIndex){
01491 bigCoef = 0.0;
01492 bigIndex = 0;
01493 for (j=i+1; j<unsat.getNumElements(); j++){
01494 double temp = unsat.getElements()[j];
01495 if (temp > bigCoef ){
01496 bigCoef = temp;
01497 bigIndex = j;
01498 }
01499 }
01500 }
01501
01502 if (bigCoef > margin+epsilon2_) gotCover = 1;
01503 i++;
01504 }
01505
01506
01507 if(gotCover){
01508 j=i;
01509 if (j<unsat.getNumElements()){
01510 while (unsat.getElements()[j]< margin) {
01511 j++;
01512 }
01513
01514 unsat.swap(i,j);
01515 i++;
01516 }
01517
01518
01519
01520 int nCover = i;
01521 double coverElementSum = 0.0;
01522 double coverXstarSum = 0.0;
01523 int k;
01524 for (k=0; k<nCover; k++){
01525 coverElementSum += unsat.getElements()[k];
01526 coverXstarSum += xstar[unsat.getIndices()[k]];
01527 }
01528
01529
01530
01531
01532
01533
01534 if (coverXstarSum > (nCover-1) && coverElementSum > unsatRhs+epsilon2_){
01535 for (i=nCover; i<unsat.getNumElements(); i++) {
01536 remainder.insert(unsat.getIndices()[i],unsat.getElements()[i]);
01537 }
01538 unsat.truncate(nCover);
01539 cover = unsat;
01540 cover.append(atOne);
01541
01542 for (k=nCover; k<cover.getNumElements(); k++){
01543 coverElementSum+=cover.getElements()[k];
01544 coverXstarSum+=xstar[cover.getIndices()[k]];
01545 }
01546
01547
01548 int size = cover.getNumElements() + remainder.getNumElements();
01549 int krowsize = krow.getNumElements();
01550 assert( size == krowsize );
01551
01552
01553 cover.sortDecrElement();
01554
01555
01556
01557
01558
01559
01560 double oneLessCoverElementSum =
01561 coverElementSum - cover.getElements()[cover.getNumElements()-1];
01562 while (oneLessCoverElementSum > b){
01563
01564 remainder.insert(cover.getIndices()[cover.getNumElements()-1],
01565 cover.getElements()[cover.getNumElements()-1]);
01566 cover.truncate(cover.getNumElements()-1);
01567 oneLessCoverElementSum -= cover.getElements()[cover.getNumElements()-1];
01568 }
01569
01570 #ifdef PRINT_DEBUG
01571 if (coverXstarSum > (nCover-1) && coverElementSum > b){
01572 printf("John and Ellis: row %i has cover of size %i.\n",
01573 row,cover.getNumElements());
01574
01575 for (i=0; i<cover.getNumElements(); i++){
01576 printf("index %i, element %g, xstar value % g \n",
01577 cover.getIndices()[i], cover.getElements()[i],
01578 xstar[cover.getIndices()[i]]);
01579 }
01580 printf("The b = %g, and the cover element sum is %g\n\n",b,cover.sum());
01581 }
01582 #endif
01583
01584 }
01585
01586 else {
01587
01588 gotCover = 0;
01589 }
01590 }
01591
01592
01593 if (!gotCover || cover.getNumElements() < 2) {
01594 return -1;
01595 }
01596
01597 return 1;
01598 }
01599
01600
01601
01602
01603
01604
01605
01606
01607
01608
01609
01610
01611 int
01612 CglKnapsackCover::findJohnAndEllisCover(
01613 int row,
01614 CoinPackedVector & krow,
01615 double & b,
01616 double * xstar,
01617 CoinPackedVector & fracCover,
01618 CoinPackedVector & atOne,
01619 CoinPackedVector & remainder) const
01620
01621 {
01622
01623
01624
01625
01626
01627
01628
01629
01630
01631
01632
01633
01634
01635
01636
01637
01638
01639
01640
01641
01642
01643
01644
01645
01646
01647
01648
01649
01650
01651
01652
01653
01654
01655
01656
01657
01658
01659
01660 fracCover.reserve(krow.getNumElements());
01661 remainder.reserve(krow.getNumElements());
01662 atOne.reserve(krow.getNumElements());
01663
01664 double unsatRhs = b;
01665
01666
01667 CoinPackedVector unsat;
01668 unsat.reserve(krow.getNumElements());
01669
01670
01671
01672
01673
01674
01675
01676
01677
01678
01679 int i;
01680 for (i=0; i<krow.getNumElements(); i++){
01681
01682 if (xstar[krow.getIndices()[i]] > onetol_){
01683 atOne.insert(krow.getIndices()[i],krow.getElements()[i]);
01684 unsatRhs -= krow.getElements()[i];
01685 }
01686 else if (xstar[krow.getIndices()[i]] >= epsilon_){
01687 unsat.insert(krow.getIndices()[i],krow.getElements()[i]) ;
01688 }
01689 else {
01690 remainder.insert(krow.getIndices()[i],krow.getElements()[i]);
01691 }
01692 }
01693
01694
01695 CoinDecrSolutionOrdered decrSol(xstar);
01696 unsat.sort(decrSol);
01697
01698 #ifdef CGL_DEBUG
01699
01700 for (i=1; i<unsat.getNumElements(); i++){
01701 double xstarim1 = xstar[unsat.getIndices()[i-1]];
01702 double xstari= xstar[unsat.getIndices()[i]];
01703 assert( xstarim1 >= xstari );
01704 }
01705 #endif
01706
01707
01708 double bigCoef= 0.0;
01709
01710 int bigIndex = 0;
01711 for (i=0; i<unsat.getNumElements(); i++){
01712 if (unsat.getElements()[i]>bigCoef){
01713 bigCoef = unsat.getElements()[i];
01714 bigIndex = i;
01715 }
01716 }
01717
01718
01719 i=0;
01720 double margin = unsatRhs;
01721 int gotCover=0;
01722 int j;
01723
01724
01725
01726 while (i<unsat.getNumElements() && !gotCover){
01727 margin -= unsat.getElements()[i];
01728
01729
01730 if (i == bigIndex){
01731 bigCoef = 0.0;
01732 bigIndex = 0;
01733 for (j=i+1; j<unsat.getNumElements(); j++){
01734 double temp = unsat.getElements()[j];
01735 if (temp > bigCoef ){
01736 bigCoef = temp;
01737 bigIndex = j;
01738 }
01739 }
01740 }
01741
01742 if (bigCoef > margin+epsilon2_) gotCover = 1;
01743 i++;
01744 }
01745
01746
01747 if(gotCover){
01748 j=i;
01749 if (j<unsat.getNumElements()){
01750 while (unsat.getElements()[j]< margin) {
01751 j++;
01752 }
01753
01754 unsat.swap(i,j);
01755 i++;
01756 }
01757
01758
01759
01760 int nCover = i;
01761 double coverElementSum = 0.0;
01762 int k;
01763 for (k=0; k<nCover; k++){
01764 coverElementSum += unsat.getElements()[k];
01765 }
01766
01767
01768
01769
01770
01771
01772
01773 if (coverElementSum > unsatRhs+epsilon2_){
01774 for (i=nCover; i<unsat.getNumElements(); i++) {
01775 remainder.insert(unsat.getIndices()[i],unsat.getElements()[i]);
01776 }
01777 unsat.truncate(nCover);
01778 fracCover = unsat;
01779
01780
01781
01782 int size = (fracCover.getNumElements() + remainder.getNumElements() +
01783 atOne.getNumElements());
01784 int krowsize = krow.getNumElements();
01785 assert( size == krowsize );
01786
01787
01788 fracCover.sortDecrElement();
01789
01790
01791
01792
01793 #if 0
01794
01795 double oneLessCoverElementSum =
01796 coverElementSum-fracCover.getElements()[fracCover.getNumElements()-1];
01797 while (oneLessCoverElementSum > b){
01798
01799 remainder.insert(fracCover.getIndices()[fracCover.getNumElements()-1],
01800 fracCover.getElements()[fracCover.getNumElements()-1]);
01801 fracCover.truncate(fracCover.getNumElements()-1);
01802 oneLessCoverElementSum -=
01803 fracCover.getElements()[fracCover.getNumElements()-1];
01804 }
01805 #endif
01806
01807 #ifdef PRINT_DEBUG
01808 printf("More Exactly John and Ellis:");
01809 printf(" row %i has -reduced--fractional- cover of size %i.\n",
01810 row,fracCover.getNumElements());
01811 double sumFracCover = 0.0;
01812 for (i=0; i<fracCover.getNumElements(); i++){
01813 printf("index %i, element %g, xstar value % g \n",
01814 fracCover.getIndices()[i],fracCover.getElements()[i],
01815 xstar[fracCover.getIndices()[i]]);
01816 sumFracCover += fracCover.getElements()[i];
01817 }
01818 double sumAtOne = 0.0;
01819 printf("There are %i variables at one:\n",atOne.getNumElements());
01820 for (i=0; i<atOne.getNumElements(); i++){
01821 printf("index %i, element %g, xstar value % g \n",
01822 atOne.getIndices()[i],atOne.getElements()[i],
01823 xstar[atOne.getIndices()[i]]);
01824 sumAtOne += atOne.getElements()[i];
01825 }
01826 printf("The b = %g, sumAtOne = %g, unsatRhs = b-sumAtOne = %g, ",
01827 b, sumAtOne, unsatRhs);
01828 printf("and the (fractional) cover element sum is %g\n\n", sumFracCover);
01829 #endif
01830
01831 }
01832
01833 else {
01834
01835 gotCover = 0;
01836 }
01837 }
01838
01839
01840
01841 if (!gotCover) {
01842 return -1;
01843 }
01844
01845 return 1;
01846 }
01847
01848
01849
01850
01851
01852
01853
01854
01855 int
01856 CglKnapsackCover::findGreedyCover(
01857 int row,
01858 CoinPackedVector & krow,
01859 double & b,
01860 double * xstar,
01861 CoinPackedVector & cover,
01862 CoinPackedVector & remainder
01863 ) const
01864
01865
01866
01867
01868 {
01869 int i;
01870 int gotCover =0;
01871
01872 cover.reserve(krow.getNumElements());
01873 remainder.reserve(krow.getNumElements());
01874
01875
01876 krow.sortDecrElement();
01877
01878
01879
01880 double greedyElementSum = 0.0;
01881 double greedyXstarSum = 0.0;
01882
01883 for (i=0;i<krow.getNumElements();i++){
01884
01885 if (xstar[krow.getIndices()[i]] >= epsilon_ &&
01886 xstar[krow.getIndices()[i]] <= onetol_ &&
01887 !gotCover){
01888 greedyElementSum += krow.getElements()[i];
01889 greedyXstarSum += xstar[krow.getIndices()[i]];
01890 cover.insert(krow.getIndices()[i],krow.getElements()[i]);
01891 if (greedyElementSum > b+epsilon2_){
01892 gotCover = 1;
01893 }
01894 }
01895 else{
01896 remainder.insert(krow.getIndices()[i],krow.getElements()[i]);
01897 }
01898 }
01899
01900
01901 int size = remainder.getNumElements()+cover.getNumElements();
01902 int krowsize = krow.getNumElements();
01903 assert( size==krowsize );
01904
01905
01906 if ( (greedyXstarSum<=(cover.getNumElements()-1)+epsilon2_) ||
01907 (!gotCover) ||
01908 (cover.getNumElements() < 2)){
01909 return -1;
01910 }
01911
01912 #ifdef PRINT_DEBUG
01913 printf("Greedy cover: row %i has cover of size %i\n",
01914 row,cover.getNumElements());
01915 for (i=0; i<cover.getNumElements(); i++){
01916 printf("index %i, element %g, xstar value % g \n",
01917 cover.getIndices()[i], cover.getElements()[i],
01918 xstar[cover.getIndices()[i]]);
01919 }
01920 printf("The b = %g, and the cover sum is %g\n\n", b, greedyElementSum);
01921 #endif
01922
01923 return 1;
01924 }
01925
01926
01927
01928
01929
01930
01931
01932
01933
01934
01935
01936
01937
01938
01939
01940
01941
01942
01943
01944
01945
01946 void
01947 CglKnapsackCover::liftUpDownAndUncomplementAndAdd(
01948 int nCols,
01949 double * xstar,
01950 int * complement,
01951 int row,
01952 int nRowElem,
01953 double & b,
01954
01955
01956
01957
01958
01959 CoinPackedVector & fracCover,
01960
01961 CoinPackedVector & atOne,
01962
01963 CoinPackedVector & remainder,
01964
01965 OsiCuts & cs ) const
01966 {
01967 CoinPackedVector cut;
01968
01969
01970 cut.reserve(nRowElem);
01971
01972
01973 cut.setConstant(fracCover.getNumElements(),fracCover.getIndices(),1.0);
01974
01975
01976
01977 double cutRhs=fracCover.getNumElements()-1;
01978
01979
01980
01981 double unsatRhs = 0, sumAtOne = 0;
01982 int i;
01983 for (i=0; i<atOne.getNumElements(); i++){
01984 sumAtOne += atOne.getElements()[i];
01985 }
01986 unsatRhs=b-sumAtOne;
01987 int firstFrac = fracCover.getIndices()[0];
01988 if (unsatRhs<=0.0&&fabs(xstar[firstFrac])>epsilon2_) {
01989 printf("At one %d\n",atOne.getNumElements());
01990 for (i=0; i<atOne.getNumElements(); i++){
01991 int iColumn = atOne.getIndices()[i];
01992 printf("%d %g %g\n",atOne.getIndices()[i],atOne.getElements()[i],
01993 xstar[iColumn]);
01994 }
01995 printf("frac %d\n",fracCover.getNumElements());
01996 for (i=0; i<fracCover.getNumElements(); i++){
01997 int iColumn = fracCover.getIndices()[i];
01998 printf("%d %g %g\n",fracCover.getIndices()[i],fracCover.getElements()[i],
01999 xstar[iColumn]);
02000 }
02001 }
02002
02003
02004
02005 if (unsatRhs>0.0&&(remainder.getNumElements()+atOne.getNumElements())> 0){
02006
02007
02008
02009
02010
02011
02012
02013 CoinDecrSolutionOrdered dso1(xstar);
02014 remainder.sort(dso1);
02015
02016
02017
02018
02019 CoinPackedVector a(fracCover);
02020 CoinPackedVector alpha;
02021 int i;
02022 for (i=0; i<fracCover.getNumElements(); i++){
02023 alpha.insert(fracCover.getIndices()[i],1.0);
02024 }
02025
02026 int * x = new int[nRowElem];
02027 double psi_j=0.0;
02028
02029
02030
02031
02032
02033
02034 double * ratio= new double[nCols];
02035 memset(ratio, 0, (nCols*sizeof(double)));
02036 double alphasize = alpha.getNumElements();
02037 double asize = a.getNumElements();
02038 assert( alphasize == asize );
02039
02040 for (i=0; i<a.getNumElements(); i++){
02041 if (fabs(a.getElements()[i])> epsilon_ ){
02042 ratio[a.getIndices()[i]]=alpha.getElements()[i]/a.getElements()[i];
02043 }
02044 else {
02045 ratio[a.getIndices()[i]] = 0.0;
02046 }
02047 }
02048
02049 CoinDecrSolutionOrdered dso2(ratio);
02050 a.sort(dso2);
02051 alpha.sort(dso2);
02052
02053 #ifdef CGL_DEBUG
02054
02055 for ( i=1; i<a.getNumElements(); i++ ) {
02056 int alphai= alpha.getIndices()[i];
02057 int ai = a.getIndices()[i];
02058 assert( alphai == ai);
02059 }
02060 #endif
02061
02062
02063 int j;
02064 for (j=0; j<remainder.getNumElements(); j++){
02065
02066
02067
02068
02069
02070
02071
02072
02073
02074 if (unsatRhs - remainder.getElements()[j] < epsilon_){
02075 psi_j = cutRhs;
02076 }
02077 else {
02078 exactSolveKnapsack(alpha.getNumElements(),
02079 unsatRhs-remainder.getElements()[j],
02080 alpha.getElements(),a.getElements(),psi_j,x);
02081 }
02082
02083
02084 alpha.insert(remainder.getIndices()[j],cutRhs-psi_j);
02085 a.insert(remainder.getIndices()[j],remainder.getElements()[j]);
02086
02087
02088
02089 if (fabs(cutRhs-psi_j)>epsilon_)
02090 cut.insert(remainder.getIndices()[j],cutRhs-psi_j);
02091
02092 ratio[remainder.getIndices()[j]]=
02093 (cutRhs-psi_j)/remainder.getElements()[j];
02094 CoinDecrSolutionOrdered dso(ratio);
02095 a.sort(dso);
02096 alpha.sort(dso);
02097 }
02098
02099
02100 for (j=0; j<atOne.getNumElements(); j++){
02101
02102
02103
02104
02105
02106
02107
02108
02109 exactSolveKnapsack(alpha.getNumElements(),
02110 unsatRhs+atOne.getElements()[j],
02111 alpha.getElements(),a.getElements(),psi_j,x);
02112 alpha.insert(atOne.getIndices()[j],psi_j-cutRhs);
02113 a.insert(atOne.getIndices()[j],atOne.getElements()[j]);
02114
02115
02116 if (fabs(psi_j-cutRhs)>epsilon_)
02117 cut.insert(atOne.getIndices()[j],psi_j-cutRhs);
02118
02119 #ifdef CGL_DEBUG
02120 assert ( fabs(atOne.getElements()[j])> epsilon_ );
02121 #else
02122 if ( fabs(atOne.getElements()[j])<= epsilon_ ) {
02123
02124 cutRhs = DBL_MAX;
02125 break;
02126 }
02127 #endif
02128 ratio[atOne.getIndices()[j]]=(psi_j-cutRhs)/atOne.getElements()[j];
02129
02130
02131 cutRhs = psi_j ;
02132 unsatRhs += atOne.getElements()[j];
02133
02134 CoinDecrSolutionOrdered dso(ratio);
02135 a.sort(dso);
02136 alpha.sort(dso);
02137 }
02138 delete [] x;
02139 delete [] ratio;
02140 }
02141
02142
02143
02144
02145
02146 double sum=0;
02147 for (i=0; i<cut.getNumElements(); i++){
02148 sum+= cut.getElements()[i]*xstar[cut.getIndices()[i]];
02149 }
02150 if (sum > cutRhs+epsilon2_){
02151 #ifdef PRINT_DEBUG
02152 printf("Sequentially lifted UpDown cover cut of ");
02153 printf("size %i derived from fracCover of size %i.\n",
02154 cut.getNumElements(), fracCover.getNumElements());
02155 for (i=0; i<cut.getNumElements(); i++){
02156 printf("index %i, element %g, xstar value % g \n",
02157 cut.getIndices()[i],cut.getElements()[i],
02158 xstar[cut.getIndices()[i]]);
02159 }
02160 printf("The cutRhs = %g, and the alpha_j*xstar_j sum is %g\n\n",
02161 cutRhs, sum);
02162 #endif
02163
02164
02165 int k;
02166 const int s = cut.getNumElements();
02167 const int * indices = cut.getIndices();
02168 double * elements = cut.getElements();
02169 for (k=0; k<s; k++){
02170 if (complement[indices[k]]) {
02171
02172
02173 elements[k] *= -1;
02174 cutRhs += elements[k];
02175 }
02176 }
02177
02178
02179
02180 OsiRowCut rc;
02181 rc.setRow(cut);
02182 #ifdef CGL_DEBUG
02183 {
02184 double * elements = cut.getElements();
02185 int * indices = cut.getIndices();
02186 int n=cut.getNumElements();
02187 for (k=0; k<n; k++){
02188 assert(indices[k]>=0);
02189 assert(elements[k]);
02190 }
02191 }
02192 #endif
02193 rc.setLb(-DBL_MAX);
02194 rc.setUb(cutRhs);
02195
02196
02197
02198 #ifdef PRINT_DEBUG
02199 {
02200 int k;
02201 printf("cutrhs %g %d elements\n",cutRhs,cut.getNumElements());
02202 double * elements = cut.getElements();
02203 int * indices = cut.getIndices();
02204 for (k=0; k<cut.getNumElements(); k++){
02205 printf("%d %g\n",indices[k],elements[k]);
02206 }
02207 }
02208 #endif
02209 cs.insert(rc);
02210 }
02211 }
02212
02213
02214
02215
02216
02217
02218
02219
02220
02221
02222
02223
02224 void
02225 CglKnapsackCover::seqLiftAndUncomplementAndAdd(
02226 int nCols,
02227 double * xstar,
02228 int * complement,
02229 int row,
02230
02231 int nRowElem,
02232
02233 double & b,
02234
02235 CoinPackedVector & cover,
02236 CoinPackedVector & remainder,
02237 OsiCuts & cs) const
02238 {
02239 CoinPackedVector cut;
02240
02241
02242 cut.reserve(nRowElem);
02243
02244
02245 cut.setConstant(cover.getNumElements(),cover.getIndices(),1.0);
02246
02247
02248 double cutRhs=cover.getNumElements()-1;
02249
02250
02251 if (remainder.getNumElements()> 0){
02252
02253
02254
02255
02256
02257 CoinDecrSolutionOrdered dso1(xstar);
02258 remainder.sort(dso1);
02259
02260
02261
02262
02263 CoinPackedVector a(cover);
02264 CoinPackedVector alpha;
02265 int i;
02266 for (i=0; i<cover.getNumElements(); i++){
02267 alpha.insert(cover.getIndices()[i],1.0);
02268 }
02269
02270 int * x = new int[nRowElem];
02271 double psi_j=0.0;
02272
02273
02274
02275
02276
02277 double * ratio= new double[nCols];
02278 memset(ratio, 0, (nCols*sizeof(double)));
02279 int alphasize = alpha.getNumElements();
02280 int asize = a.getNumElements();
02281 assert( alphasize == asize );
02282
02283 for (i=0; i<a.getNumElements(); i++){
02284 if (fabs(a.getElements()[i])> epsilon_ ){
02285 ratio[a.getIndices()[i]]=alpha.getElements()[i]/a.getElements()[i];
02286 }
02287 else {
02288 ratio[a.getIndices()[i]] = 0.0;
02289 }
02290 }
02291
02292
02293 CoinDecrSolutionOrdered dso2(ratio);
02294
02295
02296
02297 a.sort(dso2);
02298 alpha.sort(dso2);
02299
02300 #ifdef CGL_DEBUG
02301
02302 for ( i=1; i<a.getNumElements(); i++ ) {
02303 int alphai= alpha.getIndices()[i];
02304 int ai = a.getIndices()[i];
02305 assert( alphai == ai);
02306 }
02307 #endif
02308
02309
02310 int j;
02311 for (j=0; j<remainder.getNumElements(); j++){
02312
02313
02314
02315
02316
02317
02318 exactSolveKnapsack(alpha.getNumElements(),
02319 b-remainder.getElements()[j],
02320 alpha.getElements(),a.getElements(),psi_j,x);
02321 alpha.insert(remainder.getIndices()[j],cutRhs-psi_j);
02322 a.insert(remainder.getIndices()[j],remainder.getElements()[j]);
02323
02324
02325 if (fabs(cutRhs-psi_j)>epsilon_)
02326 cut.insert(remainder.getIndices()[j],cutRhs-psi_j);
02327
02328 ratio[remainder.getIndices()[j]]=
02329 (cutRhs-psi_j)/remainder.getElements()[j];
02330 CoinDecrSolutionOrdered dso(ratio);
02331 a.sort(dso);
02332 alpha.sort(dso);
02333 }
02334 delete [] x;
02335 delete [] ratio;
02336 }
02337
02338
02339
02340
02341
02342 double sum=0;
02343 int i;
02344 for (i=0; i<cut.getNumElements(); i++){
02345 sum+= cut.getElements()[i]*xstar[cut.getIndices()[i]];
02346 }
02347 if (sum > cutRhs+epsilon2_){
02348 #ifdef PRINT_DEBUG
02349 printf("Sequentially lifted cover cut of size %i derived from cover of size %i.\n",cut.getNumElements(), cover.getNumElements());
02350 for (i=0; i<cut.getNumElements(); i++){
02351 printf("index %i, element %g, xstar value % g \n", cut.getIndices()[i],cut.getElements()[i], xstar[cut.getIndices()[i]]);
02352 }
02353 printf("The cutRhs = %g, and the alpha_j*xstar_j sum is %g\n\n", cutRhs, sum);
02354 #endif
02355
02356 int k;
02357 const int s = cut.getNumElements();
02358 const int * indices = cut.getIndices();
02359 double * elements = cut.getElements();
02360 for (k=0; k<s; k++){
02361 if (complement[indices[k]]) {
02362
02363
02364 elements[k] *= -1;
02365 cutRhs += elements[k];
02366 }
02367 }
02368
02369
02370 OsiRowCut rc;
02371 rc.setRow(cut);
02372 #ifdef CGL_DEBUG
02373 {
02374 double * elements = cut.getElements();
02375 int * indices = cut.getIndices();
02376 int n=cut.getNumElements();
02377 for (k=0; k<n; k++){
02378 assert(indices[k]>=0);
02379 assert(elements[k]);
02380 }
02381 }
02382 #endif
02383 rc.setLb(-DBL_MAX);
02384 rc.setUb(cutRhs);
02385
02386
02387 #ifdef PRINT_DEBUG
02388 {
02389 int k;
02390 printf("cutrhs %g\n",cutRhs);
02391 double * elements = cut.getElements();
02392 int * indices = cut.getIndices();
02393 for (k=0; k<cut.getNumElements(); k++){
02394 printf("%d %g\n",indices[k],elements[k]);
02395 }
02396 }
02397 #endif
02398 cs.insert(rc);
02399 }
02400 }
02401
02402
02403
02404
02405
02406
02407 int
02408 CglKnapsackCover::liftCoverCut(
02409 double & b,
02410 int nRowElem,
02411 CoinPackedVector & cover,
02412 CoinPackedVector & remainder,
02413 CoinPackedVector & cut) const
02414 {
02415 int i;
02416 int goodCut=1;
02417
02418
02419
02420
02421
02422
02423
02424
02425
02426 double sum = cover.sum();
02427
02428
02429
02430 double lambda = sum-b;
02431 if (lambda < epsilon_) {
02432 #ifdef PRINT_DEBUG
02433 printf("lambda < epsilon....aborting. \n");
02434 std::cout << "lambda " << lambda << " epsilon " << epsilon_ << std::endl;
02435
02436 goodCut=0;
02437 #else
02438
02439 goodCut=0;
02440 #endif
02441 }
02442
02443
02444
02445
02446
02447 double * mu= new double[cover.getNumElements()+1];
02448 double * muMinusLambda= new double[cover.getNumElements()+1];
02449 memset(mu, 0, (cover.getNumElements()+1)*sizeof(double));
02450 memset(muMinusLambda, 0, (cover.getNumElements()+1)*sizeof(double));
02451
02452
02453 muMinusLambda[0]= -lambda;
02454 for(i=1; i<(cover.getNumElements()+1); i++){
02455 mu[i]=mu[i-1]+ cover.getElements()[i-1];
02456 muMinusLambda[i]=mu[i]-lambda;
02457 }
02458
02459 cut.reserve(nRowElem);
02460
02461
02462 cut.setConstant(cover.getNumElements(),cover.getIndices(),1.0);
02463
02464
02465 int h;
02466 if (muMinusLambda[1] >= cover.getElements()[1]-epsilon_){
02467 for (h=0; h<remainder.getNumElements(); h++){
02468 if (remainder.getElements()[h] <= muMinusLambda[1]){
02469
02470 }
02471 else{
02472
02473
02474 int found=0;
02475 i=2;
02476 while (!found && i<(cover.getNumElements()+1)){
02477 if (remainder.getElements()[h] <= muMinusLambda[i]+epsilon_){
02478 bool e = cut.isExistingIndex(remainder.getIndices()[h]);
02479 assert( !e );
02480 cut.insert( remainder.getIndices()[h], i-1.0 );
02481 found=1;
02482 }
02483 i++;
02484 }
02485 if (!found) {
02486 #ifdef CGL_DEBUG
02487 printf("Error: Unable to fix lifted coefficient\n");
02488 abort();
02489 #else
02490 goodCut=0;
02491 #endif
02492 }
02493 }
02494 }
02495 }
02496
02497
02498 else {
02499 double * rho= new double[cover.getNumElements()];
02500 rho[0]=lambda;
02501 for (i=1; i<cover.getNumElements(); i++){
02502 rho[i]=CoinMax(0.0, cover.getElements()[i]- muMinusLambda[1]);
02503 }
02504
02505 int h;
02506 for (h=0; h<remainder.getNumElements(); h++){
02507
02508 int found=0;
02509 i=0;
02510 while(!found && i<cover.getNumElements()){
02511 if (remainder.getElements()[h] <= muMinusLambda[i+1]+epsilon_){
02512 bool notE = !cut.isExistingIndex(remainder.getIndices()[h]);
02513 assert( notE );
02514 if (i)
02515 cut.insert( remainder.getIndices()[h], (double)i );
02516 found=1;
02517 }
02518 else if (remainder.getElements()[h] < muMinusLambda[i+1]+rho[i+1]){
02519 bool notE = !cut.isExistingIndex(remainder.getIndices()[h]);
02520 assert( notE );
02521 double cutCoef = i+1
02522 - (muMinusLambda[i+1]+rho[i+1]-remainder.getElements()[h])/rho[1];
02523 if (fabs(cutCoef)>epsilon_)
02524 cut.insert( remainder.getIndices()[h], cutCoef );
02525 found=1;
02526 }
02527 i++;
02528 }
02529 }
02530 delete [] rho;
02531 }
02532
02533 delete [] muMinusLambda;
02534 delete [] mu;
02535
02536 return goodCut;
02537 }
02538
02539
02540
02541
02542
02543
02544
02545
02546
02547
02548 int
02549 CglKnapsackCover::exactSolveKnapsack(
02550 int n,
02551 double c,
02552 double const *pp,
02553 double const *ww,
02554 double & z,
02555 int * x) const
02556 {
02557
02558
02559
02560
02561
02562
02563
02564
02565
02566
02567
02568
02569
02570
02571
02572
02573
02574
02575
02576
02577
02578
02579 memset(x, 0, (n)*sizeof(int));
02580 int * xhat = new int[n+1];
02581 memset(xhat, 0, (n+1)*sizeof(int));
02582 int j;
02583
02584
02585
02586 double * p = new double[n+2];
02587 double * w = new double[n+2];
02588 int ii;
02589 for (ii=1; ii<n+1; ii++){
02590 p[ii]=pp[ii-1];
02591 w[ii]=ww[ii-1];
02592 }
02593
02594
02595 double zhat = 0.0;
02596 z = 0.0;
02597 double chat = c+epsilon2_;
02598 p[n+1] = 0.0;
02599 w[n+1]= DBL_MAX;
02600 j=1;
02601
02602 while (1){
02603
02604
02605 ii=j;
02606 double wSemiSum = w[j];
02607 double pSemiSum = p[j];
02608 while (wSemiSum <= chat && ii<n+2){
02609 ii++;
02610 wSemiSum+=w[ii];
02611 pSemiSum+=p[ii];
02612 }
02613 if (ii==n+2){
02614 printf("Exceeded iterator limit. Aborting...\n");
02615 abort();
02616 }
02617
02618 wSemiSum -= w[ii];
02619 pSemiSum -= p[ii];
02620 double u = pSemiSum + floor((chat - wSemiSum)*p[ii]/w[ii]);
02621
02622
02623 if (!(z >= zhat + u)) {
02624 do {
02625
02626 while (w[j] <= chat){
02627 chat = chat - w[j];
02628 zhat = zhat + p[j];
02629 xhat[j] = 1;
02630 j+=1;
02631 }
02632 if (j<=n) {
02633 xhat[j]= 0;
02634 j+=1;
02635 }
02636 } while(j==n);
02637
02638
02639 if (j<n)
02640 continue;
02641
02642
02643 if (zhat > z) {
02644 z=zhat;
02645 int k;
02646 for (k=0; k<n; k++){
02647 x[k]=xhat[k+1];
02648 }
02649 }
02650 j=n;
02651 if (xhat[n] == 1){
02652 chat = chat+ w[n];
02653 zhat = zhat-p[n];
02654 xhat[n]=0;
02655 }
02656 }
02657
02658
02659 int i=j-1;
02660 while (!(xhat[i]==1) && i>0){
02661 i--;
02662 }
02663
02664
02665 if (i==0){
02666 delete [] p;
02667 delete [] w;
02668 delete [] xhat;
02669 return 1;
02670 }
02671
02672 chat = chat + w[i];
02673 zhat=zhat -p[i];
02674 xhat[i]=0;
02675 j=i+1;
02676
02677 }
02678 }
02679
02680
02681
02682
02683 CglKnapsackCover::CglKnapsackCover ()
02684 :
02685 CglCutGenerator(),
02686 epsilon_(1.0e-08),
02687 epsilon2_(1.0e-5),
02688 onetol_(1-epsilon_),
02689 maxInKnapsack_(50),
02690 numRowsToCheck_(-1),
02691 rowsToCheck_(0)
02692 {
02693
02694 }
02695
02696
02697
02698
02699 CglKnapsackCover::CglKnapsackCover (const CglKnapsackCover & source) :
02700 CglCutGenerator(source),
02701 epsilon_(source.epsilon_),
02702 epsilon2_(source.epsilon2_),
02703 onetol_(source.onetol_),
02704 maxInKnapsack_(source.maxInKnapsack_),
02705 numRowsToCheck_(source.numRowsToCheck_),
02706 rowsToCheck_(0)
02707 {
02708 if (numRowsToCheck_ > 0) {
02709 rowsToCheck_ = new int[numRowsToCheck_];
02710 CoinCopyN(source.rowsToCheck_, numRowsToCheck_, rowsToCheck_);
02711 }
02712
02713 }
02714
02715
02716
02717
02718 CglKnapsackCover::~CglKnapsackCover ()
02719 {
02720 delete[] rowsToCheck_;
02721
02722 }
02723
02724
02725
02726
02727 CglKnapsackCover &
02728 CglKnapsackCover::operator=(const CglKnapsackCover& rhs)
02729 {
02730 if (this != &rhs) {
02731 CglCutGenerator::operator=(rhs);
02732 epsilon_=rhs.epsilon_;
02733 epsilon2_=rhs.epsilon2_;
02734 onetol_=rhs.onetol_;
02735 maxInKnapsack_=rhs.maxInKnapsack_;
02736 delete[] rowsToCheck_;
02737 numRowsToCheck_ = rhs.numRowsToCheck_;
02738 if (numRowsToCheck_ > 0) {
02739 rowsToCheck_ = new int[numRowsToCheck_];
02740 CoinCopyN(rhs.rowsToCheck_, numRowsToCheck_, rowsToCheck_);
02741 } else {
02742 rowsToCheck_ = 0;
02743 }
02744 }
02745 return *this;
02746 }