<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Exchange Server">
<!-- converted from rtf -->
<style><!-- .EmailQuote { margin-left: 1pt; padding-left: 4pt; border-left: #800000 2px solid; } --></style>
</head>
<body>
<font face="Calibri, sans-serif" size="2">
<div>Dear CGL’ers:</div>
<div> </div>
<div>I’ve been working with Cgl in the context of our PICO parallel MIP solver, and ran into an issue and/or bug that I want to raise with the Cgl development team.</div>
<div> </div>
<div>The problem context is “pp08” from either miplib3 or miplib2003; I forget exactly which at the moment. If I solve the root LP relaxation and then attempt to find CglGomory cuts, several are found and correctly applied. However, if I modify the objective
coefficients only – we’re working with feasibility pump-like heuristics – and solve pp08, CglGomory isn’t able to identify any cuts. For us, this is a major issue because we are using Gomory cuts to escape local minima in our heuristic, and they should (to
a first order, ignoring numerical issues) always exist. It also happens on roughly 1/3 of the miplib2003 instances, which is preventing us from completing a reasonable set of experimental tests.</div>
<div> </div>
<div>I have replicated this behavior with a pure Clp/Cgl test driver, so I’m certain it isn’t related to the PICO use of Cgl/Clp. I can provide the Clp-based test driver and problem instances if anyone is interested.</div>
<div> </div>
<div>Digging into the CglGomory.cpp cut generation code, it appears that cuts are being found, but then deemed “unworthy” and then thrown away. The relevant piece of logic is:</div>
<div> </div>
<div> if (number<limit||!numberNonInteger) </div>
<div> {</div>
<div> bool goodCut=true;</div>
<div> bounds[1]=rhs;</div>
<div> if (number>50&&numberNonInteger)</div>
<div> {</div>
<div> bounds[1] = bounds[1]+1.0e-6+1.0e-8*fabs(rhs); // weaken</div>
<div> }</div>
<div> if (number>5&&numberNonInteger&&relaxation>1.0e-20) </div>
<div> {</div>
<div> relaxation *= fabs(rhs);</div>
<div> //printf("relaxing rhs by %g\n",CoinMin(relaxation,1.0e-3));</div>
<div> bounds[1] = bounds[1]+CoinMin(relaxation,1.0e-3); // weaken</div>
<div>#if 1</div>
<div> //bounds[1] = bounds[1]+relaxation*fabs(rhs); // weaken</div>
<div> // may be better to thow away</div>
<div> if (relaxation>1.0e6)</div>
<div> {</div>
<div> goodCut=false;</div>
<div> }</div>
<div>#endif</div>
<div> }</div>
<div> </div>
<div> </div>
<div>The generated cuts fall prey to the “goodCut=false” assignment, which is due to the condition number (the variable “relaxation”) exceeding the indicated threshold. Typically, I am seeing cuts with number=6 or number=7, with numberNonInteger>=1, and a large
relaxation value. </div>
<div> </div>
<div>After some internal discussion, we realize we don’t understand the logic behind this culling procedure. For example, we’d like some insight into:</div>
<ol style="margin-top: 0pt; margin-bottom: 0pt; margin-left: 36pt; ">
<li>The intuition behind scaling the relaxation by the fabs(rhs) factor</li><li>Why the relaxation values coming into this fragment are so large (e.g., on the order of 10^50 for the modified problem), when in CPLEX they are quite small (on the order of 100-10000 for the same problem).</li><li>The intuition behind triggering of culling logic only when “numberNonInteger” is > 0.</li></ol>
<div> </div>
<div>The good news is that by commenting out the “goodCut=false” line, we run fine. But that isn’t the right answer either. Perhaps a user-specified option might be, e.g., “generate-without-culling=true”. </div>
<div> </div>
<div>I am also wondering if updating this logic might improve the proving-optimality phase of many Cgl-based MIP solvers, including PICO. We have observed that it seems to under-cut relative to CPLEX.</div>
<div> </div>
<div>There are many more details, but the intent is to start a discussion. Any help is greatly appreciated on our end!</div>
<div> </div>
<div>Jean-Paul</div>
<div> </div>
<div>--</div>
<div> </div>
<div><font face="Arial, sans-serif" size="2">Dr. Jean-Paul Watson</font></div>
<div><font face="Arial, sans-serif" size="2">Discrete Math and Complex Systems Department</font></div>
<div><font face="Arial, sans-serif" size="2">Sandia National Laboratories</font></div>
<div><font face="Arial, sans-serif" size="2">P.O. Box 5800, MS 1318</font></div>
<div><font face="Arial, sans-serif" size="2">Albuquerque, NM 87185-1318 USA</font></div>
<div><font face="Arial, sans-serif" size="2">(505) 845-8887</font></div>
<div><font face="Arial, sans-serif" size="2">jwatson@sandia.gov</font></div>
<div> </div>
<div> </div>
<div> </div>
</font>
</body>
</html>