#include <CglOddHole.hpp>
Inheritance diagram for CglOddHole:
Public Member Functions | |
Generate Cuts | |
virtual void | generateCuts (const OsiSolverInterface &si, OsiCuts &cs) const |
Create Row List | |
void | createRowList (const OsiSolverInterface &si, const int *possible=NULL) |
void | createRowList (int numberRows, const int *whichRow) |
This version passes in a list - 1 marks possible. | |
Create Clique List | |
void | createCliqueList (int numberCliques, const int *cliqueStart, const int *cliqueMember) |
Number Possibilities | |
int | numberPossible () |
Returns how many rows might give odd hole cuts. | |
Gets and Sets | |
double | getMinimumViolation () const |
Minimum violation. | |
void | setMinimumViolation (double value) |
double | getMinimumViolationPer () const |
Minimum violation per entry. | |
void | setMinimumViolationPer (double value) |
int | getMaximumEntries () const |
Maximum number of entries in a cut. | |
void | setMaximumEntries (int value) |
Constructors and destructors | |
CglOddHole () | |
Default constructor. | |
CglOddHole (const CglOddHole &) | |
Copy constructor. | |
CglOddHole & | operator= (const CglOddHole &rhs) |
Assignment operator. | |
virtual | ~CglOddHole () |
Destructor. | |
virtual void | refreshSolver (OsiSolverInterface *solver) |
This can be used to refresh any inforamtion. | |
Private Member Functions | |
Private methods | |
void | generateCuts (const OsiRowCutDebugger *debugger, const CoinPackedMatrix &rowCopy, const double *solution, const double *dj, OsiCuts &cs, const int *suitableRow, const int *fixedColumn, bool packed) |
Private Attributes | |
Private member data | |
int * | suitableRows_ |
list of suitableRows | |
int * | startClique_ |
start of each clique | |
int * | member_ |
clique members | |
double | epsilon_ |
epsilon | |
double | onetol_ |
1-epsilon | |
double | minimumViolation_ |
Minimum violation. | |
double | minimumViolationPer_ |
Minimum violation per entry. | |
int | maximumEntries_ |
Maximum number of entries in a cut. | |
int | numberRows_ |
number of rows when suitability tested | |
int | numberCliques_ |
number of cliques | |
Friends | |
void | CglOddHoleUnitTest (const OsiSolverInterface *siP, const std::string mpdDir) |
Definition at line 11 of file CglOddHole.hpp.
|
Create a list of extra row cliques which may not be in matrix At present these are classical cliques Definition at line 661 of file CglOddHole.cpp. References member_, numberCliques_, and startClique_.
00663 { 00664 numberCliques_=numberCliques; 00665 startClique_=new int[numberCliques_+1]; 00666 memcpy(startClique_,cliqueStart,(numberCliques_+1)*sizeof(int)); 00667 int length=startClique_[numberCliques_]; 00668 member_=new int[length]; 00669 memcpy(member_,cliqueMember,length*sizeof(int)); 00670 } |
|
Create a list of rows which might yield cuts this is to speed up process The possible parameter is a list to cut down search Definition at line 585 of file CglOddHole.cpp. References epsilon_, numberRows_, and suitableRows_. Referenced by generateCuts().
00587 { 00588 // Get basic problem information 00589 int nRows=si.getNumRows(); 00590 00591 const CoinPackedMatrix * rowCopy = si.getMatrixByRow(); 00592 00593 const int * column = rowCopy->getIndices(); 00594 const int * rowStart = rowCopy->getVectorStarts(); 00595 const int * rowLength = rowCopy->getVectorLengths(); 00596 00597 int rowIndex; 00598 delete [] suitableRows_; 00599 numberRows_=nRows; 00600 00601 const double * rowElements = rowCopy->getElements(); 00602 const double * rowupper = si.getRowUpper(); 00603 const double * rowlower = si.getRowLower(); 00604 const double * collower = si.getColLower(); 00605 const double * colupper = si.getColUpper(); 00606 00607 suitableRows_=new int[nRows]; 00608 if (possible) { 00609 memcpy(suitableRows_,possible,nRows*sizeof(int)); 00610 } else { 00611 int i; 00612 for (i=0;i<nRows;i++) { 00613 suitableRows_[i]=1; 00614 } 00615 } 00616 for (rowIndex=0; rowIndex<nRows; rowIndex++){ 00617 double rhs1=rowupper[rowIndex]; 00618 double rhs2=rowlower[rowIndex]; 00619 if (suitableRows_[rowIndex]) { 00620 int i; 00621 bool goodRow=true; 00622 for (i=rowStart[rowIndex]; 00623 i<rowStart[rowIndex]+rowLength[rowIndex];i++) { 00624 int thisCol=column[i]; 00625 if (colupper[thisCol]-collower[thisCol]>epsilon_) { 00626 // could allow general integer variables but unlikely 00627 if (!si.isBinary(thisCol) ) { 00628 goodRow=false; 00629 break; 00630 } 00631 if (fabs(rowElements[i]-1.0)>epsilon_) { 00632 goodRow=false; 00633 break; 00634 } 00635 } else { 00636 rhs1 -= collower[thisCol]*rowElements[i]; 00637 rhs2 -= collower[thisCol]*rowElements[i]; 00638 } 00639 } 00640 if (fabs(rhs1-1.0)>epsilon_&&fabs(rhs2-1.0)>epsilon_) { 00641 goodRow=false; 00642 } 00643 if (goodRow) { 00644 suitableRows_[rowIndex]=1; 00645 } else { 00646 suitableRows_[rowIndex]=0; 00647 } 00648 } 00649 } 00650 } |
|
Generate cuts from matrix copy and solution If packed true then <=1 rows, otherwise >=1 rows. Definition at line 147 of file CglOddHole.cpp. References CoinPackedVectorBase::dotProduct(), maximumEntries_, minimumViolation_, minimumViolationPer_, and CoinPackedVector::sortIncrIndex().
00154 { 00155 CoinPackedMatrix columnCopy = rowCopy; 00156 columnCopy.reverseOrdering(); 00157 00158 // Get basic problem information 00159 int nRows=columnCopy.getNumRows(); 00160 int nCols=columnCopy.getNumCols(); 00161 00162 const int * column = rowCopy.getIndices(); 00163 const int * rowStart = rowCopy.getVectorStarts(); 00164 const int * rowLength = rowCopy.getVectorLengths(); 00165 00166 const int * row = columnCopy.getIndices(); 00167 const int * columnStart = columnCopy.getVectorStarts(); 00168 const int * columnLength = columnCopy.getVectorLengths(); 00169 00170 // we need only look at suitable rows and variables with unsatisfied 0-1 00171 // lookup from true row to compressed matrix 00172 int * mrow = new int[nRows]; 00173 // lookup from true column to compressed 00174 int * lookup = new int[nCols]; 00175 // number of columns in compressed matrix 00176 int nSmall=0; 00177 int i; 00178 //do lookup from true sequence to compressed 00179 int n=0; 00180 for (i=0;i<nRows;i++) { 00181 if (suitableRow[i]>0) { 00182 mrow[i]=n++; 00183 } else { 00184 mrow[i]=-1; 00185 } 00186 } 00187 for (i=0;i<nCols;i++) { 00188 if (!fixedColumn[i]) { 00189 lookup[i]=nSmall++; 00190 } else { 00191 lookup[i]=-1; 00192 } 00193 } 00194 int nSmall2=2*nSmall; 00195 // we don't know how big matrix will be 00196 #define MAXELS 50000 00197 int maxels=MAXELS; 00198 //How do I do reallocs in C++? 00199 // 1.0 - value x(i) - value x(j) for each node pair (or reverse if cover) 00200 double * cost = (double *) malloc(maxels*sizeof(double)); 00201 // arc i.e. j which can be reached from i 00202 int * to= (int *) malloc(maxels*sizeof(int)); 00203 //original row for each arc 00204 int * rowfound=(int *) malloc(maxels*sizeof(int)); 00205 // start of each column 00206 int * starts=new int[2*nSmall+1]; 00207 starts[0]=0; 00208 // useful array for marking if already connected 00209 int * mark =new int[nSmall2]; 00210 memset(mark,0,nSmall2*sizeof(int)); 00211 n=0; //number of elements in matrix 00212 for (i=0;i<nCols;i++) { 00213 int icol=lookup[i]; 00214 if (icol>=0) { 00215 // column in compressed matrix 00216 int k; 00217 double dd=1.0000001-solution[i]; 00218 mark[icol]=1; 00219 // reallocate if matrix reached size limit 00220 if (n+nCols>maxels) { 00221 maxels*=2; 00222 cost=(double *) realloc(cost,maxels*sizeof(int)); 00223 to=(int *) realloc(to,maxels*sizeof(int)); 00224 rowfound=(int *) realloc(rowfound,maxels*sizeof(int)); 00225 } 00226 // get all other connected variables 00227 for (k=columnStart[i];k<columnStart[i]+columnLength[i];k++) { 00228 int irow=row[k]; 00229 int jrow=mrow[irow]; 00230 // but only if row in compressed matrix 00231 if (jrow>=0) { 00232 int j; 00233 for (j=rowStart[irow];j<rowStart[irow]+rowLength[irow];j++) { 00234 int jcol=column[j]; 00235 int kcol=lookup[jcol]; 00236 if (kcol>=0&&!mark[kcol]) { 00237 cost[n]=dd-solution[jcol]; 00238 to[n]=kcol; 00239 rowfound[n++]=irow;//original row 00240 mark[kcol]=1; 00241 } 00242 } 00243 } 00244 } 00245 starts[icol+1]=n; 00246 // zero out markers for next column 00247 mark[icol]=0; 00248 for (k=starts[icol];k<starts[icol+1];k++) { 00249 int ito=to[k]; 00250 if (ito<0||ito>=nSmall) abort(); 00251 mark[to[k]]=0; 00252 } 00253 } 00254 } 00255 //if cover then change sign - otherwise make sure positive 00256 if (packed) { 00257 for (i=0;i<n;i++) { 00258 if (cost[i]<1.0e-10) { 00259 cost[i]=1.0e-10; 00260 } 00261 } 00262 } else { 00263 for (i=0;i<n;i++) { 00264 cost[i]=-cost[i]; 00265 if (cost[i]<1.0e-10) { 00266 cost[i]=1.0e-10; 00267 } 00268 } 00269 } 00270 // we are going to double size 00271 00272 if (2*n>maxels) { 00273 maxels=2*n; 00274 cost=(double *) realloc(cost,maxels*sizeof(int)); 00275 to=(int *) realloc(to,maxels*sizeof(int)); 00276 rowfound=(int *) realloc(rowfound,maxels*sizeof(int)); 00277 } 00278 /* copy and make bipartite*/ 00279 00280 for (i=0;i<nSmall;i++) { 00281 int k,j=i+nSmall; 00282 for (k=starts[i];k<starts[i+1];k++) { 00283 int ito=to[k]; 00284 to[n]=ito; 00285 to[k]=ito+nSmall; 00286 cost[n]=cost[k]; 00287 rowfound[n++]=rowfound[k];; 00288 } 00289 starts[j+1]=n; 00290 } 00291 //random numbers to winnow out duplicate cuts 00292 double * check = new double[nCols]; 00293 CoinSeedRandom(13579); 00294 for (i=0;i<nCols;i++) { 00295 check[i]=CoinDrand48(); 00296 } 00297 00298 // Shortest path algorithm from Dijkstra - is there a better one? 00299 00300 typedef struct { 00301 double cost; //cost to starting node 00302 int back; //previous node 00303 } Path; 00304 typedef struct { 00305 double cost; //cost to starting node 00306 int node; //node 00307 } Item; 00308 Item * stack = new Item [nSmall2]; 00309 Path * path = new Path [nSmall2]; 00310 // arrays below are used only if looks promising 00311 // allocate here 00312 // we don't know how many cuts will be generated 00313 int ncuts=0; 00314 int maxcuts=1000; 00315 double * hash = (double *) malloc(maxcuts*sizeof(double)); 00316 // to clean (should not be needed) 00317 int * clean = new int[nSmall2]; 00318 int * candidate = new int[CoinMax(nSmall2,nCols)]; 00319 double * element = new double[nCols]; 00320 // in case we want to sort 00321 double_double_int_triple * sortit = 00322 new double_double_int_triple [nCols]; 00323 memset(mark,0,nSmall2*sizeof(int)); 00324 int * countcol = new int[nCols]; 00325 memset(countcol,0,nCols*sizeof(int)); 00326 int bias = packed ? 0 : 1; //amount to add before halving 00327 // If nSmall large then should do a randomized subset 00328 // Improvement 1 00329 int icol; 00330 for (icol=0;icol<nSmall;icol++) { 00331 int j; 00332 int jcol=icol+nSmall; 00333 int istack=1; 00334 for (j=0;j<nSmall2;j++) { 00335 path[j].cost=1.0e70; 00336 path[j].back=nSmall2+1; 00337 } 00338 path[icol].cost=0.0; 00339 path[icol].back=-1; 00340 stack[0].cost=0.0; 00341 stack[0].node=icol; 00342 mark[icol]=1; 00343 while(istack) { 00344 Item thisItem=stack[--istack]; 00345 double thisCost=thisItem.cost; 00346 int inode=thisItem.node; 00347 int k; 00348 mark[inode]=0; //say available for further work 00349 // See if sorting every so many would help (and which way)? 00350 // Improvement 2 00351 for (k=starts[inode];k<starts[inode+1];k++) { 00352 int jnode=to[k]; 00353 if (!mark[jnode]&&thisCost+cost[k]<path[jnode].cost-1.0e-12) { 00354 path[jnode].cost=thisCost+cost[k]; 00355 path[jnode].back=inode; 00356 // add to stack 00357 stack[istack].cost=path[jnode].cost; 00358 stack[istack++].node=jnode; 00359 mark[jnode]=1; 00360 #ifdef CGL_DEBUG 00361 assert (istack<=nSmall2); 00362 #endif 00363 } 00364 } 00365 } 00366 bool good=(path[jcol].cost<0.9999); 00367 00368 if (good) { /* try */ 00369 int ii; 00370 int nrow2=0; 00371 int nclean=0; 00372 double sum=0; 00373 #ifdef CGL_DEBUG 00374 printf("** %d ",jcol-nSmall); 00375 #endif 00376 ii=1; 00377 candidate[0]=jcol; 00378 while(jcol!=icol) { 00379 int jjcol; 00380 jcol=path[jcol].back; 00381 if (jcol>=nSmall) { 00382 jjcol=jcol-nSmall; 00383 } else { 00384 jjcol=jcol; 00385 } 00386 #ifdef CGL_DEBUG 00387 printf(" %d",jjcol); 00388 #endif 00389 if (mark[jjcol]) { 00390 // good=false; 00391 // probably means this is from another cycle (will have been found) 00392 // one of cycles must be zero cost 00393 // printf("variable already on chain!\n"); 00394 } else { 00395 mark[jjcol]=1; 00396 clean[nclean++]=jjcol; 00397 candidate[ii++]=jcol; 00398 #ifdef CGL_DEBUG 00399 assert (ii<=nSmall2); 00400 #endif 00401 } 00402 } 00403 #ifdef CGL_DEBUG 00404 printf("\n"); 00405 #endif 00406 for (j=0;j<nclean;j++) { 00407 int k=clean[j]; 00408 mark[k]=0; 00409 } 00410 if (good) { 00411 int k; 00412 for (k=ii-1;k>0;k--) { 00413 int jk,kk=candidate[k]; 00414 int ix=0; 00415 for (jk=starts[kk];jk<starts[kk+1];jk++) { 00416 int ito=to[jk]; 00417 if (ito==candidate[k-1]) { 00418 ix=1; 00419 // back to original row 00420 mrow[nrow2++]=rowfound[jk]; 00421 break; 00422 } 00423 } 00424 if (!ix) { 00425 good=false; 00426 } 00427 } 00428 if ((nrow2&1)!=1) { 00429 good=false; 00430 } 00431 if (good) { 00432 int nincut=0; 00433 for (k=0;k<nrow2;k++) { 00434 int j,irow=mrow[k]; 00435 for (j=rowStart[irow];j<rowStart[irow]+rowLength[irow];j++) { 00436 int icol=column[j]; 00437 if (!countcol[icol]) candidate[nincut++]=icol; 00438 countcol[icol]++; 00439 } 00440 } 00441 #ifdef CGL_DEBUG 00442 printf("true constraint %d",nrow2); 00443 #endif 00444 nrow2=nrow2>>1; 00445 double rhs=nrow2; 00446 if (!packed) rhs++; // +1 for cover 00447 ii=0; 00448 for (k=0;k<nincut;k++) { 00449 int jcol=candidate[k]; 00450 if (countcol[jcol]) { 00451 #ifdef CGL_DEBUG 00452 printf(" %d %d",jcol,countcol[jcol]); 00453 #endif 00454 int ihalf=(countcol[jcol]+bias)>>1; 00455 if (ihalf) { 00456 element[ii]=ihalf; 00457 sum+=solution[jcol]*element[ii]; 00458 /*printf("%d %g %g\n",jcol,element[ii],sumall[jcol]);*/ 00459 candidate[ii++]=jcol; 00460 } 00461 countcol[jcol]=0; 00462 } 00463 } 00464 #ifdef CGL_DEBUG 00465 printf("\n"); 00466 #endif 00467 OsiRowCut rc; 00468 double violation=0.0; 00469 if (packed) { 00470 violation = sum-rhs; 00471 rc.setLb(-DBL_MAX); 00472 rc.setUb(rhs); 00473 } else { 00474 // other way for cover 00475 violation = rhs-sum; 00476 rc.setUb(DBL_MAX); 00477 rc.setLb(rhs); 00478 } 00479 if (violation<minimumViolation_) { 00480 #ifdef CGL_DEBUG 00481 printf("why no cut\n"); 00482 #endif 00483 good=false; 00484 } else { 00485 if (((double) ii) * minimumViolationPer_>violation|| 00486 ii>maximumEntries_) { 00487 #ifdef CGL_DEBUG 00488 printf("why no cut\n"); 00489 #endif 00490 if (packed) { 00491 // sort and see if we can get down to length 00492 // relax by taking out ones with solution 0.0 00493 nincut=ii; 00494 for (k=0;k<nincut;k++) { 00495 int jcol=candidate[k]; 00496 double value = fabs(dj[jcol]); 00497 if (solution[jcol]) 00498 value = -solution[jcol]; 00499 sortit[k].dj=value; 00500 sortit[k].element=element[k]; 00501 sortit[k].sequence=jcol; 00502 } 00503 // sort 00504 std::sort(sortit,sortit+nincut,double_double_int_triple_compare()); 00505 nincut = min(nincut,maximumEntries_); 00506 sum=0.0; 00507 for (k=0;k<nincut;k++) { 00508 int jcol=sortit[k].sequence; 00509 candidate[k]=jcol; 00510 element[k]=sortit[k].element; 00511 sum+=solution[jcol]*element[k]; 00512 } 00513 violation = sum-rhs; 00514 ii=nincut; 00515 if (violation<minimumViolation_) { 00516 good=false; 00517 } 00518 } else { 00519 good=false; 00520 } 00521 } 00522 } 00523 if (good) { 00524 //this assumes not many cuts 00525 int j; 00526 #if 0 00527 double value=0.0; 00528 for (j=0;j<ii;j++) { 00529 int icol=candidate[j]; 00530 value += check[icol]*element[j]; 00531 } 00532 #else 00533 CoinPackedVector candidatePv(ii,candidate,element); 00534 candidatePv.sortIncrIndex(); 00535 double value = candidatePv.dotProduct(check); 00536 #endif 00537 00538 for (j=0;j<ncuts;j++) { 00539 if (value==hash[j]) { 00540 //could check equality - quicker just to assume 00541 break; 00542 } 00543 } 00544 if (j==ncuts) { 00545 //new 00546 if (ncuts==maxcuts) { 00547 maxcuts *= 2; 00548 hash = (double *) realloc(hash,maxcuts*sizeof(double)); 00549 } 00550 hash[ncuts++]=value; 00551 rc.setRow(ii,candidate,element); 00552 #ifdef CGL_DEBUG 00553 printf("sum %g rhs %g %d\n",sum,rhs,ii); 00554 if (debugger) 00555 assert(!debugger->invalidCut(rc)); 00556 #endif 00557 cs.insert(rc); 00558 } 00559 } 00560 } 00561 /* end of adding cut */ 00562 } 00563 } 00564 } 00565 delete [] countcol; 00566 delete [] element; 00567 delete [] candidate; 00568 delete [] sortit; 00569 delete [] clean; 00570 delete [] path; 00571 delete [] stack; 00572 free(hash); 00573 delete [] check; 00574 delete [] mark; 00575 delete [] starts; 00576 delete [] lookup; 00577 delete [] mrow; 00578 free(rowfound); 00579 free(to); 00580 free(cost); 00581 } |
|
Generate odd hole cuts for the model of the solver interface, si. This looks at all rows of type sum x(i) <= 1 (or == 1) (x 0-1) and sees if there is an odd cycle cut. See Grotschel, Lovasz and Schrijver (1988) for method. This is then lifted by using the corresponding Chvatal cut i.e. Take all rows in cycle and add them together. RHS will be odd so weaken all odd coefficients so 1.0 goes to 0.0 etc - then constraint is sum even(j)*x(j) <= odd which can be replaced by sum (even(j)/2)*x(j) <= (odd-1.0)/2. A similar cut can be generated for sum x(i) >= 1. Insert the generated cuts into OsiCut, cs. This is only done for rows with unsatisfied 0-1 variables. If there are many of these it will be slow. Improvements would do a randomized subset and also speed up shortest path algorithm used. Implements CglCutGenerator. Definition at line 32 of file CglOddHole.cpp. References createRowList(), epsilon_, numberRows_, onetol_, and suitableRows_.
00034 { 00035 // Get basic problem information 00036 int nRows=si.getNumRows(); 00037 int nCols=si.getNumCols(); 00038 00039 const CoinPackedMatrix * rowCopy = si.getMatrixByRow(); 00040 00041 // Could do cliques and extra OSL cliques 00042 // For moment just easy ones 00043 00044 // If no information exists then get a list of suitable rows 00045 // If it does then suitable rows are subset of information 00046 00047 CglOddHole temp; 00048 int * checkRow = new int[nRows]; 00049 int i; 00050 if (!suitableRows_) { 00051 for (i=0;i<nRows;i++) { 00052 checkRow[i]=1; 00053 } 00054 } else { 00055 // initialize and extend rows to current size 00056 memset(checkRow,0,nRows*sizeof(int)); 00057 memcpy(checkRow,suitableRows_,CoinMin(nRows,numberRows_)*sizeof(int)); 00058 } 00059 temp.createRowList(si,checkRow); 00060 // now cut down further by only allowing rows with fractional solution 00061 double * solution = new double[nCols]; 00062 memcpy(solution,si.getColSolution(),nCols*sizeof(double)); 00063 const int * column = rowCopy->getIndices(); 00064 const int * rowStart = rowCopy->getVectorStarts(); 00065 const int * rowLength = rowCopy->getVectorLengths(); 00066 const double * collower = si.getColLower(); 00067 const double * colupper = si.getColUpper(); 00068 int * suitable = temp.suitableRows_; 00069 00070 // At present I am using new and delete as easier to see arrays in debugger 00071 int * fixed = new int[nCols]; // mark fixed columns 00072 00073 for (i=0;i<nCols;i++) { 00074 if (si.isBinary(i) ) { 00075 fixed[i]=0; 00076 if (colupper[i]-collower[i]<epsilon_) { 00077 solution[i]=0.0; 00078 fixed[i]=2; 00079 } else if (solution[i]<epsilon_) { 00080 solution[i]=0.0; 00081 fixed[i]=-1; 00082 } else if (solution[i]>onetol_) { 00083 solution[i]=1.0; 00084 fixed[i]=+1; 00085 } 00086 } else { 00087 //mark as fixed even if not (can not intersect any interesting rows) 00088 solution[i]=0.0; 00089 fixed[i]=3; 00090 } 00091 } 00092 // first do packed 00093 const double * rowlower = si.getRowLower(); 00094 const double * rowupper = si.getRowUpper(); 00095 for (i=0;i<nRows;i++) { 00096 if (suitable[i]) { 00097 int k; 00098 double sum=0.0; 00099 if (rowupper[i]>1.001) suitable[i]=-1; 00100 for (k=rowStart[i]; k<rowStart[i]+rowLength[i];k++) { 00101 int icol=column[k]; 00102 if (!fixed[icol]) sum += solution[icol]; 00103 } 00104 if (sum<0.9) suitable[i]=-1; //say no good 00105 } 00106 } 00107 #ifdef CGL_DEBUG 00108 const OsiRowCutDebugger * debugger = si.getRowCutDebugger(); 00109 if (debugger&&!debugger->onOptimalPath(si)) 00110 debugger = NULL; 00111 #else 00112 const OsiRowCutDebugger * debugger = NULL; 00113 #endif 00114 temp.generateCuts(debugger, *rowCopy,solution, 00115 si.getReducedCost(),cs,suitable,fixed,true); 00116 // now cover 00117 //if no >= then skip 00118 bool doCover=false; 00119 int nsuitable=0; 00120 for (i=0;i<nRows;i++) { 00121 suitable[i]=abs(suitable[i]); 00122 if (suitable[i]) { 00123 int k; 00124 double sum=0.0; 00125 if (rowlower[i]<0.999) sum=2.0; 00126 if (rowupper[i]>1.001) doCover=true; 00127 for (k=rowStart[i]; k<rowStart[i]+rowLength[i];k++) { 00128 int icol=column[k]; 00129 if (!fixed[icol]) sum += solution[icol]; 00130 if (fixed[icol]==1) sum=2.0; //don't use if any at 1 00131 } 00132 if (sum>1.1) { 00133 suitable[i]=-1; //say no good 00134 } else { 00135 nsuitable++; 00136 } 00137 } 00138 } 00139 if (doCover&&nsuitable) 00140 temp.generateCuts(debugger, *rowCopy,solution,si.getReducedCost(), 00141 cs,suitable,fixed,false); 00142 delete [] checkRow; 00143 delete [] solution; 00144 delete [] fixed; 00145 00146 } |
|
A function that tests the methods in the CglOddHole class. The only reason for it not to be a member method is that this way it doesn't have to be compiled into the library. And that's a gain, because the library should be compiled with optimization on, but this method should be compiled with debugging. Definition at line 23 of file CglOddHoleTest.cpp.
00026 { 00027 CoinRelFltEq eq(0.000001); 00028 00029 // Test default constructor 00030 { 00031 CglOddHole aGenerator; 00032 } 00033 00034 // Test copy & assignment 00035 { 00036 CglOddHole rhs; 00037 { 00038 CglOddHole bGenerator; 00039 CglOddHole cGenerator(bGenerator); 00040 rhs=bGenerator; 00041 } 00042 } 00043 00044 00045 // test on simple case 00046 { 00047 const int nRows=3; 00048 const int nCols=3; 00049 const int nEls=6; 00050 const double elem[]={1.0,1.0,1.0,1.0,1.0,1.0}; 00051 const int row[]={0,1,0,2,1,2}; 00052 const int start[]={0,2,4}; 00053 const int len[]={2,2,2}; 00054 CoinPackedMatrix matrix(true,nRows,nCols,nEls,elem,row,start,len); 00055 const double sol[]={0.5,0.5,0.5}; 00056 const double dj[]={0,0,0}; 00057 const int which[]={1,1,1}; 00058 const int fixed[]={0,0,0}; 00059 OsiCuts cs; 00060 CglOddHole test1; 00061 test1.generateCuts(NULL,matrix,sol,dj,cs,which,fixed,true); 00062 CoinPackedVector check; 00063 int index[] = {0,1,2}; 00064 double el[] = {1,1,1}; 00065 check.setVector(3,index,el); 00066 //assert (cs.sizeRowCuts()==2); 00067 assert (cs.sizeRowCuts()==1); 00068 // sort Elements in increasing order 00069 CoinPackedVector rpv=cs.rowCut(0).row(); 00070 rpv.sortIncrIndex(); 00071 assert (check==rpv); 00072 } 00073 00074 // Testcase /u/rlh/osl2/mps/scOneInt.mps 00075 // Model has 3 continous, 2 binary, and 1 general 00076 // integer variable. 00077 { 00078 OsiSolverInterface * siP = baseSiP->clone(); 00079 00080 std::string fn = mpsDir+"scOneInt"; 00081 siP->readMps(fn.c_str(),"mps"); 00082 #if 0 00083 CglOddHole cg; 00084 int nCols=siP->getNumCols(); 00085 00086 // Test the siP methods for detecting 00087 // variable type 00088 int numCont=0, numBinary=0, numIntNonBinary=0, numInt=0; 00089 for (int thisCol=0; thisCol<nCols; thisCol++) { 00090 if ( siP->isContinuous(thisCol) ) numCont++; 00091 if ( siP->isBinary(thisCol) ) numBinary++; 00092 if ( siP->isIntegerNonBinary(thisCol) ) numIntNonBinary++; 00093 if ( siP->isInteger(thisCol) ) numInt++; 00094 } 00095 assert(numCont==3); 00096 assert(numBinary==2); 00097 assert(numIntNonBinary==1); 00098 assert(numInt==3); 00099 00100 00101 // Test initializeCutGenerator 00102 siP->initialSolve(); 00103 assert(xstar !=NULL); 00104 for (i=0; i<nCols; i++){ 00105 assert(complement[i]==0); 00106 } 00107 int nRows=siP->getNumRows(); 00108 for (i=0; i<nRows; i++){ 00109 int vectorsize = siP->getMatrixByRow()->getVectorSize(i); 00110 assert(vectorsize==2); 00111 } 00112 00113 kccg.cleanUpCutGenerator(complement,xstar); 00114 #endif 00115 delete siP; 00116 } 00117 00118 } |