<br><font size=2 face="sans-serif">There was an accuracy issue with Gomory
cuts. It is very likely that the correction was over drastic.</font>
<br>
<br><font size=2 face="sans-serif">If you give me some code, I can try
and correct the correction.</font>
<br>
<br><font size=2 face="sans-serif">John Forrest</font>
<br>
<br>
<br>
<table width=100%>
<tr>
<td><img src=cid:_1_236707E823670400005094848525756A>
<td width=100%>
<table width=100%>
<tr valign=top>
<td width=100%><font size=2 face="sans-serif"><b>[Cgl] Issue/potential
bug with CglGomory cuts</b></font></table>
<br>
<table width=100%>
<tr>
<td><font size=2 color=#e26200 face="sans-serif"><b>Watson, Jean-paul </b></font>
<td><font size=2 color=#8f8f8f face="sans-serif">to:</font>
<td><font size=2 face="sans-serif">Cgl@list.coin-or.org</font>
<td>
<div align=right><font size=1 face="sans-serif">02/26/2009 10:37 PM</font></div></table>
<br>
<table width=100%>
<tr>
<td>
<table width=100%>
<tr>
<td><font size=2 color=#8f8f8f face="sans-serif">Sent by:</font>
<td width=100%><font size=2 color=#e26200 face="sans-serif"><b>cgl-bounces@list.coin-or.org</b></font>
<tr>
<td><font size=1 color=#8f8f8f face="sans-serif">Cc:</font>
<td><font size=1 face="sans-serif">"Carr, Robert D", "Hart,
William E"</font></table>
<br>
<td>
<div align=right></div></table>
<br></table>
<br>
<br>
<hr>
<br>
<br>
<br><font size=2 face="Calibri">Dear CGL’ers:</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">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.</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">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.</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">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.</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">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:</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">
if (number<limit||!numberNonInteger) </font>
<br><font size=2 face="Calibri">
{</font>
<br><font size=2 face="Calibri">
bool goodCut=true;</font>
<br><font size=2 face="Calibri">
bounds[1]=rhs;</font>
<br><font size=2 face="Calibri">
if (number>50&&numberNonInteger)</font>
<br><font size=2 face="Calibri">
{</font>
<br><font size=2 face="Calibri">
bounds[1] = bounds[1]+1.0e-6+1.0e-8*fabs(rhs);
// weaken</font>
<br><font size=2 face="Calibri">
}</font>
<br><font size=2 face="Calibri">
if (number>5&&numberNonInteger&&relaxation>1.0e-20)
</font>
<br><font size=2 face="Calibri">
{</font>
<br><font size=2 face="Calibri">
relaxation *= fabs(rhs);</font>
<br><font size=2 face="Calibri">
//printf("relaxing
rhs by %g\n",CoinMin(relaxation,1.0e-3));</font>
<br><font size=2 face="Calibri">
bounds[1] = bounds[1]+CoinMin(relaxation,1.0e-3);
// weaken</font>
<br><font size=2 face="Calibri">#if 1</font>
<br><font size=2 face="Calibri">
//bounds[1] = bounds[1]+relaxation*fabs(rhs);
// weaken</font>
<br><font size=2 face="Calibri">
// may be better to thow
away</font>
<br><font size=2 face="Calibri">
if (relaxation>1.0e6)</font>
<br><font size=2 face="Calibri">
{</font>
<br><font size=2 face="Calibri">
goodCut=false;</font>
<br><font size=2 face="Calibri">
}</font>
<br><font size=2 face="Calibri">#endif</font>
<br><font size=2 face="Calibri">
}</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">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.
</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">After some internal discussion, we realize
we don’t understand the logic behind this culling procedure. For example,
we’d like some insight into:</font>
<br><font size=2 face="sans-serif">1. </font><font size=2 face="Calibri">The
intuition behind scaling the relaxation by the fabs(rhs) factor</font>
<br><font size=2 face="sans-serif">2. </font><font size=2 face="Calibri">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).</font>
<br><font size=2 face="sans-serif">3. </font><font size=2 face="Calibri">The
intuition behind triggering of culling logic only when “numberNonInteger”
is > 0.</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">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”.
</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">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.</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">There are many more details, but the intent
is to start a discussion. Any help is greatly appreciated on our end!</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">Jean-Paul</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri">--</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Arial">Dr. Jean-Paul Watson</font>
<br><font size=2 face="Arial">Discrete Math and Complex Systems Department</font>
<br><font size=2 face="Arial">Sandia National Laboratories</font>
<br><font size=2 face="Arial">P.O. Box 5800, MS 1318</font>
<br><font size=2 face="Arial">Albuquerque, NM 87185-1318 USA</font>
<br><font size=2 face="Arial">(505) 845-8887</font>
<br><font size=2 face="Arial">jwatson@sandia.gov</font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri"> </font>
<br><font size=2 face="Calibri"> </font><tt><font size=2>_______________________________________________<br>
Cgl mailing list<br>
Cgl@list.coin-or.org<br>
http://list.coin-or.org/mailman/listinfo/cgl<br>
</font></tt>
<br>