00001
00002
00003 #if defined(_MSC_VER)
00004
00005 # pragma warning(disable:4786)
00006 #endif
00007
00008 #include <cstdio>
00009
00010 #ifdef NDEBUG
00011 #undef NDEBUG
00012 #endif
00013 #include <cassert>
00014
00015 #include "CglKnapsackCover.hpp"
00016 #include "CoinPackedMatrix.hpp"
00017
00018
00019 void
00020 CglKnapsackCoverUnitTest(
00021 const OsiSolverInterface * baseSiP,
00022 const std::string mpsDir )
00023 {
00024 int i;
00025 CoinRelFltEq eq(0.000001);
00026
00027
00028 {
00029 CglKnapsackCover kccGenerator;
00030 }
00031
00032
00033 {
00034 CglKnapsackCover rhs;
00035 {
00036 CglKnapsackCover kccGenerator;
00037 CglKnapsackCover cgC(kccGenerator);
00038 rhs=kccGenerator;
00039 }
00040 }
00041
00042
00043
00044 {
00045 CglKnapsackCover kccg;
00046 const int n=7;
00047 double c=50;
00048 double p[n] = {70,20,39,37,7,5,10};
00049 double w[n] = {31, 10, 20, 19, 4, 3, 6};
00050 double z;
00051 int x[n];
00052 int exactsol = kccg.exactSolveKnapsack(n, c, p, w, z, x);
00053 assert(exactsol==1);
00054 assert (z == 107);
00055 assert (x[0]==1);
00056 assert (x[1]==0);
00057 assert (x[2]==0);
00058 assert (x[3]==1);
00059 assert (x[4]==0);
00060 assert (x[5]==0);
00061 assert (x[6]==0);
00062 }
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112 {
00113
00114 OsiSolverInterface * siP = baseSiP->clone();
00115 std::string fn(mpsDir+"tp3");
00116 siP->readMps(fn.c_str(),"mps");
00117
00118
00119 for ( i = 0; i < siP->getNumCols(); i++ )
00120 if ( siP->isInteger(i) )
00121 assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i));
00122 OsiCuts cs;
00123 CoinPackedVector krow;
00124 double b=0;
00125 int nCols=siP->getNumCols();
00126 int * complement=new int [nCols];
00127 double * xstar=new double [nCols];
00128
00129 CglKnapsackCover kccg;
00130
00131
00132
00133 siP->initialSolve();
00134 assert( eq(siP->getObjValue(), 97.185) );
00135 double mycs[] = {.627, .667558333333, .038};
00136 siP->setColSolution(mycs);
00137 const double *colsol = siP->getColSolution();
00138 int k;
00139 for (k=0; k<nCols; k++){
00140 xstar[k]=colsol[k];
00141 complement[k]=0;
00142 }
00143
00144
00145 int rind = ( siP->getRowSense()[0] == 'N' ) ? 1 : 0;
00146 int deriveaknap = kccg.deriveAKnapsack(*siP, cs, krow,b,complement,xstar,rind,siP->getMatrixByRow()->getVector(rind));
00147 assert(deriveaknap ==1);
00148 assert(complement[0]==0);
00149 assert(complement[1]==1);
00150 assert(complement[2]==1);
00151 int inx[3] = {0,1,2};
00152 double el[3] = {161, 120, 68};
00153 CoinPackedVector r;
00154 r.setVector(3,inx,el);
00155 assert (krow == r);
00156 assert (b == 183.0);
00157
00158
00159
00160 CoinPackedVector cover,remainder;
00161 #if 0
00162 int findgreedy = kccg.findGreedyCover( 0, krow, b, xstar, cover, remainder );
00163 assert( findgreedy == 1 );
00164 int coveri = cover.getNumElements();
00165 assert( cover.getNumElements() == 2);
00166 coveri = cover.getIndices()[0];
00167 assert( cover.getIndices()[0] == 0);
00168 assert( cover.getIndices()[1] == 1);
00169 assert( cover.getElements()[0] == 161.0);
00170 assert( cover.getElements()[1] == 120.0);
00171 assert( remainder.getNumElements() == 1);
00172 assert( remainder.getIndices()[0] == 2);
00173 assert( remainder.getElements()[0] == 68.0);
00174
00175
00176 CoinPackedVector cut;
00177 double * rowupper = ekk_rowupper(model);
00178 double cutRhs = cover.getNumElements() - 1.0;
00179 kccg.liftCoverCut(b, krow.getNumElements(),
00180 cover, remainder,
00181 cut);
00182 assert ( cut.getNumElements() == 3 );
00183 assert ( cut.getIndices()[0] == 0 );
00184 assert ( cut.getIndices()[1] == 1 );
00185 assert ( cut.getIndices()[2] == 2 );
00186 assert( cut.getElements()[0] == 1 );
00187 assert( cut.getElements()[1] == 1 );
00188 assert( eq(cut.getElements()[2], 0.087719) );
00189
00190
00191 OsiCuts cuts;
00192 kccg.liftAndUncomplementAndAdd(*siP.getRowUpper()[0],krow,b,complement,0,
00193 cover,remainder,cuts);
00194 int sizerowcuts = cuts.sizeRowCuts();
00195 assert ( sizerowcuts== 1 );
00196 OsiRowCut testRowCut = cuts.rowCut(0);
00197 CoinPackedVector testRowPV = testRowCut.row();
00198 OsiRowCut sampleRowCut;
00199 const int sampleSize = 3;
00200 int sampleCols[sampleSize]={0,1,2};
00201 double sampleElems[sampleSize]={1.0,-1.0,-0.087719};
00202 sampleRowCut.setRow(sampleSize,sampleCols,sampleElems);
00203 sampleRowCut.setLb(-DBL_MAX);
00204 sampleRowCut.setUb(-0.087719);
00205 bool equiv = testRowPV.equivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05) );
00206 assert ( equiv );
00207 #endif
00208
00209
00210 cover.setVector(0,NULL, NULL);
00211 remainder.setVector(0,NULL,NULL);
00212
00213 rind = ( siP->getRowSense()[0] == 'N' ) ? 1 : 0;
00214 int findPJE = kccg.findPseudoJohnAndEllisCover( rind, krow,
00215 b, xstar, cover, remainder );
00216 assert( findPJE == 1 );
00217 assert ( cover.getIndices()[0] == 0 );
00218 assert ( cover.getIndices()[1] == 2 );
00219 assert ( cover.getElements()[0] == 161 );
00220 assert ( cover.getElements()[1] == 68 );
00221 assert ( remainder.getIndices()[0] == 1 );
00222 assert ( remainder.getElements()[0] == 120 );
00223 OsiCuts cuts;
00224 kccg.liftAndUncomplementAndAdd((*siP).getRowUpper()[rind],krow,b, complement, rind,
00225 cover,remainder,cuts);
00226 assert (cuts.sizeRowCuts() == 1 );
00227
00228 OsiRowCut testRowCut = cuts.rowCut(0);
00229 CoinPackedVector testRowPV = testRowCut.row();
00230
00231
00232 const int sampleSize = 3;
00233 int sampleCols[sampleSize]={0,1,2};
00234 double sampleElems[sampleSize]={1.0, -1.0, -1.0};
00235 OsiRowCut sampleRowCut;
00236 sampleRowCut.setRow(sampleSize,sampleCols,sampleElems);
00237 sampleRowCut.setLb(-DBL_MAX);
00238 sampleRowCut.setUb(-1.0);
00239
00240
00241 assert( testRowPV.isEquivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05) ) );
00242
00243 for (i=0; i<nCols; i++){
00244 complement[i]=0;
00245 }
00246
00247 rind++;
00248 deriveaknap = kccg.deriveAKnapsack(*siP,cuts,krow,b,complement,xstar,rind,siP->getMatrixByRow()->getVector(rind));
00249 assert(deriveaknap==0);
00250
00251
00252 for (i=0; i<nCols; i++){
00253 complement[i]=0;
00254 }
00255 deriveaknap = kccg.deriveAKnapsack(*siP,cuts,krow,b,complement,xstar,2,
00256 siP->getMatrixByRow()->getVector(2));
00257 assert(deriveaknap == 0);
00258
00259
00260 delete [] complement;
00261 delete [] xstar;
00262
00263 delete siP;
00264 }
00265
00266 #if 0
00267
00268
00269
00270
00271
00272
00273 {
00274
00275 EKKContext * env=ekk_initializeContext();
00276 EKKModel * model = ekk_newModel(env,"");
00277 OsiSolverInterface si(model);
00278 ekk_importModel(model, "tp4.mps");
00279 CglKnapsackCover kccg;
00280 kccg.ekk_validateIntType(si);
00281
00282
00283
00284 ekk_allSlackBasis(model);
00285 ekk_crash(model,1);
00286 ekk_primalSimplex(model,1);
00287 double lpRelaxBefore=ekk_getRobjvalue(model);
00288 #ifdef CGL_DEBUG
00289 printf("\n\nOrig LP min=%f\n",lpRelaxBefore);
00290 #endif
00291
00292
00293
00294 int nCols=ekk_getInumcols(model);
00295 double * optLpSol = ekk_colsol(model);
00296 int ipOpt = 1;
00297 i=0;
00298 while (i++<nCols && ipOpt){
00299 if(optLpSol[i] < 1.0-1.0e-08 && optLpSol[i]> 1.0e-08) ipOpt = 0;
00300 }
00301
00302 if (ipOpt){
00303 #ifdef CGL_DEBUG
00304 printf("Lp solution is within ip optimality tolerance\n");
00305 #endif
00306 }
00307 else {
00308 OsiSolverInterface iModel(model);
00309 OsiCuts cuts;
00310
00311
00312 kccg.generateCuts(iModel,cuts);
00313 OsiSolverInterface::ApplyCutsReturnCode rc = iModel.applyCuts(cuts);
00314
00315 ekk_mergeBlocks(model,1);
00316 ekk_dualSimplex(model);
00317 double lpRelaxAfter=ekk_getRobjvalue(model);
00318 #ifdef CGL_DEBUG
00319 printf("\n\nFinal LP min=%f\n",lpRelaxAfter);
00320 #endif
00321 assert( lpRelaxBefore < lpRelaxAfter );
00322
00323
00324
00325 assert( cuts.sizeRowCuts() == 1 );
00326 OsiRowCut testRowCut = cuts.rowCut(0);
00327 CoinPackedVector testRowPV = testRowCut.row();
00328
00329 OsiRowCut sampleRowCut;
00330 const int sampleSize = 6;
00331 int sampleCols[sampleSize]={0,1,2,3,4,5};
00332 double sampleElems[sampleSize]={1.0,1.0,1.0,1.0,0.5, 2.0};
00333 sampleRowCut.setRow(sampleSize,sampleCols,sampleElems);
00334 sampleRowCut.setLb(-DBL_MAX);
00335 sampleRowCut.setUb(3.0);
00336 bool equiv = testRowPV.equivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05) );
00337 assert( testRowPV.equivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05) ) );
00338 }
00339
00340
00341 ekk_deleteModel(model);
00342 ekk_endContext(env);
00343
00344 }
00345 #endif
00346
00347
00348
00349
00350
00351
00352
00353
00354 {
00355
00356 OsiSolverInterface * siP = baseSiP->clone();
00357 std::string fn(mpsDir+"tp5");
00358 siP->readMps(fn.c_str(),"mps");
00359
00360
00361 for ( i = 0; i < siP->getNumCols(); i++ )
00362 if ( siP->isInteger(i) )
00363 assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i));
00364 CglKnapsackCover kccg;
00365
00366
00367
00368 siP->initialSolve();
00369 double lpRelaxBefore=siP->getObjValue();
00370 assert( eq(lpRelaxBefore, -51.66666666667) );
00371 double mycs[] = {.8999999999, .899999999999, .89999999999, 1.110223e-16, .5166666666667, 0};
00372 siP->setColSolution(mycs);
00373 #ifdef CGL_DEBUG
00374 printf("\n\nOrig LP min=%f\n",lpRelaxBefore);
00375 #endif
00376
00377
00378 int nCols=siP->getNumCols();
00379 const double * optLpSol = siP->getColSolution();
00380 bool ipOpt = true;
00381 i=0;
00382 while (i++<nCols && ipOpt){
00383 if(optLpSol[i] > kccg.epsilon_ && optLpSol[i] < kccg.onetol_) ipOpt = false;
00384 }
00385
00386 if (ipOpt){
00387 #ifdef CGL_DEBUG
00388 printf("Lp solution is within ip optimality tolerance\n");
00389 #endif
00390 }
00391 else {
00392
00393 OsiCuts cuts;
00394 CoinPackedVector krow;
00395 double b=0.0;
00396 int * complement=new int[nCols];
00397 double * xstar=new double[nCols];
00398
00399 const double *colsol = siP->getColSolution();
00400 for (i=0; i<nCols; i++){
00401 xstar[i]=colsol[i];
00402 complement[i]=0;
00403 }
00404 int row = ( siP->getRowSense()[0] == 'N' ) ? 1 : 0;
00405
00406 if (kccg.deriveAKnapsack(*siP, cuts, krow, b, complement, xstar, row,siP->getMatrixByRow()->getVector(row))){
00407 CoinPackedVector cover, remainder;
00408
00409 if (kccg.findGreedyCover(row, krow, b, xstar, cover, remainder) == 1){
00410
00411 kccg.liftAndUncomplementAndAdd((*siP).getRowUpper()[row],krow, b, complement, row, cover, remainder, cuts);
00412 }
00413
00414 const double * rowupper = siP->getRowUpper();
00415 int k;
00416 if (fabs(b-rowupper[row]) > 1.0e-05) {
00417 for(k=0; k<krow.getNumElements(); k++) {
00418 if (complement[krow.getIndices()[k]]){
00419 xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]];
00420 complement[krow.getIndices()[k]]=0;
00421 }
00422 }
00423 }
00424
00425 delete [] complement;
00426 delete [] xstar;
00427 }
00428
00429 OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts);
00430
00431 siP->resolve();
00432 double lpRelaxAfter=siP->getObjValue();
00433 assert( eq(lpRelaxAfter, -30.0) );
00434 #ifdef CGL_DEBUG
00435 printf("\n\nFinal LP min=%f\n",lpRelaxAfter);
00436 #endif
00437
00438 assert( lpRelaxBefore < lpRelaxAfter );
00439 assert( cuts.sizeRowCuts() == 1 );
00440 OsiRowCut testRowCut = cuts.rowCut(0);
00441 CoinPackedVector testRowPV = testRowCut.row();
00442 OsiRowCut sampleRowCut;
00443 const int sampleSize = 6;
00444 int sampleCols[sampleSize]={0,1,2,3,4,5};
00445 double sampleElems[sampleSize]={1.0,1.0,1.0,0.25,1.0,2.0};
00446 sampleRowCut.setRow(sampleSize,sampleCols,sampleElems);
00447 sampleRowCut.setLb(-DBL_MAX);
00448 sampleRowCut.setUb(3.0);
00449 assert(testRowPV.isEquivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05)));
00450 }
00451
00452 delete siP;
00453 }
00454
00455
00456
00457
00458
00459 {
00460
00461 OsiSolverInterface * siP = baseSiP->clone();
00462 std::string fn(mpsDir+"p0033");
00463 siP->readMps(fn.c_str(),"mps");
00464
00465
00466 for ( i = 0; i < siP->getNumCols(); i++ )
00467 if ( siP->isInteger(i) )
00468 assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i));
00469 int nCols=siP->getNumCols();
00470 CglKnapsackCover kccg;
00471
00472
00473
00474 siP->initialSolve();
00475 double lpRelaxBefore=siP->getObjValue();
00476 assert( eq(lpRelaxBefore, 2520.5717391304347) );
00477 double mycs[] = {0, 1, 0, 0, -2.0837010502455788e-19, 1, 0, 0, 1,
00478 0.021739130434782594, 0.35652173913043478,
00479 -6.7220534694101275e-18, 5.3125906451789717e-18,
00480 1, 0, 1.9298798670241979e-17, 0, 0, 0,
00481 7.8875708048320448e-18, 0.5, 0,
00482 0.85999999999999999, 1, 1, 0.57999999999999996,
00483 1, 0, 1, 0, 0.25, 0, 0.67500000000000004};
00484 siP->setColSolution(mycs);
00485 #ifdef CGL_DEBUG
00486 printf("\n\nOrig LP min=%f\n",lpRelaxBefore);
00487 #endif
00488
00489 OsiCuts cuts;
00490
00491
00492 kccg.generateCuts(*siP,cuts);
00493 OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts);
00494
00495 siP->resolve();
00496 double lpRelaxAfter=siP->getObjValue();
00497 assert( eq(lpRelaxAfter, 2829.0597826086955) );
00498 #ifdef CGL_DEBUG
00499 printf("\n\nOrig LP min=%f\n",lpRelaxBefore);
00500 printf("\n\nFinal LP min=%f\n",lpRelaxAfter);
00501 #endif
00502 assert( lpRelaxBefore < lpRelaxAfter );
00503
00504
00505
00506 int objIndices[14] = {
00507 0, 6, 7, 9, 13, 17, 18,
00508 22, 24, 25, 26, 27, 28, 29 };
00509 CoinPackedVector p0033(14,objIndices,1.0);
00510
00511
00512 const double * objective=siP->getObjCoefficients();
00513 double ofv =0 ;
00514 int r;
00515 for (r=0; r<nCols; r++){
00516 ofv=ofv + p0033[r]*objective[r];
00517 }
00518 CoinRelFltEq eq;
00519 assert( eq(ofv,3089.0) );
00520
00521 int nRowCuts = cuts.sizeRowCuts();
00522 OsiRowCut rcut;
00523 CoinPackedVector rpv;
00524 for (i=0; i<nRowCuts; i++){
00525 rcut = cuts.rowCut(i);
00526 rpv = rcut.row();
00527 double p0033Sum = (rpv*p0033).sum();
00528 assert (p0033Sum <= rcut.ub() );
00529 }
00530
00531 delete siP;
00532 }
00533
00534
00535 {
00536 FILE * fp = fopen("knapsack.debug","r");
00537 if (fp) {
00538 int ncol,nel;
00539 double up;
00540 fscanf(fp,"%d %d %lg",&ncol,&nel,&up);
00541 printf("%d columns, %d elements, upper %g\n",ncol,nel,up);
00542 double * sol1 = new double[nel];
00543 double * el1 = new double[nel];
00544 int * col1 = new int[nel];
00545 int * start = new int[ncol+1];
00546 memset(start,0,ncol*sizeof(int));
00547 int * row = new int[nel];
00548 int i;
00549 for (i=0;i<nel;i++) {
00550 fscanf(fp,"%d %lg %lg",col1+i,el1+i,sol1+i);
00551 printf("[%d, e=%g, v=%g] ",col1[i],el1[i],sol1[i]);
00552 start[col1[i]]=1;
00553 row[i]=0;
00554 }
00555 printf("\n");
00556
00557 OsiSolverInterface * siP = baseSiP->clone();
00558
00559 double lo=-1.0e30;
00560 double * upper = new double[ncol];
00561 start[ncol]=nel;
00562 int last=0;
00563 for (i=0;i<ncol;i++) {
00564 upper[i]=1.0;
00565 int marked=start[i];
00566 start[i]=last;
00567 if (marked)
00568 last++;
00569 }
00570 siP->loadProblem(ncol,1,start,row,el1,NULL,upper,NULL,&lo,&up);
00571
00572 memset(upper,0,ncol*sizeof(double));
00573 for (i=0;i<nel;i++) {
00574 int icol=col1[i];
00575 upper[icol]=sol1[i];
00576 siP->setInteger(icol);
00577 }
00578 siP->setColSolution(upper);
00579 delete [] sol1;
00580 delete [] el1;
00581 delete [] col1;
00582 delete [] start;
00583 delete [] row;
00584 delete [] upper;
00585 CglKnapsackCover kccg;
00586
00587 OsiCuts cuts;
00588
00589
00590 kccg.generateCuts(*siP,cuts);
00591
00592 int numberCuts = cuts.sizeRowCuts();
00593 if (numberCuts) {
00594 for (i=0;i<numberCuts;i++) {
00595 OsiRowCut * thisCut = cuts.rowCutPtr(i);
00596 int n=thisCut->row().getNumElements();
00597 printf("Cut %d has %d entries, rhs %g %g =>",i,n,thisCut->lb(),
00598 thisCut->ub());
00599 int j;
00600 const int * index = thisCut->row().getIndices();
00601 const double * element = thisCut->row().getElements();
00602 for (j=0;j<n;j++) {
00603 printf(" (%d,%g)",index[j],element[j]);
00604 }
00605 printf("\n");
00606 }
00607 }
00608 fclose(fp);
00609 }
00610 }
00611
00612
00613
00614
00615 {
00616
00617 OsiSolverInterface * siP = baseSiP->clone();
00618 std::string fn(mpsDir+"p0201");
00619 siP->readMps(fn.c_str(),"mps");
00620
00621
00622 for ( i = 0; i < siP->getNumCols(); i++ )
00623 if ( siP->isInteger(i) )
00624 assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i));
00625
00626 const int nCols=siP->getNumCols();
00627 CglKnapsackCover kccg;
00628
00629
00630
00631 siP->initialSolve();
00632 double lpRelaxBefore=siP->getObjValue();
00633 assert( eq(lpRelaxBefore, 6875.) );
00634 double mycs[] =
00635 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00636 0, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5,
00637 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0,
00638 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5,
00639 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0,
00640 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0,
00641 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0,
00642 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0,
00643 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00644 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00645 1};
00646 siP->setColSolution(mycs);
00647 #ifdef CGL_DEBUG
00648 printf("\n\nOrig LP min=%f\n",lpRelaxBefore);
00649 #endif
00650
00651 OsiCuts cuts;
00652
00653
00654 kccg.generateCuts(*siP,cuts);
00655 OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts);
00656
00657 siP->resolve();
00658 double lpRelaxAfter=siP->getObjValue();
00659 assert( eq(lpRelaxAfter, 7125) );
00660 #ifdef CGL_DEBUG
00661 printf("\n\nOrig LP min=%f\n",lpRelaxBefore);
00662 printf("\n\nFinal LP min=%f\n",lpRelaxAfter);
00663 #endif
00664 assert( lpRelaxBefore < lpRelaxAfter );
00665
00666
00667 int objIndices[22] = { 8, 10, 21, 38, 39, 56,
00668 60, 74, 79, 92, 94, 110, 111, 128, 132, 146,
00669 151,164, 166, 182,183, 200 };
00670 CoinPackedVector p0201(22,objIndices,1.0);
00671
00672
00673 const double * objective=siP->getObjCoefficients();
00674 double ofv =0 ;
00675 int r;
00676 for (r=0; r<nCols; r++){
00677 ofv=ofv + p0201[r]*objective[r];
00678 }
00679 CoinRelFltEq eq;
00680 assert( eq(ofv,7615.0) );
00681
00682
00683 int nRowCuts = cuts.sizeRowCuts();
00684 OsiRowCut rcut;
00685 CoinPackedVector rpv;
00686 for (i=0; i<nRowCuts; i++){
00687 rcut = cuts.rowCut(i);
00688 rpv = rcut.row();
00689 double p0201Sum = (rpv*p0201).sum();
00690 assert (p0201Sum <= rcut.ub() );
00691 }
00692
00693 delete siP;
00694 }
00695
00696
00697
00698 {
00699 OsiSolverInterface * siP=baseSiP->clone();
00700 std::string fn(mpsDir+"nw460");
00701 siP->readMps(fn.c_str(),"mps");
00702
00703
00704 for ( i = 0; i < siP->getNumCols(); i++ )
00705 if ( siP->isInteger(i) )
00706 assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i));
00707 CglKnapsackCover kccg;
00708
00709
00710
00711 siP->initialSolve();
00712 double lpRelaxBefore=siP->getObjValue();
00713 assert( eq(lpRelaxBefore, -225.68951787852194) );
00714 double mycs[] = {0.7099213482046447, 0, 0.34185802225477174, 1, 1, 0, 1, 1, 0};
00715 siP->setColSolution(mycs);
00716
00717 OsiCuts cuts;
00718
00719
00720 kccg.generateCuts(*siP,cuts);
00721 OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts);
00722
00723 siP->resolve();
00724 double lpRelaxAfter=siP->getObjValue();
00725 assert( eq(lpRelaxAfter, -176) );
00726 #ifdef CGL_DEBUG
00727 printf("\n\nOrig LP min=%f\n",lpRelaxBefore);
00728 printf("\n\nFinal LP min=%f\n",lpRelaxAfter);
00729 #endif
00730 #ifdef MJS
00731 assert( lpRelaxBefore < lpRelaxAfter );
00732 #endif
00733
00734 int nRowCuts = cuts.sizeRowCuts();
00735 OsiRowCut rcut;
00736 CoinPackedVector rpv;
00737 for (i=0; i<nRowCuts; i++){
00738 rcut = cuts.rowCut(i);
00739 rpv = rcut.row();
00740 int j;
00741 printf("Row cut number %i has rhs = %g\n",i,rcut.ub());
00742 for (j=0; j<rpv.getNumElements(); j++){
00743 printf("index %i, element %g\n", rpv.getIndices()[j], rpv.getElements()[j]);
00744 }
00745 printf("\n");
00746 }
00747 delete siP;
00748 }
00749
00750
00751 {
00752
00753 OsiSolverInterface * siP = baseSiP->clone();
00754 std::string fn(mpsDir+"exmip1");
00755 siP->readMps(fn.c_str(),"mps");
00756
00757
00758 for ( i = 0; i < siP->getNumCols(); i++ )
00759 if ( siP->isInteger(i) )
00760 assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i));
00761 CglKnapsackCover kccg;
00762
00763
00764
00765 siP->initialSolve();
00766 double lpRelaxBefore=siP->getObjValue();
00767 assert( eq(lpRelaxBefore, 3.2368421052631575) );
00768 double mycs[] = {2.5, 0, 0, 0.6428571428571429, 0.5, 4, 0, 0.26315789473684253};
00769 siP->setColSolution(mycs);
00770
00771 OsiCuts cuts;
00772 kccg.generateCuts(*siP,cuts);
00773 OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts);
00774
00775 siP->resolve();
00776 double lpRelaxAfter=siP->getObjValue();
00777 assert( eq(lpRelaxAfter, 3.2368421052631575) );
00778 #ifdef CGL_DEBUG
00779 printf("\n\nOrig LP min=%f\n",lpRelaxBefore);
00780 printf("\n\nFinal LP min=%f\n",lpRelaxAfter);
00781 #endif
00782 assert( lpRelaxBefore <= lpRelaxAfter );
00783
00784 delete siP;
00785 }
00786
00787 #ifdef CGL_DEBUG
00788
00789 {
00790 int nCols = 2;
00791 int row = 1;
00792 CoinPackedVector krow;
00793 double e[2] = {5,10};
00794 int ii[2] = {0,1};
00795 krow.setVector(nCols,ii,e);
00796 double b=11;
00797 double xstar[2] = {.2,.9};
00798 CoinPackedVector cover;
00799 CoinPackedVector remainder;
00800 CglKnapsackCover kccg;
00801 kccg.findLPMostViolatedMinCover(nCols, row, krow, b, xstar, cover, remainder);
00802 printf("num in cover = %i\n",cover.getNumElements());
00803 int j;
00804 for (j=0; j<cover.getNumElements(); j++){
00805 printf(" index %i element % g\n", cover.getIndices()[j], cover.getElements()[j]);
00806 }
00807 }
00808 #endif
00809
00810 #ifdef CGL_DEBUG
00811
00812 {
00813 int nCols = 5;
00814 int row = 1;
00815 CoinPackedVector krow;
00816 double e[5] = {1,1,1,1,10};
00817 int ii[5] = {0,1,2,3,4};
00818 krow.setVector(nCols,ii,e);
00819 double b=11;
00820 double xstar[5] = {.9,.9,1,1,.1};
00821 CoinPackedVector cover;
00822 CoinPackedVector remainder;
00823 CglKnapsackCover kccg;
00824 kccg.findLPMostViolatedMinCover(nCols, row, krow, b, xstar, cover, remainder);
00825 printf("num in cover = %i\n",cover.getNumElements());
00826 int j;
00827 for (j=0; j<cover.getNumElements(); j++){
00828 printf(" index %i element % g\n", cover.getIndices()[j], cover.getElements()[j]);
00829 }
00830 }
00831 #endif
00832
00833 }
00834