#include <CglProbing.hpp>
Inheritance diagram for CglProbing:
Public Member Functions | |
Generate Cuts | |
virtual void | generateCuts (const OsiSolverInterface &si, OsiCuts &cs) const |
int | generateCutsAndModify (const OsiSolverInterface &si, OsiCuts &cs) |
snapshot | |
void | snapshot (const OsiSolverInterface &si, char *possible=NULL) |
deleteSnapshot | |
void | deleteSnapshot () |
Deletes snapshot. | |
Get tighter column bounds | |
const double * | tightLower () const |
Lower. | |
const double * | tightUpper () const |
Upper. | |
Get possible freed up row bounds - only valid after mode==3 | |
const double * | relaxedRowLower () const |
Lower. | |
const double * | relaxedRowUpper () const |
Upper. | |
Change mode | |
void | setMode (int mode) |
Set. | |
int | getMode () const |
Get. | |
Change maxima | |
void | setMaxPass (int value) |
Set maximum number of passes per node. | |
int | getMaxPass () const |
Get maximum number of passes per node. | |
void | setMaxProbe (int value) |
Set maximum number of unsatisfied variables to look at. | |
int | getMaxProbe () const |
Get maximum number of unsatisfied variables to look at. | |
void | setMaxLook (int value) |
Set maximum number of variables to look at in one probe. | |
int | getMaxLook () const |
Get maximum number of variables to look at in one probe. | |
Stop or restart row cuts (otherwise just fixing from probing) | |
void | setRowCuts (int type) |
int | rowCuts () const |
Get. | |
Whether use objective as constraint | |
void | setUsingObjective (bool yesNo) |
Set. | |
int | getUsingObjective () const |
Get. | |
Constructors and destructors | |
CglProbing () | |
Default constructor. | |
CglProbing (const CglProbing &) | |
Copy constructor. | |
CglProbing & | operator= (const CglProbing &rhs) |
Assignment operator. | |
virtual | ~CglProbing () |
Destructor. | |
virtual void | refreshSolver (OsiSolverInterface *solver) |
This can be used to refresh any inforamtion. | |
Private Member Functions | |
probe | |
int | probe (const OsiSolverInterface &si, const OsiRowCutDebugger *debugger, OsiCuts &cs, double *colLower, double *colUpper, CoinPackedMatrix *rowCopy, double *rowLower, double *rowUpper, char *intVar, double *minR, double *maxR, int *markR, int *look, int nlook) const |
Does probing and adding cuts. | |
int | gutsOfGenerateCuts (const OsiSolverInterface &si, OsiCuts &cs, double *rowLower, double *rowUpper, double *colLower, double *colUpper) const |
Private Attributes | |
Private member data | |
CoinPackedMatrix * | rowCopy_ |
Row copy. | |
double * | rowLower_ |
Lower bounds on rows. | |
double * | rowUpper_ |
Upper bounds on rows. | |
double * | colLower_ |
Lower bounds on columns. | |
double * | colUpper_ |
Upper bounds on columns. | |
int | numberRows_ |
Number of rows in snapshot (0 if no snapshot). | |
int | numberColumns_ |
Number of columns in snapshot (must == current). | |
double | primalTolerance_ |
Tolerance to see if infeasible. | |
int | mode_ |
Mode - 0 lazy using snapshot, 1 just unsatisfied, 2 all. | |
int | rowCuts_ |
int | maxPass_ |
Maximum number of passes to do in probing. | |
int | maxProbe_ |
Maximum number of unsatisfied variables to probe. | |
int | maxStack_ |
Maximum number of variables to look at in one probe. | |
bool | usingObjective_ |
Whether to include objective as constraint. | |
int | numberIntegers_ |
Number of integer variables. | |
disaggregation * | cutVector_ |
Friends | |
void | CglProbingUnitTest (const OsiSolverInterface *siP, const std::string mpdDir) |
Definition at line 11 of file CglProbing.hpp.
|
Generate probing/disaggregation cuts for the model of the solver interface, si. This is a simplification of probing ideas put into OSL about ten years ago. The only known documentation is a copy of a talk handout - we think Robin Lougee-Heimer has a copy! For selected integer variables (e.g. unsatisfied ones) the effect of setting them up or down is investigated. Setting a variable up may in turn set other variables (continuous as well as integer). There are various possible results: 1) It is shown that problem is infeasible (this may also be because objective function or reduced costs show worse than best solution). If the other way is feasible we can generate a column cut (and continue probing), if not feasible we can say problem infeasible. 2) If both ways are feasible, it can happen that x to 0 implies y to 1 and x to 1 implies y to 1 (again a column cut). More common is that x to 0 implies y to 1 and x to 1 implies y to 0 so we could substitute for y which might lead later to more powerful cuts. This is not done in this code as there is no mechanism for returning information. 3) When x to 1 a constraint went slack by c. We can tighten the constraint ax + .... <= b (where a may be zero) to (a+c)x + .... <= b. If this cut is violated then it is generated. 4) Similarly we can generate implied disaggregation cuts Note - differences to cuts in OSL. a) OSL had structures intended to make this faster. b) The "chaining" in 2) was done c) Row cuts modified original constraint rather than adding cut b) This code can cope with general integer variables. Insert the generated cuts into OsiCut, cs. If a "snapshot" of a matrix exists then this will be used. Presumably this will give global cuts and will be faster. No check is done to see if cuts will be global. Otherwise use current matrix. Both row cuts and column cuts may be returned The mode options are: 0) Only unsatisfied integer variables will be looked at. If no information exists for that variable then probing will be done so as a by-product you "may" get a fixing or infeasibility. This will be fast and is only available if a snapshot exists (otherwise as 1). The bounds in the snapshot are the ones used. 1) Look at unsatisfied integer variables, using current bounds. Probing will be done on all looked at. 2) Look at all integer variables, using current bounds. Probing will be done on all If generateCutsAndModify is used then new relaxed row bounds and tightened coliumn bounds are generated Returns number of infeasibilities Implements CglCutGenerator. Definition at line 369 of file CglProbing.cpp. References gutsOfGenerateCuts().
00371 { 00372 #ifdef CGL_DEBUG 00373 const OsiRowCutDebugger * debugger = si.getRowCutDebugger(); 00374 if (debugger&&debugger->onOptimalPath(si)) { 00375 printf("On optimal path %d\n",nPath); 00376 nPath++; 00377 int nCols=si.getNumCols(); 00378 int i; 00379 const double * solution = si.getColSolution(); 00380 const double * lower = si.getColLower(); 00381 const double * upper = si.getColUpper(); 00382 const double * optimal = debugger->optimalSolution(); 00383 const double * objective = si.getObjCoefficients(); 00384 double objval1=0.0,objval2=0.0; 00385 for (i=0;i<nCols;i++) { 00386 printf("%d %g %g %g %g\n",i,lower[i],solution[i],upper[i],optimal[i]); 00387 objval1 += solution[i]*objective[i]; 00388 objval2 += optimal[i]*objective[i]; 00389 assert(optimal[i]>=lower[i]&&optimal[i]<=upper[i]); 00390 } 00391 printf("current obj %g, integer %g\n",objval1,objval2); 00392 } 00393 #endif 00394 int nRows=si.getNumRows(); 00395 double * rowLower = new double[nRows+1]; 00396 double * rowUpper = new double[nRows+1]; 00397 00398 int nCols=si.getNumCols(); 00399 double * colLower = new double[nCols]; 00400 double * colUpper = new double[nCols]; 00401 00402 int ninfeas=gutsOfGenerateCuts(si,cs,rowLower,rowUpper,colLower,colUpper); 00403 if (ninfeas) { 00404 // generate infeasible cut and return 00405 OsiRowCut rc; 00406 rc.setLb(DBL_MAX); 00407 rc.setUb(0.0); 00408 cs.insert(rc); 00409 #ifdef CGL_DEBUG 00410 const OsiRowCutDebugger * debugger = si.getRowCutDebugger(); 00411 if (debugger&&debugger->onOptimalPath(si)) 00412 assert(!debugger->invalidCut(rc)); 00413 #endif 00414 } 00415 delete [] rowLower; 00416 delete [] rowUpper; 00417 delete [] colLower; 00418 delete [] colUpper; 00419 } |
|
Does most of work of generateCuts Returns number of infeasibilities Definition at line 482 of file CglProbing.cpp. References colLower_, colUpper_, CoinPackedVector::getElements(), CoinPackedVector::getIndices(), CoinPackedVector::getNumElements(), CglProbing::disaggregation::index, CoinPackedVector::insert(), CglProbing::disaggregation::lastLBWhenAt0, CglProbing::disaggregation::lastLBWhenAt1, CglProbing::disaggregation::lastUBWhenAt0, CglProbing::disaggregation::lastUBWhenAt1, maxProbe_, mode_, CglProbing::disaggregation::newValue, numberColumns_, numberIntegers_, numberRows_, primalTolerance_, probe(), rowCopy_, rowLower_, rowUpper_, CglProbing::disaggregation::sequence, and usingObjective_. Referenced by generateCuts().
00486 { 00487 // Get basic problem information 00488 int nRows; 00489 00490 CoinPackedMatrix * rowCopy=NULL; 00491 00492 // get branch and bound cutoff 00493 double cutoff; 00494 si.getDblParam(OsiDualObjectiveLimit,cutoff); 00495 cutoff *= si.getObjSense(); 00496 if (fabs(cutoff)>1.0e30) 00497 assert (cutoff>1.0e30); 00498 int mode=mode_; 00499 00500 int nCols=si.getNumCols(); 00501 00502 // get integer variables 00503 char * intVar = new char[nCols]; 00504 int i; 00505 int numberIntegers=0; 00506 for (i=0;i<nCols;i++) { 00507 if (si.isInteger(i)) { 00508 intVar[i]=1; 00509 numberIntegers++; 00510 } else { 00511 intVar[i]=0; 00512 } 00513 } 00514 00515 int ninfeas=0; 00516 00517 // see if using cached copy or not 00518 if (!numberRows_) { 00519 // create from current 00520 nRows=si.getNumRows(); 00521 00522 // mode==0 is invalid if going from current matrix 00523 if (mode==0) 00524 mode=1; 00525 rowCopy = new CoinPackedMatrix(*si.getMatrixByRow()); 00526 // add in objective if there is a cutoff 00527 if (cutoff<1.0e30&&usingObjective_) { 00528 int * columns = new int[nCols]; 00529 double * elements = new double[nCols]; 00530 int n=0; 00531 const double * objective = si.getObjCoefficients(); 00532 bool maximize = (si.getObjSense()==-1); 00533 for (i=0;i<nCols;i++) { 00534 if (objective[i]) { 00535 elements[n]= (maximize) ? -objective[i] : objective[i]; 00536 columns[n++]=i; 00537 } 00538 } 00539 rowCopy->appendRow(n,columns,elements); 00540 delete [] columns; 00541 delete [] elements; 00542 memcpy(rowLower,si.getRowLower(),nRows*sizeof(double)); 00543 memcpy(rowUpper,si.getRowUpper(),nRows*sizeof(double)); 00544 rowLower[nRows]=-DBL_MAX; 00545 rowUpper[nRows]=cutoff; 00546 nRows++; 00547 } else { 00548 memcpy(rowLower,si.getRowLower(),nRows*sizeof(double)); 00549 memcpy(rowUpper,si.getRowUpper(),nRows*sizeof(double)); 00550 } 00551 memcpy(colLower,si.getColLower(),nCols*sizeof(double)); 00552 memcpy(colUpper,si.getColUpper(),nCols*sizeof(double)); 00553 } else { 00554 // use snapshot 00555 nRows=numberRows_; 00556 assert(nCols==numberColumns_); 00557 00558 rowCopy = rowCopy_; 00559 rowLower = new double[nRows]; 00560 rowUpper = new double[nRows]; 00561 memcpy(rowLower,rowLower_,nRows*sizeof(double)); 00562 memcpy(rowUpper,rowUpper_,nRows*sizeof(double)); 00563 rowLower[nRows-1]=-DBL_MAX; 00564 if (usingObjective_) { 00565 rowUpper[nRows-1]=cutoff; 00566 } else { 00567 rowUpper[nRows-1]=DBL_MAX; 00568 } 00569 memcpy(colLower,colLower_,nCols*sizeof(double)); 00570 memcpy(colUpper,colUpper_,nCols*sizeof(double)); 00571 if (mode) { 00572 // tighten bounds to reflect state of problem 00573 const double * lower = si.getColLower(); 00574 const double * upper = si.getColUpper(); 00575 for (i=0;i<nCols;i++) { 00576 if (colLower[i]<lower[i]) 00577 colLower[i]=lower[i]; 00578 if (colUpper[i]>upper[i]) 00579 colUpper[i]=upper[i]; 00580 } 00581 } 00582 } 00583 #ifdef CGL_DEBUG 00584 const OsiRowCutDebugger * debugger = si.getRowCutDebugger(); 00585 if (debugger&&!debugger->onOptimalPath(si)) 00586 debugger = NULL; 00587 #else 00588 const OsiRowCutDebugger * debugger = NULL; 00589 #endif 00590 00591 const int * column = rowCopy->getIndices(); 00592 const int * rowStart = rowCopy->getVectorStarts(); 00593 const int * rowLength = rowCopy->getVectorLengths(); 00594 const double * rowElements = rowCopy->getElements(); 00595 00596 if (mode) { 00597 ninfeas= tighten(colLower, colUpper, column, rowElements, 00598 rowStart, rowLength, rowLower, rowUpper, 00599 nRows, nCols, intVar, 2, primalTolerance_); 00600 if (!ninfeas) { 00601 // create column cuts where integer bounds have changed 00602 { 00603 const double * lower = si.getColLower(); 00604 const double * upper = si.getColUpper(); 00605 const double * colsol = si.getColSolution(); 00606 int numberChanged=0,ifCut=0; 00607 CoinPackedVector lbs; 00608 CoinPackedVector ubs; 00609 for (i = 0; i < nCols; ++i) { 00610 if (intVar[i]) { 00611 colUpper[i] = min(upper[i],floor(colUpper[i]+1.0e-4)); 00612 if (colUpper[i]<upper[i]-1.0e-8) { 00613 if (colUpper[i]<colsol[i]-1.0e-8) 00614 ifCut=1; 00615 ubs.insert(i,colUpper[i]); 00616 numberChanged++; 00617 } 00618 colLower[i] = max(lower[i],ceil(colLower[i]-1.0e-4)); 00619 if (colLower[i]>lower[i]+1.0e-8) { 00620 if (colLower[i]>colsol[i]+1.0e-8) 00621 ifCut=1; 00622 lbs.insert(i,colLower[i]); 00623 numberChanged++; 00624 } 00625 } 00626 } 00627 if (numberChanged) { 00628 OsiColCut cc; 00629 cc.setUbs(ubs); 00630 cc.setLbs(lbs); 00631 if (ifCut) { 00632 cc.setEffectiveness(100.0); 00633 } else { 00634 cc.setEffectiveness(1.0e-5); 00635 } 00636 #ifdef CGL_DEBUG 00637 checkBounds(debugger,cc); 00638 #endif 00639 cs.insert(cc); 00640 } 00641 } 00642 int * markR = new int [nRows]; 00643 double * minR = new double [nRows]; 00644 double * maxR = new double [nRows]; 00645 int * look = new int[nCols]; 00646 int nLook=0; 00647 // get min max etc for rows 00648 tighten2(colLower, colUpper, column, rowElements, 00649 rowStart, rowLength, rowLower, rowUpper, 00650 minR , maxR , markR, nRows, nCols); 00651 // decide what to look at 00652 if (mode==1) { 00653 const double * colsol = si.getColSolution(); 00654 double_int_pair * array = new double_int_pair [nCols]; 00655 for (i=0;i<nCols;i++) { 00656 if (intVar[i]&&colUpper[i]-colLower[i]>1.0e-8) { 00657 double away = fabs(0.5-(colsol[i]-floor(colsol[i]))); 00658 if (away<0.49999) { 00659 array[nLook].infeasibility=away; 00660 array[nLook++].sequence=i; 00661 } 00662 } 00663 } 00664 std::sort(array,array+nLook,double_int_pair_compare()); 00665 nLook=min(nLook,maxProbe_); 00666 for (i=0;i<nLook;i++) { 00667 look[i]=array[i].sequence; 00668 } 00669 delete [] array; 00670 } else { 00671 for (i=0;i<nCols;i++) { 00672 if (intVar[i]&&colUpper[i]-colLower[i]>1.0e-8) { 00673 look[nLook++]=i; 00674 } 00675 } 00676 } 00677 ninfeas= probe(si, debugger, cs, colLower, colUpper, rowCopy, 00678 rowLower, rowUpper, 00679 intVar, minR, maxR, markR, 00680 look,nLook); 00681 delete [] look; 00682 delete [] markR; 00683 delete [] minR; 00684 delete [] maxR; 00685 } 00686 } else { 00687 // global cuts from previous calculations 00688 // could check more thoroughly that integers are correct 00689 assert(numberIntegers==numberIntegers_); 00690 // make up list of new variables to look at 00691 int * markR = new int [nRows]; 00692 double * minR = new double [nRows]; 00693 double * maxR = new double [nRows]; 00694 int * look = new int[nCols]; 00695 int nLook=0; 00696 const double * colsol = si.getColSolution(); 00697 for (i=0;i<numberIntegers_;i++) { 00698 int j=cutVector_[i].sequence; 00699 if (!cutVector_[i].newValue&&colUpper[j]-colLower[j]>1.0e-8) { 00700 double away = fabs(0.5-(colsol[j]-floor(colsol[j]))); 00701 if (away<0.4999999) { 00702 look[nLook++]=j; 00703 } 00704 } 00705 } 00706 // get min max etc for rows 00707 tighten2(colLower, colUpper, column, rowElements, 00708 rowStart, rowLength, rowLower, rowUpper, 00709 minR , maxR , markR, nRows, nCols); 00710 OsiCuts csNew; 00711 ninfeas= probe(si, debugger, csNew, colLower, colUpper, rowCopy, 00712 rowLower, rowUpper, 00713 intVar, minR, maxR, markR, 00714 look,nLook); 00715 if (!ninfeas) { 00716 // go through row cuts 00717 int nCuts = csNew.sizeRowCuts(); 00718 int iCut; 00719 // need space for backward lookup 00720 // just for ones being looked at 00721 int * backward = new int [2*nCols]; 00722 int * onList = backward + nCols; 00723 for (i=0;i<numberIntegers_;i++) { 00724 int j=cutVector_[i].sequence; 00725 backward[j]=i; 00726 onList[j]=0; 00727 } 00728 for (i=0;i<nLook;i++) { 00729 onList[look[i]]=1; 00730 } 00731 // first do counts 00732 // we know initialized to zero 00733 for (iCut=0;iCut<nCuts;iCut++) { 00734 OsiRowCut rcut; 00735 CoinPackedVector rpv; 00736 rcut = csNew.rowCut(iCut); 00737 rpv = rcut.row(); 00738 assert(rpv.getNumElements()==2); 00739 const int * indices = rpv.getIndices(); 00740 double* elements = rpv.getElements(); 00741 double lb=rcut.lb(); 00742 // find out which integer 00743 i=backward[indices[1]]; 00744 if (lb==-DBL_MAX) { 00745 // UB 00746 if (elements[1]<0.0) { 00747 cutVector_[i].lastUBWhenAt0++; 00748 } else { 00749 cutVector_[i].lastUBWhenAt1++; 00750 } 00751 } else { 00752 // LB 00753 if (elements[1]>0.0) { 00754 cutVector_[i].lastLBWhenAt0++; 00755 } else { 00756 cutVector_[i].lastLBWhenAt1++; 00757 } 00758 } 00759 } 00760 // allocate space 00761 for (i=0;i<numberIntegers_;i++) { 00762 int j=cutVector_[i].sequence; 00763 if (onList[j]&&!cutVector_[i].newValue) { 00764 disaggregation thisOne=cutVector_[i]; 00765 int total; 00766 // set to start of each type 00767 cutVector_[i].lastUBWhenAt0 =0; 00768 total = thisOne.lastUBWhenAt0; 00769 cutVector_[i].lastUBWhenAt1 = total; 00770 total += thisOne.lastUBWhenAt1; 00771 cutVector_[i].lastLBWhenAt0 = total; 00772 total += thisOne.lastLBWhenAt0; 00773 cutVector_[i].lastLBWhenAt1 = total; 00774 total += thisOne.lastLBWhenAt1; 00775 cutVector_[i].newValue=new double[total]; 00776 cutVector_[i].index=new int[total]; 00777 } 00778 } 00779 // now put in 00780 for (iCut=0;iCut<nCuts;iCut++) { 00781 OsiRowCut rcut; 00782 CoinPackedVector rpv; 00783 int iput; 00784 rcut = csNew.rowCut(iCut); 00785 rpv = rcut.row(); 00786 assert(rpv.getNumElements()==2); 00787 const int * indices = rpv.getIndices(); 00788 double* elements = rpv.getElements(); 00789 double lb=rcut.lb(); 00790 // find out which integer 00791 i=backward[indices[1]]; 00792 if (lb==-DBL_MAX) { 00793 // UB 00794 if (elements[1]<0.0) { 00795 iput=cutVector_[i].lastUBWhenAt0; 00796 cutVector_[i].newValue[iput]=elements[1]; 00797 cutVector_[i].index[iput]=indices[0]; 00798 cutVector_[i].lastUBWhenAt0++; 00799 } else { 00800 iput=cutVector_[i].lastUBWhenAt1; 00801 cutVector_[i].newValue[iput]=elements[1]; 00802 cutVector_[i].index[iput]=indices[0]; 00803 cutVector_[i].lastUBWhenAt1++; 00804 } 00805 } else { 00806 // LB 00807 if (elements[1]>0.0) { 00808 iput=cutVector_[i].lastLBWhenAt0; 00809 cutVector_[i].newValue[iput]=elements[1]; 00810 cutVector_[i].index[iput]=indices[0]; 00811 cutVector_[i].lastLBWhenAt0++; 00812 } else { 00813 iput=cutVector_[i].lastLBWhenAt1; 00814 cutVector_[i].newValue[iput]=elements[1]; 00815 cutVector_[i].index[iput]=indices[0]; 00816 cutVector_[i].lastLBWhenAt1++; 00817 } 00818 } 00819 } 00820 // now see if any disaggregation cuts are violated 00821 for (i=0;i<numberIntegers_;i++) { 00822 int j=cutVector_[i].sequence; 00823 double upperInt=colUpper_[j]; 00824 double lowerInt=colLower_[j]; 00825 double solInt=colsol[j]; 00826 double down = solInt-lowerInt; 00827 double up = upperInt-solInt; 00828 double lower, upper, solValue; 00829 int icol; 00830 double newSol,value,newValue; 00831 int index[2]; 00832 double element[2]; 00833 if (colUpper[j]-colLower[j]>1.0e-8) { 00834 double away = fabs(0.5-(colsol[j]-floor(colsol[j]))); 00835 if (away<0.4999999) { 00836 disaggregation thisOne=cutVector_[i]; 00837 int k; 00838 OsiRowCut rc; 00839 // UB changes when integer goes to lb 00840 for (k=0;k<thisOne.lastUBWhenAt0;k++) { 00841 icol = thisOne.index[k]; 00842 value = thisOne.newValue[k]; // new U - old U 00843 solValue=colsol[icol]; 00844 upper=colUpper_[icol]; 00845 newValue= value + upper; 00846 if (solValue > newValue - value * down + primalTolerance_) { 00847 rc.setLb(-DBL_MAX); 00848 rc.setUb(newValue + lowerInt*value); 00849 index[0]=icol; 00850 element[0]=1.0; 00851 index[1]=j; 00852 element[1]= value; 00853 // effectiveness is how far j moves 00854 newSol = (rc.ub()-solValue)/element[1]; 00855 if (mode_) 00856 assert(newSol>solInt); 00857 rc.setEffectiveness(newSol-solInt); 00858 if (rc.effectiveness()>1.0e-3) { 00859 rc.setRow(2,index,element); 00860 #ifdef CGL_DEBUG 00861 if (debugger) assert(!debugger->invalidCut(rc)); 00862 #endif 00863 cs.insert(rc); 00864 } 00865 } 00866 } 00867 // UB changes when integer goes to ub 00868 for (k=thisOne.lastUBWhenAt0;k<thisOne.lastUBWhenAt1;k++) { 00869 icol = thisOne.index[k]; 00870 value = thisOne.newValue[k]; // new U - old U 00871 solValue=colsol[icol]; 00872 upper=colUpper_[icol]; 00873 newValue= value + upper; 00874 if (solValue > newValue - value * up + primalTolerance_) { 00875 rc.setLb(-DBL_MAX); 00876 rc.setUb(newValue - upperInt*value); 00877 index[0]=icol; 00878 element[0]=1.0; 00879 index[1]=j; 00880 element[1]= value; 00881 // effectiveness is how far j moves 00882 newSol = (rc.ub()-solValue)/element[1]; 00883 if (mode_) 00884 assert(newSol>solInt); 00885 rc.setEffectiveness(newSol-solInt); 00886 if (rc.effectiveness()>1.0e-3) { 00887 rc.setRow(2,index,element); 00888 #ifdef CGL_DEBUG 00889 if (debugger) assert(!debugger->invalidCut(rc)); 00890 #endif 00891 cs.insert(rc); 00892 } 00893 } 00894 } 00895 // LB changes when integer goes to lb 00896 for (k=thisOne.lastUBWhenAt1;k<thisOne.lastLBWhenAt0;k++) { 00897 icol = thisOne.index[k]; 00898 value = thisOne.newValue[k]; // new L - old L 00899 solValue=colsol[icol]; 00900 lower=colLower_[icol]; 00901 newValue= value + lower; 00902 if (solValue < newValue - value * down - primalTolerance_) { 00903 rc.setLb(newValue + lowerInt*value); 00904 rc.setUb(DBL_MAX); 00905 index[0]=icol; 00906 element[0]=1.0; 00907 index[1]=j; 00908 element[1]= value; 00909 // effectiveness is how far j moves 00910 newSol = (rc.lb()-solValue)/element[1]; 00911 if (mode_) 00912 assert(newSol>solInt); 00913 rc.setEffectiveness(newSol-solInt); 00914 if (rc.effectiveness()>1.0e-3) { 00915 rc.setRow(2,index,element); 00916 #ifdef CGL_DEBUG 00917 if (debugger) assert(!debugger->invalidCut(rc)); 00918 #endif 00919 cs.insert(rc); 00920 } 00921 } 00922 } 00923 // LB changes when integer goes to ub 00924 for (k=thisOne.lastLBWhenAt0;k<thisOne.lastLBWhenAt1;k++) { 00925 icol = thisOne.index[k]; 00926 value = thisOne.newValue[k]; // new L - old L 00927 solValue=colsol[icol]; 00928 lower=colLower_[icol]; 00929 newValue= value + lower; 00930 if (solValue < newValue - value * up - primalTolerance_) { 00931 rc.setLb(newValue - upperInt*value); 00932 rc.setUb(DBL_MAX); 00933 index[0]=icol; 00934 element[0]=1.0; 00935 index[1]=j; 00936 element[1]= value; 00937 // effectiveness is how far j moves 00938 newSol = (rc.lb()-solValue)/element[1]; 00939 if (mode_) 00940 assert(newSol>solInt); 00941 rc.setEffectiveness(newSol-solInt); 00942 if (rc.effectiveness()>1.0e-3) { 00943 rc.setRow(2,index,element); 00944 #ifdef CGL_DEBUG 00945 if (debugger) assert(!debugger->invalidCut(rc)); 00946 #endif 00947 cs.insert(rc); 00948 } 00949 } 00950 } 00951 } 00952 } 00953 } 00954 delete [] backward; 00955 } 00956 delete [] look; 00957 delete [] markR; 00958 delete [] minR; 00959 delete [] maxR; 00960 } 00961 // delete stuff 00962 if (!numberRows_) { 00963 delete rowCopy; 00964 } else { 00965 delete [] rowLower; 00966 delete [] rowUpper; 00967 } 00968 delete [] intVar; 00969 return ninfeas; 00970 } |
|
Set 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both) Definition at line 2225 of file CglProbing.cpp. References rowCuts_.
02226 { 02227 if (type>=0&&type<4) 02228 rowCuts_=type; 02229 } |
|
Create a copy of matrix which is to be used this is to speed up process and to give global cuts Can give an array with 1 set to select, 0 to ignore column bounds are tightened If array given then values of 1 will be set to 0 if redundant Definition at line 2046 of file CglProbing.cpp. References colLower_, colUpper_, deleteSnapshot(), numberColumns_, numberIntegers_, numberRows_, primalTolerance_, rowCopy_, rowLower_, and rowUpper_.
02048 { 02049 deleteSnapshot(); 02050 // Get basic problem information 02051 02052 numberColumns_=si.getNumCols(); 02053 numberRows_=si.getNumRows(); 02054 colLower_ = new double[numberColumns_]; 02055 colUpper_ = new double[numberColumns_]; 02056 memcpy(colLower_,si.getColLower(),numberColumns_*sizeof(double)); 02057 memcpy(colUpper_,si.getColUpper(),numberColumns_*sizeof(double)); 02058 rowLower_= new double [numberRows_+1]; 02059 rowUpper_= new double [numberRows_+1]; 02060 memcpy(rowLower_,si.getRowLower(),numberRows_*sizeof(double)); 02061 memcpy(rowUpper_,si.getRowUpper(),numberRows_*sizeof(double)); 02062 02063 int i; 02064 if (possible) { 02065 for (i=0;i<numberRows_;i++) { 02066 if (!possible[i]) { 02067 rowLower_[i]=-DBL_MAX; 02068 rowUpper_[i]=DBL_MAX; 02069 } 02070 } 02071 } 02072 02073 02074 char * intVar = new char[numberColumns_]; 02075 numberIntegers_=0; 02076 for (i=0;i<numberColumns_;i++) { 02077 if (si.isInteger(i)) { 02078 intVar[i]=1; 02079 numberIntegers_++; 02080 } else { 02081 intVar[i]=0; 02082 } 02083 } 02084 02085 rowCopy_ = new CoinPackedMatrix(*si.getMatrixByRow()); 02086 02087 const int * column = rowCopy_->getIndices(); 02088 const int * rowStart = rowCopy_->getVectorStarts(); 02089 const int * rowLength = rowCopy_->getVectorLengths(); 02090 const double * rowElements = rowCopy_->getElements(); 02091 02092 int ninfeas= tighten(colLower_, colUpper_, column, rowElements, 02093 rowStart, rowLength, rowLower_, rowUpper_, 02094 numberRows_, numberColumns_, intVar, 5, primalTolerance_); 02095 assert (!ninfeas); 02096 02097 // do integer stuff for mode 0 02098 cutVector_ = new disaggregation [numberIntegers_]; 02099 memset(cutVector_,0,numberIntegers_*sizeof(disaggregation)); 02100 numberIntegers_=0; 02101 for (i=0;i<numberColumns_;i++) { 02102 if (intVar[i]) { 02103 cutVector_[numberIntegers_++].sequence=i; 02104 } 02105 } 02106 delete [] intVar; 02107 02108 // now delete rows 02109 if (possible) { 02110 for (i=0;i<numberRows_;i++) { 02111 if (rowLower_[i]<-1.0e30&&rowUpper_[i]>1.0e30) 02112 possible[i]=0; 02113 } 02114 } 02115 int * index = new int[numberRows_]; 02116 int nDrop=0,nKeep=0; 02117 for (i=0;i<numberRows_;i++) { 02118 if (rowLower_[i]<-1.0e30&&rowUpper_[i]>1.0e30) { 02119 index[nDrop++]=i; 02120 } else { 02121 rowLower_[nKeep]=rowLower_[i]; 02122 rowUpper_[nKeep++]=rowUpper_[i]; 02123 } 02124 } 02125 numberRows_=nKeep; 02126 if (nDrop) 02127 rowCopy_->deleteRows(nDrop,index); 02128 delete [] index; 02129 // add in objective 02130 int * columns = new int[numberColumns_]; 02131 double * elements = new double[numberColumns_]; 02132 int n=0; 02133 const double * objective = si.getObjCoefficients(); 02134 bool maximize = (si.getObjSense()==-1); 02135 for (i=0;i<numberColumns_;i++) { 02136 if (objective[i]) { 02137 elements[n]= (maximize) ? -objective[i] : objective[i]; 02138 columns[n++]=i; 02139 } 02140 } 02141 rowCopy_->appendRow(n,columns,elements); 02142 delete [] columns; 02143 delete [] elements; 02144 numberRows_++; 02145 02146 } |
|
A function that tests the methods in the CglProbing 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 24 of file CglProbingTest.cpp.
00027 { 00028 CoinRelFltEq eq(0.000001); 00029 00030 // Test default constructor 00031 { 00032 CglProbing aGenerator; 00033 } 00034 00035 // Test copy & assignment 00036 { 00037 CglProbing rhs; 00038 { 00039 CglProbing bGenerator; 00040 CglProbing cGenerator(bGenerator); 00041 rhs=bGenerator; 00042 } 00043 } 00044 00045 { 00046 OsiCuts osicuts; 00047 CglProbing test1; 00048 OsiSolverInterface * siP = baseSiP->clone(); 00049 int i; 00050 int nColCuts; 00051 int nRowCuts; 00052 00053 std::string fn = mpsDir+"p0033"; 00054 siP->readMps(fn.c_str(),"mps"); 00055 siP->initialSolve(); 00056 // just unsatisfied variables 00057 test1.generateCuts(*siP,osicuts); 00058 nColCuts = osicuts.sizeColCuts(); 00059 nRowCuts = osicuts.sizeRowCuts(); 00060 std::cout<<"There are "<<nRowCuts<<" probing cuts"<<std::endl; 00061 { 00062 std::cout<<"there are "<<nColCuts<<" probing column cuts"<<std::endl; 00063 const double * lo = siP->getColLower(); 00064 const double * up = siP->getColUpper(); 00065 for (i=0; i<nColCuts; i++){ 00066 OsiColCut ccut; 00067 CoinPackedVector cpv; 00068 ccut = osicuts.colCut(i); 00069 cpv = ccut.lbs(); 00070 int n = cpv.getNumElements(); 00071 int j; 00072 const int * indices = cpv.getIndices(); 00073 double* elements = cpv.getElements(); 00074 for (j=0;j<n;j++) { 00075 int icol=indices[j]; 00076 if (elements[j]>lo[icol]) 00077 std::cout<<"Can increase lb on "<<icol<<" from "<<lo[icol]<< 00078 " to "<<elements[j]<<std::endl; 00079 } 00080 cpv = ccut.ubs(); 00081 n = cpv.getNumElements(); 00082 indices = cpv.getIndices(); 00083 elements = cpv.getElements(); 00084 for (j=0;j<n;j++) { 00085 int icol=indices[j]; 00086 if (elements[j]<up[icol]) 00087 std::cout<<"Can decrease ub on "<<icol<<" from "<<up[icol]<< 00088 " to "<<elements[j]<<std::endl; 00089 } 00090 } 00091 } 00092 for (i=0; i<nRowCuts; i++){ 00093 OsiRowCut rcut; 00094 CoinPackedVector rpv; 00095 const double * colsol = siP->getColSolution(); 00096 rcut = osicuts.rowCut(i); 00097 rpv = rcut.row(); 00098 const int n = rpv.getNumElements(); 00099 const int * indices = rpv.getIndices(); 00100 double* elements = rpv.getElements(); 00101 double sum2=0.0; 00102 int k=0; 00103 double lb=rcut.lb(); 00104 double ub=rcut.ub(); 00105 for (k=0; k<n; k++){ 00106 int column=indices[k]; 00107 sum2 += colsol[column]*elements[k]; 00108 } 00109 if (sum2 >ub + 1.0e-7 ||sum2 < lb - 1.0e-7) { 00110 std::cout<<"Cut "<<i<<" lb "<<lb<<" solution "<<sum2<<" ub "<<ub<<std::endl; 00111 for (k=0; k<n; k++){ 00112 int column=indices[k]; 00113 std::cout<<"(col="<<column<<",el="<<elements[k]<<",sol="<< 00114 colsol[column]<<") "; 00115 } 00116 std::cout <<std::endl; 00117 } 00118 } 00119 CoinPackedVector check; 00120 int index[] = {6,32}; 00121 double el[] = {1,1}; 00122 check.setVector(2,index,el); 00123 assert (osicuts.sizeRowCuts()==2); 00124 // sort Elements in increasing order 00125 CoinPackedVector rpv=osicuts.rowCut(1).row(); 00126 rpv.sortIncrIndex(); 00127 assert (check==rpv); 00128 assert (osicuts.rowCut(1).lb()==1.0); 00129 // now all variables 00130 osicuts=OsiCuts(); 00131 test1.setMode(2); 00132 test1.generateCuts(*siP,osicuts); 00133 nColCuts = osicuts.sizeColCuts(); 00134 nRowCuts = osicuts.sizeRowCuts(); 00135 std::cout<<"There are "<<nRowCuts<<" probing cuts"<<std::endl; 00136 { 00137 std::cout<<"there are "<<nColCuts<<" probing column cuts"<<std::endl; 00138 const double * lo = siP->getColLower(); 00139 const double * up = siP->getColUpper(); 00140 for (i=0; i<nColCuts; i++){ 00141 OsiColCut ccut; 00142 CoinPackedVector cpv; 00143 ccut = osicuts.colCut(i); 00144 cpv = ccut.lbs(); 00145 int n = cpv.getNumElements(); 00146 int j; 00147 const int * indices = cpv.getIndices(); 00148 double* elements = cpv.getElements(); 00149 for (j=0;j<n;j++) { 00150 int icol=indices[j]; 00151 if (elements[j]>lo[icol]) 00152 std::cout<<"Can increase lb on "<<icol<<" from "<<lo[icol]<< 00153 " to "<<elements[j]<<std::endl; 00154 } 00155 cpv = ccut.ubs(); 00156 n = cpv.getNumElements(); 00157 indices = cpv.getIndices(); 00158 elements = cpv.getElements(); 00159 for (j=0;j<n;j++) { 00160 int icol=indices[j]; 00161 if (elements[j]<up[icol]) 00162 std::cout<<"Can decrease ub on "<<icol<<" from "<<up[icol]<< 00163 " to "<<elements[j]<<std::endl; 00164 } 00165 } 00166 } 00167 for (i=0; i<nRowCuts; i++){ 00168 OsiRowCut rcut; 00169 CoinPackedVector rpv; 00170 const double * colsol = siP->getColSolution(); 00171 rcut = osicuts.rowCut(i); 00172 rpv = rcut.row(); 00173 const int n = rpv.getNumElements(); 00174 const int * indices = rpv.getIndices(); 00175 double* elements = rpv.getElements(); 00176 double sum2=0.0; 00177 int k=0; 00178 double lb=rcut.lb(); 00179 double ub=rcut.ub(); 00180 for (k=0; k<n; k++){ 00181 int column=indices[k]; 00182 sum2 += colsol[column]*elements[k]; 00183 } 00184 if (sum2 >ub + 1.0e-7 ||sum2 < lb - 1.0e-7) { 00185 std::cout<<"Cut "<<i<<" lb "<<lb<<" solution "<<sum2<<" ub "<<ub<<std::endl; 00186 for (k=0; k<n; k++){ 00187 int column=indices[k]; 00188 std::cout<<"(col="<<column<<",el="<<elements[k]<<",sol="<< 00189 colsol[column]<<") "; 00190 } 00191 std::cout <<std::endl; 00192 } 00193 } 00194 assert (osicuts.sizeRowCuts()==10); 00195 delete siP; 00196 } 00197 00198 } |
|
Row cuts flag 0 no cuts, 1 just disaggregation type, 2 coefficient ( 3 both) Definition at line 232 of file CglProbing.hpp. Referenced by operator=(), probe(), rowCuts(), and setRowCuts(). |