[Cgl] exact knapsack solver bound

[Matthew Galati]

Do CGL cover cuts ensure that all profits to the lifting subproblem using
CGL:exactSolveKnapsack are integral? If not, there might be a bug here.

The original Horowitz-Sahni paper (HS) assumes integral coefficients, which
allows one to floor the fractional contribution from the last item. For
general profit coefficients, I don't think that is a safe bound. Correct?

double u = pSemiSum + floor((chat - wSemiSum)*p[ii]/w[ii]);

Likely this is returning suboptimal KP solutions (lifting coefficients) and
leading to weaker cuts (?).

I am not basing this off of any example I have - just off of looking at the
logic of the HS code.

Cheers,
Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cgl/attachments/20130708/667eb94d/attachment.html>