CglKnapsackCover Class Reference

#include <CglKnapsackCover.hpp>

Inheritance diagram for CglKnapsackCover:

List of all members.

Public Member Functions
void	setTestedRowIndices (int num, const int *ind)
Generate Cuts
virtual void	generateCuts (const OsiSolverInterface &si, OsiCuts &cs) const
Constructors and destructors
	CglKnapsackCover ()
	Default constructor.
	CglKnapsackCover (const CglKnapsackCover &)
	Copy constructor.
CglKnapsackCover &	operator= (const CglKnapsackCover &rhs)
	Assignment operator.
virtual	~CglKnapsackCover ()
	Destructor.
Sets and gets
void	setMaxInKnapsack (int value)
	Set limit on number in knapsack.
int	getMaxInKnapsack () const
	get limit on number in knapsack
Private Member Functions
Private methods
int	deriveAKnapsack (const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, bool treatAsLRow, double &b, int *complement, double *xstar, int rowIndex, int numberElements, const int *index, const double *element) const
int	deriveAKnapsack (const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, double &b, int *complement, double *xstar, int rowIndex, const CoinPackedVectorBase &matrixRow) const
int	findExactMostViolatedMinCover (int nCols, int row, CoinPackedVector &krow, double b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
int	findLPMostViolatedMinCover (int nCols, int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
int	findGreedyCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
	find a minimum cover by a simple greedy approach
int	liftCoverCut (double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut) const
	lift the cover inequality
int	liftAndUncomplementAndAdd (double rowub, CoinPackedVector &krow, double &b, int *complement, int row, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs) const
	sequence-independent lift and uncomplement and add the resulting cut to the cut set
void	seqLiftAndUncomplementAndAdd (int nCols, double *xstar, int *complement, int row, int nRowElem, double &b, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs) const
	sequence-dependent lift, uncomplement and add the resulting cut to the cut set
void	liftUpDownAndUncomplementAndAdd (int nCols, double *xstar, int *complement, int row, int nRowElem, double &b, CoinPackedVector &fracCover, CoinPackedVector &atOne, CoinPackedVector &remainder, OsiCuts &cs) const
	sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set
int	findPseudoJohnAndEllisCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
	find a cover using a variation of the logic found in OSL (w/o SOS)
int	findJohnAndEllisCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &fracCover, CoinPackedVector &atOnes, CoinPackedVector &remainder) const
	find a cover using the basic logic found in OSL (w/o SOS)
int	exactSolveKnapsack (int n, double c, double const *pp, double const *ww, double &z, int *x) const
Private Attributes
Private member data
double	epsilon_
	epsilon
double	epsilon2_
	Tolerance to use for violation - bigger than epsilon_.
double	onetol_
	1-epsilon
int	maxInKnapsack_
	Maximum in knapsack.
int	numRowsToCheck_
int *	rowsToCheck_
Friends
void	CglKnapsackCoverUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)

---

Detailed Description

Knapsack Cover Cut Generator Class

Definition at line 11 of file CglKnapsackCover.hpp.

---

Member Function Documentation

int CglKnapsackCover::deriveAKnapsack (  const OsiSolverInterface &  si, OsiCuts &  cs, CoinPackedVector &  krow, bool  treatAsLRow, double &  b, int *  complement, double *  xstar, int  rowIndex, int  numberElements, const int *  index, const double *  element )  const [private]

deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise. Definition at line 738 of file CglKnapsackCover.cpp. References CoinPackedVector::clear(), epsilon_, CoinPackedVector::getElements(), CoinPackedVector::getIndices(), CoinPackedVector::getNumElements(), CoinPackedVector::insert(), and onetol_. Referenced by generateCuts(). { int i; krow.clear(); // if the matrixRow represent a ge inequality, then // leMatrixRow == -matrixRow // otherwise // leMatrixRow == matrixRow. CoinPackedVector leMatrixRow(numberElements,index,element); double maxKrowElement = -DBL_MAX; double minKrowElement = DBL_MAX; if (treatAsLRow) { // treat as if L row } else { // treat as if G row b=-b; std::transform(leMatrixRow.getElements(), leMatrixRow.getElements() + leMatrixRow.getNumElements(), leMatrixRow.getElements(), std::negate<double>()); } // nBinUnsat is a counter for the number of unsatisfied // (i.e. fractional) binary vars int nBinUnsat =0; const double * colupper = si.getColUpper(); const double * collower = si.getColLower(); // At this point, leMatrixRow and b represent a le inequality in general // variables. // To derive a canonical knapsack inequality in free binary variable, // process out the continuous & non-binary integer & fixed binary variables. // If the non-free-binary variables can be appropriately bounded, // net them out of the constraint, otherwise abandon this row and return 0. const int * indices = leMatrixRow.getIndices(); const double * elements = leMatrixRow.getElements(); // for every variable in the constraint for (i=0; i<leMatrixRow.getNumElements(); i++){ // if the variable is not a free binary var if ( !si.isFreeBinary(indices[i]) ) { // and the coefficient is strictly negative if(elements[i]<-epsilon_){ // and the variable has a finite upper bound if (colupper[indices[i]] < si.getInfinity()){ // then replace the variable with its upper bound. b=b-elements[i]*colupper[indices[i]]; } else { return 0; } } // if the coefficient is strictly positive else if(elements[i]>epsilon_){ // and the variable has a finite lower bound if (collower[indices[i]] > -si.getInfinity()){ // then replace the variable with its lower bound. b=b-elements[i]*collower[indices[i]]; } else { return 0; } } // note: if the coefficient is zero, the variable is not included in the // knapsack inequality. } // else the variable is a free binary var and is included in the knapsack // inequality. // note: the variable is included regardless of its solution value to the // lp relaxation. else{ krow.insert(indices[i], elements[i]); // if the binary variable is unsatified (i.e. has fractional value), // increment the counter. if(xstar[indices[i]] > epsilon_ && xstar[indices[i]] < onetol_) nBinUnsat++; // keep track of the largest and smallest elements in the knapsack // (the idea is if there is not a lot of variation in the knapsack // coefficients, it is unlikely we will find a violated minimal // cover from this knapsack so don't even bother trying) if (fabs(elements[i]) > maxKrowElement) maxKrowElement = fabs(elements[i]); if (fabs(elements[i]) < minKrowElement) minKrowElement = fabs(elements[i]); } } // If there's little variation in the knapsack coefficients, return 0. // If there are no unsatisfied binary variables, return. // If there's only one binary, return. // ToDo: but why return if 2 binary? ...there was some assumption in the // findVioMinCover..(?) // Anyway probing will probably find something if (krow.getNumElements() < 3 || nBinUnsat == 0 || maxKrowElement-minKrowElement < 1.0e-3*maxKrowElement ) { return 0; } // However if we do decide to do when count is two - look carefully if (krow.getNumElements()==2) { const int * indices = krow.getIndices(); double * elements = krow.getElements(); double sum=0.0; for(i=0; i<2; i++){ int iColumn = indices[i]; sum += elements[i]*xstar[iColumn]; } if (sum<b-1.0e-4) { return 0; } else { printf("*** Doubleton Row is "); for(i=0; i<2; i++){ int iColumn = indices[i]; sum += elements[i]*xstar[iColumn]; printf("%d (coeff = %g, value = %g} ",indices[i], elements[i],xstar[iColumn]); } printf("<= %g - go for it\n",b); } } // At this point krow and b represent a le inequality in binary variables. // To obtain an le inequality with all positive coefficients, complement // any variable with a negative coefficient by changing the sign of // the coefficient, adjusting the rhs, and adjusting xstar, the column // solution vector. { const int s = krow.getNumElements(); const int * indices = krow.getIndices(); double * elements = krow.getElements(); for(i=0; i<s; i++){ if (elements[i] < -epsilon_) { complement[indices[i]]= 1; elements[i] *= -1; b+=elements[i]; xstar[indices[i]]=1.0-xstar[indices[i]]; } } } // Quick feasibility check. // If the problem is infeasible, add an infeasible col cut to cut set // e.g. one that has lb > ub. // TODO: test this scenario in BCP if (b < 0 ){ OsiColCut cc; int index = krow.getIndices()[0]; const double fakeLb = colupper[index] + 1.0;; // yes, colupper. const double fakeUb = collower[index]; assert( fakeUb < fakeLb ); cc.setLbs( 1, &index, &fakeLb); cc.setUbs( 1, &index, &fakeLb); cc.setEffectiveness(DBL_MAX); cs.insert(cc); #ifdef PRINT_DEBUG printf("Cgl: Problem is infeasible\n"); #endif } // At this point, krow and b represent a le inequality with postive // coefficients. // If any coefficient a_j > b, then x_j = 0, return 0 // If any complemented var has coef a_j > b, then x_j = 1, return 0 int fixed = 0; CoinPackedVector fixedBnd; for(i=0; i<krow.getNumElements(); i++){ if (krow.getElements()[i]> b){ fixedBnd.insert(krow.getIndices()[i],complement[krow.getIndices()[i]]); #ifdef PRINT_DEBUG printf("Variable %i being fixed to %i due to row %i.\n", krow.getIndices()[i],complement[krow.getIndices()[i]],rowIndex); #endif fixed = 1; } } // After all possible variables are fixed by adding a column cut with // equivalent lower and upper bounds, return if (fixed) { OsiColCut cc; cc.setLbs(fixedBnd); cc.setUbs(fixedBnd); cc.setEffectiveness(DBL_MAX); return 0; } return 1; }

int CglKnapsackCover::exactSolveKnapsack (  int  n, double  c, double const *  pp, double const *  ww, double &  z, int *  x )  const [private]

A C-style implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem. (ToDo: implement the more efficient dynamic programming approach) (Reference: Martello and Toth, Knapsack Problems, Wiley, 1990, p30.) Definition at line 2549 of file CglKnapsackCover.cpp. References epsilon2_. Referenced by findExactMostViolatedMinCover(), liftUpDownAndUncomplementAndAdd(), and seqLiftAndUncomplementAndAdd(). { // The knapsack problem is to find: // max {sum(j=1,n) p_j*x_j st. sum (j=1,n)w_j*x_j <= c, x binary} // Notation: // xhat : current solution vector // zhat : current solution value = sum (j=1,n) p_j*xhat_j // chat : current residual capacity = c - sum (j=1,n) w_j*xhat_j // x : best solution so far, n-vector. // z : value of the best solution so far = sum (j=1,n) p_j*x_j // Input: n, the number of variables; // c, the rhs; // p, n-vector of objective func. coefficients; // w, n-vector of the row coeff. // Output: z, the optimal objective function value; // x, the optimal (binary) solution n-vector; // Assumes items are sorted p_1/w_1 >= p_2/w_2 >= ... >= p_n/w_n memset(x, 0, (n)*sizeof(int)); int * xhat = new int[n+1]; memset(xhat, 0, (n+1)*sizeof(int)); int j; // set up: adding the extra element and // accounting for the FORTRAN vs C difference in indexing arrays. double * p = new double[n+2]; double * w = new double[n+2]; int ii; for (ii=1; ii<n+1; ii++){ p[ii]=pp[ii-1]; w[ii]=ww[ii-1]; } // 1. initialize double zhat = 0.0; z = 0.0; double chat = c+epsilon2_; p[n+1] = 0.0; w[n+1]= DBL_MAX; j=1; while (1){ // 2. compute upper bound u // "find r = min {i: sum k=j,i w_k>chat};" ii=j; double wSemiSum = w[j]; double pSemiSum = p[j]; while (wSemiSum <= chat && ii<n+2){ ii++; wSemiSum+=w[ii]; pSemiSum+=p[ii]; } if (ii==n+2){ printf("Exceeded iterator limit. Aborting...\n"); abort(); } // r = ii at this point wSemiSum -= w[ii]; pSemiSum -= p[ii]; double u = pSemiSum + floor((chat - wSemiSum)*p[ii]/w[ii]); // "if (z >= zhat + u) goto 5: backtrack;" if (!(z >= zhat + u)) { do { // 3. perform a forward step while (w[j] <= chat){ chat = chat - w[j]; zhat = zhat + p[j]; xhat[j] = 1; j+=1; } if (j<=n) { xhat[j]= 0; j+=1; } } while(j==n); // "if (j<n) goto 2: compute_ub;" if (j<n) continue; // 4. up date the best solution so far if (zhat > z) { z=zhat; int k; for (k=0; k<n; k++){ x[k]=xhat[k+1]; } } j=n; if (xhat[n] == 1){ chat = chat+ w[n]; zhat = zhat-p[n]; xhat[n]=0; } } // 5. backtrack // "find i=max{k<j:xhat[k]=1};" int i=j-1; while (!(xhat[i]==1) && i>0){ i--; } // "if (no such i exists) return;" if (i==0){ delete [] p; delete [] w; delete [] xhat; return 1; } chat = chat + w[i]; zhat=zhat -p[i]; xhat[i]=0; j=i+1; // "goto 2: compute_ub;" } }

int CglKnapsackCover::findExactMostViolatedMinCover (  int  nCols, int  row, CoinPackedVector &  krow, double  b, double *  xstar, CoinPackedVector &  cover, CoinPackedVector &  remainder )  const [private]

Find a violated minimal cover from a canonical form knapsack inequality by solving the -most- violated cover problem and postprocess to ensure minimality Definition at line 1196 of file CglKnapsackCover.cpp. References epsilon_, exactSolveKnapsack(), CoinPackedVector::getElements(), CoinPackedVector::getIndices(), CoinPackedVector::getNumElements(), CoinPackedVector::insert(), CoinPackedVector::reserve(), CoinPackedVector::sort(), CoinPackedVector::sortDecrElement(), CoinPackedVectorBase::sum(), and CoinPackedVector::truncate(). Referenced by generateCuts(). { // assumes the row is in canonical knapsack form // A violated min.cover inequality exists if the // opt obj func value (oofv) < 1: // oofv = min sum (1-xstar_j)z_j // s.t. sum a_jz_j > b // x binary // The vector z is the incidence vector // defines the set R and the cover inequality. // (sum j in R) x_j <= |R|-1 // This is the min version of the knapsack problem. // (note that strict inequalty...bleck) // To obtain the max version, complement the z's, z_j=1-y_j and // adjust the constraint. // oofv = (sum (1-xstar_j))- max sum (1-xstar)y_j // s.t. sum a_jy_j <= (sum over j)a_j - b (- EPSILON)] // y binary // If oofv < 1, violated min cover inequality has // incidence vector z=1-y and rhs= num of nonzero's in z, i.e. // the number 0 in y. // We solve the 0-1 knapsack problem by explicit ennumeration double elementSum = krow.sum(); // Redundant/useless adjusted rows should have been trapped in // transformation to canonical form of knapsack inequality if (elementSum < b + epsilon_) { #ifdef PRINT_DEBUG printf("Redundant/useless adjusted row\n"); #endif return -1; } // Order krow in nonincreasing order of coefObj_j/a_j. // (1-xstar_1)/a_1 >= (1-xstar_2)/a_2 >= ... >= (1-xstar_n)/a_n // by defining this full-storage array "ratio" to be the external sort key. double * ratio= new double[nCols]; memset(ratio, 0, (nCols*sizeof(double))); int i; { const int * indices = krow.getIndices(); const double * elements = krow.getElements(); for (i=0; i<krow.getNumElements(); i++){ if (fabs(elements[i])> epsilon_ ){ ratio[indices[i]]= (1.0-xstar[indices[i]]) / elements[i]; } else { ratio[indices[i]] = 0.0; } } } // ToDo: would be nice to have sortkey NOT be full-storage vector CoinDecrSolutionOrdered dso(ratio); krow.sort(dso); #ifdef CGL_DEBUG // sanity check for ( i=1; i<krow.getNumElements(); i++ ) { double ratioim1 = ratio[krow.getIndices()[i-1]]; double ratioi= ratio[krow.getIndices()[i]]; assert( ratioim1 >= ratioi ); } #endif // Recall: // oofv = (sum (1-xstar_j))- max sum (1-xstar)y_j // s.t. sum a_jy_j <= (sum over j)a_j - b (- epsilon_)] // y binary double objConst = 0.0; double exactOptVal = -1.0; int * exactOptSol = new int[krow.getNumElements()]; double * p = new double[krow.getNumElements()]; double * w = new double[krow.getNumElements()]; int kk; for (kk=0; kk<krow.getNumElements(); kk++){ p[kk]=1.0-xstar[krow.getIndices()[kk]]; w[kk]=krow.getElements()[kk]; objConst+=p[kk]; } // vectors are indexed in ratioSortIndex order exactSolveKnapsack(krow.getNumElements(), (elementSum-b-epsilon_), p, w, exactOptVal, exactOptSol); if(objConst-exactOptVal < 1){ cover.reserve(krow.getNumElements()); remainder.reserve(krow.getNumElements()); // Partition the krow into the cover and the remainder. // The cover is complement of solution. double coverElementSum = 0; for(kk=0;kk<krow.getNumElements();kk++){ if(exactOptSol[kk]==0){ cover.insert(krow.getIndices()[kk],krow.getElements()[kk]); coverElementSum += krow.getElements()[kk]; } else { remainder.insert(krow.getIndices()[kk],krow.getElements()[kk]); } } cover.sortDecrElement(); // We have a violated cover inequality. // Construct a -minimal- violated cover // by testing and potentially tossing smallest // elements double oneLessCoverElementSum = coverElementSum - cover.getElements()[cover.getNumElements()-1]; while (oneLessCoverElementSum > b){ // move the excess cover member into the set of remainders remainder.insert(cover.getIndices()[cover.getNumElements()-1], cover.getElements()[cover.getNumElements()-1]); cover.truncate(cover.getNumElements()-1); oneLessCoverElementSum -= cover.getElements()[cover.getNumElements()-1]; } #ifdef PRINT_DEBUG printf("Exact Most Violated Cover: row %i has cover of size %i.\n", row,cover.getNumElements()); //double sumCover = 0.0; for (i=0; i<cover.getNumElements(); i++){ printf("index %i, element %g, xstar value % g \n", cover.getIndices()[i], cover.getElements()[i], xstar[cover.getIndices()[i]]); //sumCover += cover.getElements()[i]; } printf("The b = %g, and the cover sum is %g\n\n", b, cover.sum() ); #endif // local clean up delete [] exactOptSol; delete [] p; delete [] w; delete [] ratio; return 1; // found an exact one } // local clean up delete [] exactOptSol; delete [] p; delete [] w; delete [] ratio; return 0; // didn't find an exact one }

int CglKnapsackCover::findLPMostViolatedMinCover (  int  nCols, int  row, CoinPackedVector &  krow, double &  b, double *  xstar, CoinPackedVector &  cover, CoinPackedVector &  remainder )  const [private]

Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover problem Definition at line 992 of file CglKnapsackCover.cpp. References epsilon_, CoinPackedVector::getElements(), CoinPackedVector::getIndices(), CoinPackedVector::getNumElements(), CoinPackedVector::insert(), CoinPackedVector::reserve(), CoinPackedVector::sort(), CoinPackedVector::sortDecrElement(), CoinPackedVectorBase::sum(), and CoinPackedVector::truncate(). Referenced by generateCuts(). { // Assumes krow and b describe a knapsack inequality in canonical form // Given a knapsack inequality sum a_jx_j <= b, and optimal lp solution // xstart, a violated minimal cover inequality exists if the following 0-1 // programming problem has an optimal objective function value (oofv) < 1 // oofv = min sum (1-xstar_j)z_j // s.t. sum a_jz_j > b // z binary // The vector z is an incidence vector, defining the cover R with the // associated cover inequality: // (sum j in R) x_j <= |R|-1 // This problem is itself a (min version of the) knapsack problem // but with a unsightly strict inequalty. // To transform transform it into a max version, // complement the z's, z_j=1-y_j. // To compensate for the strict inequality, subtract epsilon from the rhs. // oofv = (sum (1-xstar_j))- max sum (1-xstar)y_j // s.t. sum a_jy_j <= (sum over j)a_j - b (- EPSILON) // y binary // If oofv < 1, then a violated min cover inequality has // incidence vector z with elements z_j=1-y_j and rhs= num of nonzero's in // z, i.e. the number of 0's in y. // If the size of the knapsack is "small", we solve the problem exactly. // If the size of the knapsack is large, we solve the (simpler) lp relaxation // of the knapsack problem and postprocess to ensure the construction of a // minimimal cover. // We also assume that testing/probing/fixing based on the knapsack structure // is done elsewhere. Only convenient-to-do sanity checks are done here. // (We do not assume that data is integer.) double elementSum = krow.sum(); // Redundant/useless adjusted rows should have been trapped in the // transformation to the canonical form of knapsack inequality if (elementSum < b + epsilon_) { return -1; } // Order krow in nonincreasing order of coefObj_j/a_j. // (1-xstar_1)/a_1 >= (1-xstar_2)/a_2 >= ... >= (1-xstar_n)/a_n // by defining this full-storage array "ratio" to be the external sort key. double * ratio= new double[nCols]; memset(ratio, 0, (nCols*sizeof(double))); int i; for (i=0; i<krow.getNumElements(); i++){ if (fabs(krow.getElements()[i])> epsilon_ ){ ratio[krow.getIndices()[i]]= (1.0-xstar[krow.getIndices()[i]]) / (krow.getElements()[i]); } else { ratio[krow.getIndices()[i]] = 0.0; } } // ToDo: would be nice to have sortkey NOT be full-storage vector CoinDecrSolutionOrdered dso(ratio); krow.sort(dso); // Find the "critical" element index "r" in the knapsack lp solution int r = 0; double sum = krow.getElements()[0]; while ( sum <= (elementSum - b - epsilon_ ) ){ r++; sum += krow.getElements()[r]; } // Note: It is possible the r=0, and you get a violated minimal cover // if (r=0), then you've got a var with a really large coeff. compared // to the rest of the row. // r=0 says trivially that the // sum of ALL the binary vars in the row <= (cardinality of all the set -1) // Note: The cover may not be minimal if there are alternate optimals to the // maximization problem, so the cover must be post-processed to ensure // minimality. // "r" is the critical element // The lp relaxation column solution is: // y_j = 1 for j=0,...,(r-1) // y_r = (elementSum - b - sum + krow.element()[r])/krow.element()[r] // y_j = 0 for j=r+1,...,krow.getNumElements() // The number of nonzeros in the lp column solution is r+1 // if oofv to the lp knap >= 1, then no violated min cover is possible int nCover; double lpoofv=0.0; for (i=r+1; i<krow.getNumElements(); i++){ lpoofv += (1-xstar[krow.getIndices()[i]]); } double ipofv = lpoofv + (1-xstar[krow.getIndices()[r]]); // Couldn't find an lp violated min cover inequality if (ipofv > 1.0 - epsilon_){ delete [] ratio; return -1; } else { // Partition knapsack into cover and noncover (i.e. remainder) // pieces nCover = krow.getNumElements() - r; double coverSum =0.0; cover.reserve(nCover); remainder.reserve(r); for (i=r; i<krow.getNumElements(); i++){ cover.insert(krow.getIndices()[i],krow.getElements()[i]); coverSum += krow.getElements()[i]; } for (i=0; i<r; i++){ remainder.insert(krow.getIndices()[i],krow.getElements()[i]); } #ifdef PRINT_DEBUG if (coverSum <= b){ printf("The identified cover is NOT a cover\n"); abort(); } #endif // Sort cover in terms of knapsack row coefficients cover.sortDecrElement(); // We have a violated cover inequality. // Construct a -minimal- violated cover // by testing and potentially tossing smallest // elements double oneLessCoverSum = coverSum - cover.getElements()[nCover-1]; while (oneLessCoverSum > b){ // move the excess cover member into the set of remainders remainder.insert(cover.getIndices()[nCover-1], cover.getElements()[nCover-1]); cover.truncate(nCover-1); nCover--; oneLessCoverSum -= cover.getElements()[nCover-1]; } if (nCover<2){ #ifdef PRINT_DEBUG printf("nCover < 2...aborting\n"); #endif abort(); } #ifdef PRINT_DEBUG /* debug */ printf("\ Lp relax of most violated minimal cover: row %i has cover of size %i.\n", row,nCover); //double sumCover = 0.0; for (i=0; i<cover.getNumElements(); i++){ printf("index %i, element %g, xstar value % g \n", cover.getIndices()[i],cover.getElements()[i], xstar[cover.getIndices()[i]]); //sumCover += cover.getElements()[i]; } printf("The b = %g, and the cover sum is %g\n\n", b, cover.sum()); #endif #ifdef P0201 double ppsum=0.0; for (i=0; i<nCover; i++){ ppsum += p0201[krow.getIndices()[i]]; } if (ppsum > nCover-1){ printf("\ \nBad cover from lp relax of most violated cover..aborting\n"); abort(); } #endif /* clean up */ delete [] ratio; return 1; } }

void CglKnapsackCover::generateCuts (  const OsiSolverInterface &  si, OsiCuts &  cs )  const [virtual]

Generate knapsack cover cuts for the model of the solver interface, si. Insert the generated cuts into OsiCut, cs. Implements CglCutGenerator. Definition at line 25 of file CglKnapsackCover.cpp. References deriveAKnapsack(), epsilon_, findExactMostViolatedMinCover(), findGreedyCover(), findJohnAndEllisCover(), findLPMostViolatedMinCover(), findPseudoJohnAndEllisCover(), CoinPackedVector::getIndices(), CoinPackedVector::getNumElements(), liftAndUncomplementAndAdd(), liftUpDownAndUncomplementAndAdd(), maxInKnapsack_, numRowsToCheck_, seqLiftAndUncomplementAndAdd(), and CoinPackedVector::setVector(). { // Get basic problem information int nRows=si.getNumRows(); int nCols=si.getNumCols(); // Create working space for "canonical" knapsack inequality // - krow will contain the coefficients and indices of the // (potentially complemented) variables in the knapsack inequality. // - b is the rhs of knapsack inequality. // - complement[i] is 1 if the index i in krow refers to the complement // of the variable, and 0 otherwise. CoinPackedVector krow; double b=0.0; int * complement= new int[nCols]; // Create a local copy of the column solution (colsol), call it xstar, and // inititalize it. // Assumes the lp-relaxation has been solved, and the solver interface // has a meaningful colsol. double * xstar= new double[nCols]; // To allow for vub knapsacks int * thisColumnIndex = new int [nCols]; double * thisElement = new double[nCols]; int * back = new int[nCols]; const double *colsol = si.getColSolution(); int k; // For each row point to vub variable // -1 if no vub // -2 if can skip row for knapsacks int * vub = new int [nRows]; // For each column point to vub row int * vubRow = new int [nCols]; double * vubValue = new double [nRows]; // Take out all fixed double * effectiveUpper = new double [nRows]; double * effectiveLower = new double [nRows]; const double * colUpper = si.getColUpper(); const double * colLower = si.getColLower(); for (k=0; k<nCols; k++){ back[k]=-1; xstar[k]=colsol[k]; complement[k]=0; vubRow[k]=-1; if (si.isBinary(k)) { if (si.isFreeBinary(k)) { vubRow[k]=-2; } else { vubRow[k]=-10; } } else if (colUpper[k]==colLower[k]) { vubRow[k]=-10; // fixed } } int rowIndex; int numberVub=0; const CoinPackedMatrix * matrixByRow = si.getMatrixByRow(); const double * elementByRow = matrixByRow->getElements(); const int * column = matrixByRow->getIndices(); const int * rowStart = matrixByRow->getVectorStarts(); const int * rowLength = matrixByRow->getVectorLengths(); const double * rowUpper = si.getRowUpper(); const double * rowLower = si.getRowLower(); // Scan all rows looking for possibles for (rowIndex=0;rowIndex<nRows;rowIndex++) { int start = rowStart[rowIndex]; int end = start + rowLength[rowIndex]; double upRhs = rowUpper[rowIndex]; double loRhs = rowLower[rowIndex]; int numberContinuous=0; int numberBinary=0; int iCont=-1; double sum = 0.0; double valueContinuous=0.0; double valueBinary=0.0; int iBinary=-1; int j; for (j=start;j<end;j++) { int iColumn=column[j]; if (colUpper[iColumn]>colLower[iColumn]) { sum += colsol[iColumn]*elementByRow[j]; if (vubRow[iColumn]==-2) { // binary numberBinary++; valueBinary=elementByRow[j]; iBinary=iColumn; } else if (vubRow[iColumn]==-1) { // only use if not at bound if (colsol[iColumn]<colUpper[iColumn]-1.0e-6&& colsol[iColumn]>colLower[iColumn]+1.0e-6) { // possible iCont=iColumn; numberContinuous++; valueContinuous=elementByRow[j]; } else { // ** needs more thought numberContinuous ++; iCont=-1; } } else { // ** needs more thought numberContinuous ++; iCont=-1; if (colsol[iColumn]<colUpper[iColumn]-1.0e-6&& colsol[iColumn]>colLower[iColumn]+1.0e-6) { // already assigned numberContinuous ++; iCont=-1; } } } else { // fixed upRhs -= colLower[iColumn]*elementByRow[j]; loRhs -= colLower[iColumn]*elementByRow[j]; } } // see if binding effectiveUpper[rowIndex] = upRhs; effectiveLower[rowIndex] = loRhs; vubValue[rowIndex] = valueContinuous; bool possible = false; if (fabs(sum-upRhs)<1.0e-5) { possible=true; } else { effectiveUpper[rowIndex]=DBL_MAX; } if (fabs(sum-loRhs)<1.0e-5) { possible=true; } else { effectiveLower[rowIndex]=-DBL_MAX; } if (!numberBinary||numberBinary+numberContinuous>maxInKnapsack_) possible=false; if (possible) { // binding with binary if(numberContinuous==1&&iCont>=0) { // vub if (numberBinary==1) #ifdef PRINT_DEBUG printf("vub (by row %d) %g <= 0-1 %g * %d + %g * %d <= %g\n", rowIndex,effectiveLower[rowIndex],valueBinary,iBinary, valueContinuous,iCont,effectiveUpper[rowIndex]); #endif vubRow[iCont]=rowIndex; vub[rowIndex]=iCont; numberVub++; } else if (numberBinary>1) { // could be knapsack vub[rowIndex]=-1; } else { // no point looking at this row vub[rowIndex]=-2; } } else { // no point looking at this row vub[rowIndex]=-2; } } // Main loop int numCheck = 0; int* toCheck = 0; if (!rowsToCheck_) { toCheck = new int[nRows]; CoinIotaN(toCheck, nRows, 0); numCheck = nRows; } else { numCheck = numRowsToCheck_; toCheck = rowsToCheck_; } // Set up number of tries for each row int ntry; if (numberVub) ntry=4; else ntry=2; //ntry=2; // switch off for (int ii=0; ii < numCheck; ++ii){ rowIndex = toCheck[ii]; if (rowIndex < 0 || rowIndex >= nRows) continue; if (vub[rowIndex]==-2) continue; #ifdef PRINT_DEBUG std::cout << "CGL: Processing row " << rowIndex << std::endl; #endif // Get a tight row // (want to be able to // experiment by turning this on and off) // // const double * pi=si.rowprice(); // if (fabs(pi[row]) < epsilon_){ // continue; // } // Derive a "canonical" knapsack // // inequality (in binary variables) // // from the model row in mixed integer variables // #ifdef CGL_DEBUG assert(!krow.getNumElements()); #endif double effectiveRhs[4]; double rhs[4]; double sign[]={0.0,0.0,-1.0,1.0}; bool rowType[] = {false,true,false,true}; effectiveRhs[0] = effectiveLower[rowIndex]; rhs[0]=rowLower[rowIndex]; effectiveRhs[2] = effectiveRhs[0]; rhs[2]= effectiveRhs[0]; effectiveRhs[1] = effectiveUpper[rowIndex]; rhs[1]=rowUpper[rowIndex]; effectiveRhs[3] = effectiveRhs[1]; rhs[3]= effectiveRhs[1]; int itry; #ifdef CGL_DEBUG int kcuts[4]; memset(kcuts,0,4*sizeof(int)); #endif for (itry=0;itry<ntry;itry++) { #ifdef CGL_DEBUG int nlast=cs.sizeRowCuts(); #endif // see if to skip if (fabs(effectiveRhs[itry])>1.0e20) continue; int length = rowLength[rowIndex]; memcpy(thisColumnIndex,column+rowStart[rowIndex],length*sizeof(int)); memcpy(thisElement,elementByRow+rowStart[rowIndex], length*sizeof(double)); b=rhs[itry]; if (itry>1) { // see if we would be better off relaxing int i; // mark columns int length2=length; // for new length int numberReplaced=0; for (i=0;i<length;i++) { int iColumn = thisColumnIndex[i]; back[thisColumnIndex[i]]=i; if (vubRow[iColumn]==-10) { // fixed - take out thisElement[i]=0.0; } } for (i=0;i<length;i++) { int iColumn = thisColumnIndex[i]; int iRow = vubRow[iColumn]; if (iRow>=0&&vub[iRow]==iColumn&&iRow!=rowIndex) { double useRhs=0.0; double vubCoefficient = vubValue[iRow]; double thisCoefficient = thisElement[i]; int replace = 0; // break it out - may be able to do better if (sign[itry]*thisCoefficient>0.0) { // we want valid lower bound on continuous if (effectiveLower[iRow]>-1.0e20&&vubCoefficient>0.0) replace=-1; else if (effectiveUpper[iRow]<1.0e20&&vubCoefficient<0.0) replace=1; } else { // we want valid upper bound on continuous if (effectiveLower[iRow]>-1.0e20&&vubCoefficient<0.0) replace=-1; else if (effectiveUpper[iRow]<1.0e20&&vubCoefficient>0.0) replace=1; } if (replace) { numberReplaced++; if (replace<0) useRhs = effectiveLower[iRow]; else useRhs = effectiveUpper[iRow]; // now replace (just using vubRow==-2) // delete continuous thisElement[i]=0.0; double scale = thisCoefficient/vubCoefficient; // modify rhs b -= scale*useRhs; int start = rowStart[iRow]; int end = start+rowLength[iRow]; int j; for (j=start;j<end;j++) { int iColumn = column[j]; if (vubRow[iColumn]==-2) { double change = scale*elementByRow[j]; int iBack = back[iColumn]; if (iBack<0) { // element does not exist back[iColumn]=length2; thisElement[length2]=-change; thisColumnIndex[length2++]=iColumn; } else { // element does exist thisElement[iBack] -= change; } } } } } } if (numberReplaced) { length=0; for (i=0;i<length2;i++) { int iColumn = thisColumnIndex[i]; back[iColumn]=-1; // un mark if (thisElement[i]) { thisElement[length]=thisElement[i]; thisColumnIndex[length++]=iColumn; } } if (length>maxInKnapsack_) continue; // too long } else { for (i=0;i<length;i++) { int iColumn = thisColumnIndex[i]; back[iColumn]=-1; // un mark } continue; // no good } } if (!deriveAKnapsack(si, cs, krow, rowType[itry], b, complement, xstar, rowIndex, length,thisColumnIndex,thisElement)) { // Reset local data and continue to the next iteration // of the rowIndex-loop for(k=0; k<krow.getNumElements(); k++) { if (complement[krow.getIndices()[k]]){ xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]]; complement[krow.getIndices()[k]]=0; } } krow.setVector(0,NULL,NULL); continue; } #ifdef PRINT_DEBUG { // Get the sense of the row int i; printf("rhs sense %c rhs %g\n",si.getRowSense()[rowIndex], si.getRightHandSide()[rowIndex]); const int * indices = si.getMatrixByRow()->getVector(rowIndex).getIndices(); const double * elements = si.getMatrixByRow()->getVector(rowIndex).getElements(); // for every variable in the constraint for (i=0; i<si.getMatrixByRow()->getVector(rowIndex).getNumElements(); i++){ printf("%d (s=%g) %g, ",indices[i],colsol[indices[i]],elements[i]); } printf("\n"); } #endif // Look for a series of // // different types of minimal covers. // // If a minimal cover is found, // // lift the associated minimal cover inequality, // // uncomplement the vars // // and add it to the cut set. // // After the last type of cover is tried, // // restore xstar values // // Try to generate a violated // // minimal cover greedily from fractional vars // CoinPackedVector cover, remainder; if (findGreedyCover(rowIndex, krow, b, xstar, cover, remainder) == 1){ // Lift cover inequality and add to cut set if (!liftAndUncomplementAndAdd(rowUpper[rowIndex], krow, b, complement, rowIndex, cover, remainder, cs)) { // Reset local data and continue to the next iteration // of the rowIndex-loop // I am not sure this is needed but I am just being careful for(k=0; k<krow.getNumElements(); k++) { if (complement[krow.getIndices()[k]]){ xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]]; complement[krow.getIndices()[k]]=0; } } krow.setVector(0,NULL,NULL); continue; } } // Try to generate a violated // // minimal cover using pseudo John and Ellis logic // // Reset the cover and remainder cover.setVector(0,NULL,NULL); remainder.setVector(0,NULL,NULL); if (findPseudoJohnAndEllisCover(rowIndex, krow, b, xstar, cover, remainder) == 1){ // (Sequence Independent) Lift cover inequality and add to cut set if (!liftAndUncomplementAndAdd(rowUpper[rowIndex], krow, b, complement, rowIndex, cover, remainder, cs)) { // Reset local data and continue to the next iteration // of the rowIndex-loop // I am not sure this is needed but I am just being careful for(k=0; k<krow.getNumElements(); k++) { if (complement[krow.getIndices()[k]]){ xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]]; complement[krow.getIndices()[k]]=0; } } krow.setVector(0,NULL,NULL); continue; } // Skip experiment for now... #if 0 // experimenting here... // (Sequence Dependent) Lift cover inequality and add to cut set seqLiftAndUncomplementAndAdd(nCols, xstar, complement, rowIndex, krow.getNumElements(), b, cover, remainder, cs); #endif } // Try to generate cuts using covers of unsat // // vars on reduced krows with John and Ellis logic // CoinPackedVector atOnes; CoinPackedVector fracCover; // different than cover // reset the remainder remainder.setVector(0,NULL,NULL); if (findJohnAndEllisCover(rowIndex, krow, b, xstar, fracCover, atOnes, remainder) == 1){ // experimenting here... // Sequence Dependent Lifting up on remainders and lifting down on the // atOnes liftUpDownAndUncomplementAndAdd(nCols, xstar, complement, rowIndex, krow.getNumElements(), b, fracCover, atOnes, remainder, cs); } // Try to generate a violated // // minimal cover by considering the // // most violated cover problem // // reset cover and remainder cover.setVector(0,NULL,NULL); remainder.setVector(0,NULL,NULL); // if the size of the krow is "small", // use an exact algorithm to find the most violated (minimal) cover, // else, // use an lp-relaxation to find the most violated (minimal) cover. if(krow.getNumElements()<=15){ if (findExactMostViolatedMinCover(nCols, rowIndex, krow, b, xstar, cover, remainder) == 1){ // Lift cover inequality and add to cut set if (!liftAndUncomplementAndAdd(rowUpper[rowIndex], krow, b, complement, rowIndex, cover, remainder, cs)) { // Reset local data and continue to the next iteration // of the rowIndex-loop // I am not sure this is needed but I am just being careful for(k=0; k<krow.getNumElements(); k++) { if (complement[krow.getIndices()[k]]){ xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]]; complement[krow.getIndices()[k]]=0; } } krow.setVector(0,NULL,NULL); continue; } } } else { if (findLPMostViolatedMinCover(nCols, rowIndex, krow, b, xstar, cover, remainder) == 1){ // Lift cover inequality and add to cut set if (!liftAndUncomplementAndAdd(rowUpper[rowIndex], krow, b, complement, rowIndex, cover, remainder, cs)) { // Reset local data and continue to the next iteration // of the rowIndex-loop // I am not sure this is needed but I am just being careful for(k=0; k<krow.getNumElements(); k++) { if (complement[krow.getIndices()[k]]){ xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]]; complement[krow.getIndices()[k]]=0; } } krow.setVector(0,NULL,NULL); continue; } } } // Reset xstar and complement to their initialized values for the next // go-around int k; if (fabs(b-rowUpper[rowIndex]) > epsilon_) { for(k=0; k<krow.getNumElements(); k++) { if (complement[krow.getIndices()[k]]){ xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]]; complement[krow.getIndices()[k]]=0; } } } krow.setVector(0,NULL,NULL); #ifdef CGL_DEBUG int nnow = cs.sizeRowCuts(); if (nnow>nlast) { const OsiRowCutDebugger * debugger = si.getRowCutDebugger(); if (debugger&&debugger->onOptimalPath(si)) { // check cuts okay int k; for (k=nlast;k<nnow;k++) { OsiRowCut rc=cs.rowCut(k); if(debugger->invalidCut(rc)) { printf("itry %d, rhs %g, length %d\n",itry,rhs[itry],length); int i; for (i=0;i<length;i++) { int iColumn = thisColumnIndex[i]; printf("column %d, coefficient %g, value %g, bounds %g %g\n",iColumn, thisElement[i],colsol[iColumn],colLower[iColumn], colUpper[iColumn]); } if (itry>1) { int length = rowLength[rowIndex]; memcpy(thisColumnIndex,column+rowStart[rowIndex], length*sizeof(int)); memcpy(thisElement,elementByRow+rowStart[rowIndex], length*sizeof(double)); printf("Original row had rhs %g and length %d\n", (itry==2 ? rowLower[rowIndex] :rowUpper[rowIndex]), length); for (i=0;i<length;i++) { int iColumn = thisColumnIndex[i]; printf("column %d, coefficient %g, value %g, bounds %g %g\n",iColumn, thisElement[i],colsol[iColumn],colLower[iColumn], colUpper[iColumn]); } } assert(!debugger->invalidCut(rc)); } } } if (itry>1&&nnow-nlast>kcuts[itry-2]) { printf("itry %d gave %d cuts as against %d for itry %d\n", itry,nnow-nlast,kcuts[itry-2],itry-2); } kcuts[itry]=nnow-nlast; nlast=nnow; } #endif } } // Clean up: free allocated memory if (toCheck != rowsToCheck_) delete[] toCheck; delete[] xstar; delete[] complement; delete [] thisColumnIndex; delete [] thisElement; delete [] back; delete [] vub; delete [] vubRow; delete [] vubValue; delete [] effectiveLower; delete [] effectiveUpper; }

void CglKnapsackCover::setTestedRowIndices (  int  num, const int *  ind )

A method to set which rows should be tested for knapsack covers Definition at line 631 of file CglKnapsackCover.cpp. References numRowsToCheck_. { if (rowsToCheck_) delete[] rowsToCheck_; numRowsToCheck_ = num; if (num > 0) { rowsToCheck_ = new int[num]; CoinCopyN(ind, num, rowsToCheck_); } }

---

Friends And Related Function Documentation

void CglKnapsackCoverUnitTest (  const OsiSolverInterface *  siP, const std::string  mpdDir )  [friend]

A function that tests the methods in the CglKnapsackCover 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 20 of file CglKnapsackCoverTest.cpp. { int i; CoinRelFltEq eq(0.000001); // Test default constructor { CglKnapsackCover kccGenerator; } // Test copy & assignment { CglKnapsackCover rhs; { CglKnapsackCover kccGenerator; CglKnapsackCover cgC(kccGenerator); rhs=kccGenerator; } } // test exactSolveKnapsack { CglKnapsackCover kccg; const int n=7; double c=50; double p[n] = {70,20,39,37,7,5,10}; double w[n] = {31, 10, 20, 19, 4, 3, 6}; double z; int x[n]; int exactsol = kccg.exactSolveKnapsack(n, c, p, w, z, x); assert(exactsol==1); assert (z == 107); assert (x[0]==1); assert (x[1]==0); assert (x[2]==0); assert (x[3]==1); assert (x[4]==0); assert (x[5]==0); assert (x[6]==0); } /* // Testcase /u/rlh/osl2/mps/scOneInt.mps // Model has 3 continous, 2 binary, and 1 general // integer variable. { OsiSolverInterface * siP = baseSiP->clone(); int * complement=NULL; double * xstar=NULL; siP->readMps("../Mps/scOneInt","mps"); CglKnapsackCover kccg; int nCols=siP->getNumCols(); // Test the siP methods for detecting // variable type int numCont=0, numBinary=0, numIntNonBinary=0, numInt=0; for (int thisCol=0; thisCol<nCols; thisCol++) { if ( siP->isContinuous(thisCol) ) numCont++; if ( siP->isBinary(thisCol) ) numBinary++; if ( siP->isIntegerNonBinary(thisCol) ) numIntNonBinary++; if ( siP->isInteger(thisCol) ) numInt++; } assert(numCont==3); assert(numBinary==2); assert(numIntNonBinary==1); assert(numInt==3); // Test initializeCutGenerator siP->initialSolve(); assert(xstar !=NULL); for (i=0; i<nCols; i++){ assert(complement[i]==0); } int nRows=siP->getNumRows(); for (i=0; i<nRows; i++){ int vectorsize = siP->getMatrixByRow()->vectorSize(i); assert(vectorsize==2); } kccg.cleanUpCutGenerator(complement,xstar); delete siP; } */ // Testcase /u/rlh/osl2/mps/tp3.mps // Models has 3 cols, 3 rows // Row 0 yields a knapsack, others do not. { // setup OsiSolverInterface * siP = baseSiP->clone(); std::string fn(mpsDir+"tp3"); siP->readMps(fn.c_str(),"mps"); // All integer variables should be binary. // Assert that this is true. for ( i = 0; i < siP->getNumCols(); i++ ) if ( siP->isInteger(i) ) assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i)); OsiCuts cs; CoinPackedVector krow; double b=0; int nCols=siP->getNumCols(); int * complement=new int [nCols]; double * xstar=new double [nCols]; CglKnapsackCover kccg; // solve LP relaxation // a "must" before calling initialization siP->initialSolve(); assert( eq(siP->getObjValue(), 97.185) ); double mycs[] = {.627, .667558333333, .038}; siP->setColSolution(mycs); const double *colsol = siP->getColSolution(); int k; for (k=0; k<nCols; k++){ xstar[k]=colsol[k]; complement[k]=0; } // test deriveAKnapsack int rind = ( siP->getRowSense()[0] == 'N' ) ? 1 : 0; int deriveaknap = kccg.deriveAKnapsack(*siP, cs, krow,b,complement,xstar,rind,siP->getMatrixByRow()->getVector(rind)); assert(deriveaknap ==1); assert(complement[0]==0); assert(complement[1]==1); assert(complement[2]==1); int inx[3] = {0,1,2}; double el[3] = {161, 120, 68}; CoinPackedVector r; r.setVector(3,inx,el); assert (krow == r); assert (b == 183.0); // test findGreedyCover CoinPackedVector cover,remainder; #if 0 int findgreedy = kccg.findGreedyCover( 0, krow, b, xstar, cover, remainder ); assert( findgreedy == 1 ); int coveri = cover.getNumElements(); assert( cover.getNumElements() == 2); coveri = cover.getIndices()[0]; assert( cover.getIndices()[0] == 0); assert( cover.getIndices()[1] == 1); assert( cover.getElements()[0] == 161.0); assert( cover.getElements()[1] == 120.0); assert( remainder.getNumElements() == 1); assert( remainder.getIndices()[0] == 2); assert( remainder.getElements()[0] == 68.0); // test liftCoverCut CoinPackedVector cut; double * rowupper = ekk_rowupper(model); double cutRhs = cover.getNumElements() - 1.0; kccg.liftCoverCut(b, krow.getNumElements(), cover, remainder, cut); assert ( cut.getNumElements() == 3 ); assert ( cut.getIndices()[0] == 0 ); assert ( cut.getIndices()[1] == 1 ); assert ( cut.getIndices()[2] == 2 ); assert( cut.getElements()[0] == 1 ); assert( cut.getElements()[1] == 1 ); assert( eq(cut.getElements()[2], 0.087719) ); // test liftAndUncomplementAndAdd OsiCuts cuts; kccg.liftAndUncomplementAndAdd(*siP.getRowUpper()[0],krow,b,complement,0, cover,remainder,cuts); int sizerowcuts = cuts.sizeRowCuts(); assert ( sizerowcuts== 1 ); OsiRowCut testRowCut = cuts.rowCut(0); CoinPackedVector testRowPV = testRowCut.row(); OsiRowCut sampleRowCut; const int sampleSize = 3; int sampleCols[sampleSize]={0,1,2}; double sampleElems[sampleSize]={1.0,-1.0,-0.087719}; sampleRowCut.setRow(sampleSize,sampleCols,sampleElems); sampleRowCut.setLb(-DBL_MAX); sampleRowCut.setUb(-0.087719); bool equiv = testRowPV.equivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05) ); assert ( equiv ); #endif // test find PseudoJohnAndEllisCover cover.setVector(0,NULL, NULL); remainder.setVector(0,NULL,NULL); rind = ( siP->getRowSense()[0] == 'N' ) ? 1 : 0; int findPJE = kccg.findPseudoJohnAndEllisCover( rind, krow, b, xstar, cover, remainder ); assert( findPJE == 1 ); assert ( cover.getIndices()[0] == 0 ); assert ( cover.getIndices()[1] == 2 ); assert ( cover.getElements()[0] == 161 ); assert ( cover.getElements()[1] == 68 ); assert ( remainder.getIndices()[0] == 1 ); assert ( remainder.getElements()[0] == 120 ); OsiCuts cuts; kccg.liftAndUncomplementAndAdd((*siP).getRowUpper()[rind],krow,b, complement, rind, cover,remainder,cuts); assert (cuts.sizeRowCuts() == 1 ); OsiRowCut testRowCut = cuts.rowCut(0); CoinPackedVector testRowPV = testRowCut.row(); const int sampleSize = 3; int sampleCols[sampleSize]={0,1,2}; double sampleElems[sampleSize]={1.0, -1.0, -1.0}; OsiRowCut sampleRowCut; sampleRowCut.setRow(sampleSize,sampleCols,sampleElems); sampleRowCut.setLb(-DBL_MAX); sampleRowCut.setUb(-1.0); // test for 'close enough' assert( testRowPV.isEquivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05) ) ); // Reset complement & test next row for (i=0; i<nCols; i++){ complement[i]=0; } rind++; deriveaknap = kccg.deriveAKnapsack(*siP,cuts,krow,b,complement,xstar,rind,siP->getMatrixByRow()->getVector(rind)); assert(deriveaknap==0); // Reset complement & test next row for (i=0; i<nCols; i++){ complement[i]=0; } deriveaknap = kccg.deriveAKnapsack(*siP,cuts,krow,b,complement,xstar,2, siP->getMatrixByRow()->getVector(2)); assert(deriveaknap == 0); // Clean up delete [] complement; delete [] xstar; delete siP; } #if 0 // Testcase /u/rlh/osl2/mps/tp4.mps // Models has 6 cols, 1 knapsack row and // 3 rows explicily bounding variables // Row 0 yields a knapsack cover cut // using findGreedyCover which moves the // LP objective function value. { // Setup EKKContext * env=ekk_initializeContext(); EKKModel * model = ekk_newModel(env,""); OsiSolverInterface si(model); ekk_importModel(model, "tp4.mps"); CglKnapsackCover kccg; kccg.ekk_validateIntType(si); // Solve the LP relaxation of the model and // print out ofv for sake of comparison ekk_allSlackBasis(model); ekk_crash(model,1); ekk_primalSimplex(model,1); double lpRelaxBefore=ekk_getRobjvalue(model); #ifdef CGL_DEBUG printf("\n\nOrig LP min=%f\n",lpRelaxBefore); #endif // Determine if lp sol is ip optimal // Note: no ekk_function to do this int nCols=ekk_getInumcols(model); double * optLpSol = ekk_colsol(model); int ipOpt = 1; i=0; while (i++<nCols && ipOpt){ if(optLpSol[i] < 1.0-1.0e-08 && optLpSol[i]> 1.0e-08) ipOpt = 0; } if (ipOpt){ #ifdef CGL_DEBUG printf("Lp solution is within ip optimality tolerance\n"); #endif } else { OsiSolverInterface iModel(model); OsiCuts cuts; // Test generateCuts method kccg.generateCuts(iModel,cuts); OsiSolverInterface::ApplyCutsReturnCode rc = iModel.applyCuts(cuts); ekk_mergeBlocks(model,1); ekk_dualSimplex(model); double lpRelaxAfter=ekk_getRobjvalue(model); #ifdef CGL_DEBUG printf("\n\nFinal LP min=%f\n",lpRelaxAfter); #endif assert( lpRelaxBefore < lpRelaxAfter ); // This may need to be updated as other // minimal cover finders are added assert( cuts.sizeRowCuts() == 1 ); OsiRowCut testRowCut = cuts.rowCut(0); CoinPackedVector testRowPV = testRowCut.row(); OsiRowCut sampleRowCut; const int sampleSize = 6; int sampleCols[sampleSize]={0,1,2,3,4,5}; double sampleElems[sampleSize]={1.0,1.0,1.0,1.0,0.5, 2.0}; sampleRowCut.setRow(sampleSize,sampleCols,sampleElems); sampleRowCut.setLb(-DBL_MAX); sampleRowCut.setUb(3.0); bool equiv = testRowPV.equivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05) ); assert( testRowPV.equivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05) ) ); } // Exit out of OSL ekk_deleteModel(model); ekk_endContext(env); } #endif // Testcase /u/rlh/osl2/mps/tp5.mps // Models has 6 cols, 1 knapsack row and // 3 rows explicily bounding variables // Row 0 yields a knapsack cover cut // using findGreedyCover which moves the // LP objective function value. { // Setup OsiSolverInterface * siP = baseSiP->clone(); std::string fn(mpsDir+"tp5"); siP->readMps(fn.c_str(),"mps"); // All integer variables should be binary. // Assert that this is true. for ( i = 0; i < siP->getNumCols(); i++ ) if ( siP->isInteger(i) ) assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i)); CglKnapsackCover kccg; // Solve the LP relaxation of the model and // print out ofv for sake of comparison siP->initialSolve(); double lpRelaxBefore=siP->getObjValue(); assert( eq(lpRelaxBefore, -51.66666666667) ); double mycs[] = {.8999999999, .899999999999, .89999999999, 1.110223e-16, .5166666666667, 0}; siP->setColSolution(mycs); #ifdef CGL_DEBUG printf("\n\nOrig LP min=%f\n",lpRelaxBefore); #endif // Determine if lp sol is 0/1 optimal int nCols=siP->getNumCols(); const double * optLpSol = siP->getColSolution(); bool ipOpt = true; i=0; while (i++<nCols && ipOpt){ if(optLpSol[i] > kccg.epsilon_ && optLpSol[i] < kccg.onetol_) ipOpt = false; } if (ipOpt){ #ifdef CGL_DEBUG printf("Lp solution is within ip optimality tolerance\n"); #endif } else { // set up OsiCuts cuts; CoinPackedVector krow; double b=0.0; int * complement=new int[nCols]; double * xstar=new double[nCols]; // initialize cut generator const double *colsol = siP->getColSolution(); for (i=0; i<nCols; i++){ xstar[i]=colsol[i]; complement[i]=0; } int row = ( siP->getRowSense()[0] == 'N' ) ? 1 : 0; // transform row into canonical knapsack form if (kccg.deriveAKnapsack(*siP, cuts, krow, b, complement, xstar, row,siP->getMatrixByRow()->getVector(row))){ CoinPackedVector cover, remainder; // apply greedy logic to detect violated minimal cover inequalities if (kccg.findGreedyCover(row, krow, b, xstar, cover, remainder) == 1){ // lift, uncomplements, and add cut to cut set kccg.liftAndUncomplementAndAdd((*siP).getRowUpper()[row],krow, b, complement, row, cover, remainder, cuts); } // reset optimal column solution (xstar) information in OSL const double * rowupper = siP->getRowUpper(); int k; if (fabs(b-rowupper[row]) > 1.0e-05) { for(k=0; k<krow.getNumElements(); k++) { if (complement[krow.getIndices()[k]]){ xstar[krow.getIndices()[k]]= 1.0-xstar[krow.getIndices()[k]]; complement[krow.getIndices()[k]]=0; } } } // clean up delete [] complement; delete [] xstar; } // apply the cuts OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts); siP->resolve(); double lpRelaxAfter=siP->getObjValue(); assert( eq(lpRelaxAfter, -30.0) ); #ifdef CGL_DEBUG printf("\n\nFinal LP min=%f\n",lpRelaxAfter); #endif // test that expected cut was detected assert( lpRelaxBefore < lpRelaxAfter ); assert( cuts.sizeRowCuts() == 1 ); OsiRowCut testRowCut = cuts.rowCut(0); CoinPackedVector testRowPV = testRowCut.row(); OsiRowCut sampleRowCut; const int sampleSize = 6; int sampleCols[sampleSize]={0,1,2,3,4,5}; double sampleElems[sampleSize]={1.0,1.0,1.0,0.25,1.0,2.0}; sampleRowCut.setRow(sampleSize,sampleCols,sampleElems); sampleRowCut.setLb(-DBL_MAX); sampleRowCut.setUb(3.0); assert(testRowPV.isEquivalent(sampleRowCut.row(),CoinRelFltEq(1.0e-05))); } delete siP; } // Testcase /u/rlh/osl2/mps/p0033 // Miplib3 problem p0033 // Test that no cuts chop off the optimal solution { // Setup OsiSolverInterface * siP = baseSiP->clone(); std::string fn(mpsDir+"p0033"); siP->readMps(fn.c_str(),"mps"); // All integer variables should be binary. // Assert that this is true. for ( i = 0; i < siP->getNumCols(); i++ ) if ( siP->isInteger(i) ) assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i)); int nCols=siP->getNumCols(); CglKnapsackCover kccg; // Solve the LP relaxation of the model and // print out ofv for sake of comparison siP->initialSolve(); double lpRelaxBefore=siP->getObjValue(); assert( eq(lpRelaxBefore, 2520.5717391304347) ); double mycs[] = {0, 1, 0, 0, -2.0837010502455788e-19, 1, 0, 0, 1, 0.021739130434782594, 0.35652173913043478, -6.7220534694101275e-18, 5.3125906451789717e-18, 1, 0, 1.9298798670241979e-17, 0, 0, 0, 7.8875708048320448e-18, 0.5, 0, 0.85999999999999999, 1, 1, 0.57999999999999996, 1, 0, 1, 0, 0.25, 0, 0.67500000000000004}; siP->setColSolution(mycs); #ifdef CGL_DEBUG printf("\n\nOrig LP min=%f\n",lpRelaxBefore); #endif OsiCuts cuts; // Test generateCuts method kccg.generateCuts(*siP,cuts); OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts); siP->resolve(); double lpRelaxAfter=siP->getObjValue(); assert( eq(lpRelaxAfter, 2829.0597826086955) ); #ifdef CGL_DEBUG printf("\n\nOrig LP min=%f\n",lpRelaxBefore); printf("\n\nFinal LP min=%f\n",lpRelaxAfter); #endif assert( lpRelaxBefore < lpRelaxAfter ); // the CoinPackedVector p0033 is the optimal // IP solution to the miplib problem p0033 int objIndices[14] = { 0, 6, 7, 9, 13, 17, 18, 22, 24, 25, 26, 27, 28, 29 }; CoinPackedVector p0033(14,objIndices,1.0); // Sanity check const double * objective=siP->getObjCoefficients(); double ofv =0 ; int r; for (r=0; r<nCols; r++){ ofv=ofv + p0033[r]*objective[r]; } CoinRelFltEq eq; assert( eq(ofv,3089.0) ); int nRowCuts = cuts.sizeRowCuts(); OsiRowCut rcut; CoinPackedVector rpv; for (i=0; i<nRowCuts; i++){ rcut = cuts.rowCut(i); rpv = rcut.row(); double p0033Sum = (rpv*p0033).sum(); assert (p0033Sum <= rcut.ub() ); } delete siP; } // if a debug file is there then look at it { FILE * fp = fopen("knapsack.debug","r"); if (fp) { int ncol,nel; double up; fscanf(fp,"%d %d %lg",&ncol,&nel,&up); printf("%d columns, %d elements, upper %g\n",ncol,nel,up); double * sol1 = new double[nel]; double * el1 = new double[nel]; int * col1 = new int[nel]; int * start = new int[ncol+1]; memset(start,0,ncol*sizeof(int)); int * row = new int[nel]; int i; for (i=0;i<nel;i++) { fscanf(fp,"%d %lg %lg",col1+i,el1+i,sol1+i); printf("[%d, e=%g, v=%g] ",col1[i],el1[i],sol1[i]); start[col1[i]]=1; row[i]=0; } printf("\n"); // Setup OsiSolverInterface * siP = baseSiP->clone(); double lo=-1.0e30; double * upper = new double[ncol]; start[ncol]=nel; int last=0; for (i=0;i<ncol;i++) { upper[i]=1.0; int marked=start[i]; start[i]=last; if (marked) last++; } siP->loadProblem(ncol,1,start,row,el1,NULL,upper,NULL,&lo,&up); // use upper for solution memset(upper,0,ncol*sizeof(double)); for (i=0;i<nel;i++) { int icol=col1[i]; upper[icol]=sol1[i]; siP->setInteger(icol); } siP->setColSolution(upper); delete [] sol1; delete [] el1; delete [] col1; delete [] start; delete [] row; delete [] upper; CglKnapsackCover kccg; OsiCuts cuts; // Test generateCuts method kccg.generateCuts(*siP,cuts); // print out and compare to known cuts int numberCuts = cuts.sizeRowCuts(); if (numberCuts) { for (i=0;i<numberCuts;i++) { OsiRowCut * thisCut = cuts.rowCutPtr(i); int n=thisCut->row().getNumElements(); printf("Cut %d has %d entries, rhs %g %g =>",i,n,thisCut->lb(), thisCut->ub()); int j; const int * index = thisCut->row().getIndices(); const double * element = thisCut->row().getElements(); for (j=0;j<n;j++) { printf(" (%d,%g)",index[j],element[j]); } printf("\n"); } } fclose(fp); } } // Testcase /u/rlh/osl2/mps/p0201 // Miplib3 problem p0282 // Test that no cuts chop off the optimal ip solution { // Setup OsiSolverInterface * siP = baseSiP->clone(); std::string fn(mpsDir+"p0201"); siP->readMps(fn.c_str(),"mps"); // All integer variables should be binary. // Assert that this is true. for ( i = 0; i < siP->getNumCols(); i++ ) if ( siP->isInteger(i) ) assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i)); const int nCols=siP->getNumCols(); CglKnapsackCover kccg; // Solve the LP relaxation of the model and // print out ofv for sake of comparisn siP->initialSolve(); double lpRelaxBefore=siP->getObjValue(); assert( eq(lpRelaxBefore, 6875.) ); double mycs[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0.5, 0, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}; siP->setColSolution(mycs); #ifdef CGL_DEBUG printf("\n\nOrig LP min=%f\n",lpRelaxBefore); #endif OsiCuts cuts; // Test generateCuts method kccg.generateCuts(*siP,cuts); OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts); siP->resolve(); double lpRelaxAfter=siP->getObjValue(); assert( eq(lpRelaxAfter, 7125) ); #ifdef CGL_DEBUG printf("\n\nOrig LP min=%f\n",lpRelaxBefore); printf("\n\nFinal LP min=%f\n",lpRelaxAfter); #endif assert( lpRelaxBefore < lpRelaxAfter ); // Optimal IP solution to p0201 int objIndices[22] = { 8, 10, 21, 38, 39, 56, 60, 74, 79, 92, 94, 110, 111, 128, 132, 146, 151,164, 166, 182,183, 200 }; CoinPackedVector p0201(22,objIndices,1.0); // Sanity check const double * objective=siP->getObjCoefficients(); double ofv =0 ; int r; for (r=0; r<nCols; r++){ ofv=ofv + p0201[r]*objective[r]; } CoinRelFltEq eq; assert( eq(ofv,7615.0) ); //printf("p0201 optimal ofv = %g\n",ofv); int nRowCuts = cuts.sizeRowCuts(); OsiRowCut rcut; CoinPackedVector rpv; for (i=0; i<nRowCuts; i++){ rcut = cuts.rowCut(i); rpv = rcut.row(); double p0201Sum = (rpv*p0201).sum(); assert (p0201Sum <= rcut.ub() ); } delete siP; } // see if I get the same covers that N&W get { OsiSolverInterface * siP=baseSiP->clone(); std::string fn(mpsDir+"nw460"); siP->readMps(fn.c_str(),"mps"); // All integer variables should be binary. // Assert that this is true. for ( i = 0; i < siP->getNumCols(); i++ ) if ( siP->isInteger(i) ) assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i)); CglKnapsackCover kccg; // Solve the LP relaxation of the model and // print out ofv for sake of comparison siP->initialSolve(); double lpRelaxBefore=siP->getObjValue(); assert( eq(lpRelaxBefore, -225.68951787852194) ); double mycs[] = {0.7099213482046447, 0, 0.34185802225477174, 1, 1, 0, 1, 1, 0}; siP->setColSolution(mycs); OsiCuts cuts; // Test generateCuts method kccg.generateCuts(*siP,cuts); OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts); siP->resolve(); double lpRelaxAfter=siP->getObjValue(); assert( eq(lpRelaxAfter, -176) ); #ifdef CGL_DEBUG printf("\n\nOrig LP min=%f\n",lpRelaxBefore); printf("\n\nFinal LP min=%f\n",lpRelaxAfter); #endif #ifdef MJS assert( lpRelaxBefore < lpRelaxAfter ); #endif int nRowCuts = cuts.sizeRowCuts(); OsiRowCut rcut; CoinPackedVector rpv; for (i=0; i<nRowCuts; i++){ rcut = cuts.rowCut(i); rpv = rcut.row(); int j; printf("Row cut number %i has rhs = %g\n",i,rcut.ub()); for (j=0; j<rpv.getNumElements(); j++){ printf("index %i, element %g\n", rpv.getIndices()[j], rpv.getElements()[j]); } printf("\n"); } delete siP; } // Debugging: try "exmip1.mps" { // Setup OsiSolverInterface * siP = baseSiP->clone(); std::string fn(mpsDir+"exmip1"); siP->readMps(fn.c_str(),"mps"); // All integer variables should be binary. // Assert that this is true. for ( i = 0; i < siP->getNumCols(); i++ ) if ( siP->isInteger(i) ) assert(siP->getColUpper()[i]==1.0 && siP->isBinary(i)); CglKnapsackCover kccg; // Solve the LP relaxation of the model and // print out ofv for sake of comparison siP->initialSolve(); double lpRelaxBefore=siP->getObjValue(); assert( eq(lpRelaxBefore, 3.2368421052631575) ); double mycs[] = {2.5, 0, 0, 0.6428571428571429, 0.5, 4, 0, 0.26315789473684253}; siP->setColSolution(mycs); // Test generateCuts method OsiCuts cuts; kccg.generateCuts(*siP,cuts); OsiSolverInterface::ApplyCutsReturnCode rc = siP->applyCuts(cuts); siP->resolve(); double lpRelaxAfter=siP->getObjValue(); assert( eq(lpRelaxAfter, 3.2368421052631575) ); #ifdef CGL_DEBUG printf("\n\nOrig LP min=%f\n",lpRelaxBefore); printf("\n\nFinal LP min=%f\n",lpRelaxAfter); #endif assert( lpRelaxBefore <= lpRelaxAfter ); delete siP; } #ifdef CGL_DEBUG // See what findLPMostViolatedMinCover for knapsack with 2 elements does { int nCols = 2; int row = 1; CoinPackedVector krow; double e[2] = {5,10}; int ii[2] = {0,1}; krow.setVector(nCols,ii,e); double b=11; double xstar[2] = {.2,.9}; CoinPackedVector cover; CoinPackedVector remainder; CglKnapsackCover kccg; kccg.findLPMostViolatedMinCover(nCols, row, krow, b, xstar, cover, remainder); printf("num in cover = %i\n",cover.getNumElements()); int j; for (j=0; j<cover.getNumElements(); j++){ printf(" index %i element % g\n", cover.getIndices()[j], cover.getElements()[j]); } } #endif #ifdef CGL_DEBUG // see what findLPMostViolatedMinCover does { int nCols = 5; int row = 1; CoinPackedVector krow; double e[5] = {1,1,1,1,10}; int ii[5] = {0,1,2,3,4}; krow.setVector(nCols,ii,e); double b=11; double xstar[5] = {.9,.9,1,1,.1}; CoinPackedVector cover; CoinPackedVector remainder; CglKnapsackCover kccg; kccg.findLPMostViolatedMinCover(nCols, row, krow, b, xstar, cover, remainder); printf("num in cover = %i\n",cover.getNumElements()); int j; for (j=0; j<cover.getNumElements(); j++){ printf(" index %i element % g\n", cover.getIndices()[j], cover.getElements()[j]); } } #endif }

---

Member Data Documentation

int CglKnapsackCover::numRowsToCheck_ [private]

which rows to look at. If specified, only these rows will be considered for generating knapsack covers. Otherwise all rows will be tried Definition at line 228 of file CglKnapsackCover.hpp. Referenced by CglKnapsackCover(), generateCuts(), operator=(), and setTestedRowIndices().

---

The documentation for this class was generated from the following files:

• CglKnapsackCover.hpp
• CglKnapsackCover.cpp

---