<div dir="ltr">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. <div><br></div><div>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&#39;t think that is a safe bound. Correct?</div>
<div><br></div><div><span class="" style="color:rgb(68,85,136);font-weight:bold;font-family:monospace;font-size:11px">double</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px"> u </span><span class="" style="font-weight:bold;color:rgb(0,0,0);font-family:monospace;font-size:11px">=</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px"> pSemiSum </span><span class="" style="font-weight:bold;color:rgb(0,0,0);font-family:monospace;font-size:11px">+</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px"> floor</span><span class="" style="color:rgb(0,0,0);font-family:monospace;font-size:11px">((</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px">chat </span><span class="" style="font-weight:bold;color:rgb(0,0,0);font-family:monospace;font-size:11px">-</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px"> wSemiSum</span><span class="" style="color:rgb(0,0,0);font-family:monospace;font-size:11px">)</span><span class="" style="font-weight:bold;color:rgb(0,0,0);font-family:monospace;font-size:11px">*</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px">p</span><span class="" style="color:rgb(0,0,0);font-family:monospace;font-size:11px">[</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px">ii</span><span class="" style="color:rgb(0,0,0);font-family:monospace;font-size:11px">]</span><span class="" style="font-weight:bold;color:rgb(0,0,0);font-family:monospace;font-size:11px">/</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px">w</span><span class="" style="color:rgb(0,0,0);font-family:monospace;font-size:11px">[</span><span style="color:rgb(0,0,0);font-family:monospace;font-size:11px">ii</span><span class="" style="color:rgb(0,0,0);font-family:monospace;font-size:11px">]);</span></div>
<div><br></div><div>Likely this is returning suboptimal KP solutions (lifting coefficients) and leading to weaker cuts (?).<br><div><br></div><div>I am not basing this off of any example I have - just off of looking at the logic of the HS code.</div>
</div><div><br></div><div style>Cheers,</div><div style>Matt</div><div style><br></div><div style><br></div></div>