<br><font size=2 face="sans-serif">Jean-Paul,</font>
<br>
<br><font size=2 face="sans-serif">Firstly, I would suggest you upgrade
your version of Cgl from 0.52 to 0.53. The goodCuts code you complained
about was removed from 0.53 and the relaxation tightened a bit. So
with 0.53 I get changes with both matrices.</font>
<br>
<br><font size=2 face="sans-serif">I am looking at relaxation in trunk
- at present the code runs slower if I tighten too much.</font>
<br>
<br><font size=2 face="sans-serif">John</font>
<br>
<br>
<br>
<table width=100%>
<tr>
<td><img src=cid:_1_2111E6942111E2AC007171E68525756A>
<td width=100%>
<table width=100%>
<tr valign=top>
<td width=100%><font size=2 face="sans-serif"><b>RE: [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">John J Forrest</font>
<td>
<div align=right><font size=1 face="sans-serif">02/27/2009 11:37 AM</font></div></table>
<br>
<table width=100%>
<tr>
<td>
<table width=100%>
<tr>
<td><font size=1 color=#8f8f8f face="sans-serif">Cc:</font>
<td width=100%><font size=1 face="sans-serif">"Cgl@list.coin-or.org"</font></table>
<br>
<td>
<div align=right></div></table>
<br></table>
<br>
<br>
<hr>
<br>
<br>
<br><font size=2 color=#004080 face="Calibri">Sure – I’ve attached two
mps files (one for which cuts will be generated, one for which they won’t)
and a simple test driver based on some Cgl example. </font>
<br><font size=2 color=#004080 face="Calibri"> </font>
<br><font size=2 color=#004080 face="Calibri">Jean-Paul</font>
<br><font size=2 color=#004080 face="Calibri"> </font>
<br><font size=2 face="Tahoma"><b>From:</b> cgl-bounces@list.coin-or.org
[mailto:cgl-bounces@list.coin-or.org] <b>On Behalf Of </b>John J Forrest<b><br>
Sent:</b> Friday, February 27, 2009 7:40 AM<b><br>
Cc:</b> Cgl@list.coin-or.org<b><br>
Subject:</b> Re: [Cgl] Issue/potential bug with CglGomory cuts</font>
<br><font size=3 face="Times New Roman"> </font>
<br><font size=2 face="Arial"><br>
There was an accuracy issue with Gomory cuts. It is very likely that
the correction was over drastic.</font><font size=3 face="Times New Roman">
<br>
</font><font size=2 face="Arial"><br>
If you give me some code, I can try and correct the correction.</font><font size=3 face="Times New Roman">
<br>
</font><font size=2 face="Arial"><br>
John Forrest</font><font size=3 face="Times New Roman"> <br>
</font>
<p>
<table width=100%>
<tr>
<td width=8%>
<td width=91%>
<br>
<table width=100%>
<tr valign=top>
<td width=100%><font size=2 face="Arial"><b>[Cgl] Issue/potential bug with
CglGomory cuts</b></font></table>
<br><font size=3 face="Times New Roman"> </font>
<p>
<br>
<table width=100%>
<tr>
<td width=33%><font size=2 color=#e26200 face="Arial"><b>Watson, Jean-paul
</b></font>
<td width=5%><font size=2 color=#8f8f8f face="Arial">to:</font><font size=3 face="Times New Roman">
</font>
<td width=32%><font size=2 face="Arial">Cgl@list.coin-or.org</font><font size=3 face="Times New Roman">
</font>
<td width=28%>
<div align=right><font size=1 face="Arial">02/26/2009 10:37 PM</font></div></table>
<br><font size=3 face="Times New Roman"> </font>
<p>
<br>
<table width=100%>
<tr>
<td width=98%>
<table width=100%>
<tr>
<td width=22%><font size=2 color=#8f8f8f face="Arial">Sent by:</font><font size=3 face="Times New Roman">
</font>
<td width=77%><font size=2 color=#e26200 face="Arial"><b>cgl-bounces@list.coin-or.org</b></font><font size=3 face="Times New Roman">
</font>
<tr>
<td><font size=1 color=#8f8f8f face="Arial">Cc:</font><font size=3 face="Times New Roman">
</font>
<td><font size=1 face="Arial">"Carr, Robert D", "Hart, William
E"</font></table>
<br>
<td width=1%></table>
<br></table>
<br><font size=3 face="Times New Roman"> </font>
<div align=center>
<br>
<hr></div>
<br><font size=3 face="Times New Roman"><br>
<br>
</font><font size=2 face="Calibri"><br>
Dear CGL’ers:</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
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><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
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><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
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><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
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><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
if (number<limit||!numberNonInteger)
<br>
{</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
bool goodCut=true;</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
bounds[1]=rhs;</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
if (number>50&&numberNonInteger)</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
{</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
bounds[1] = bounds[1]+1.0e-6+1.0e-8*fabs(rhs); // weaken</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
}</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
if (number>5&&numberNonInteger&&relaxation>1.0e-20)
<br>
{</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
relaxation *= fabs(rhs);</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
//printf("relaxing rhs by %g\n",CoinMin(relaxation,1.0e-3));</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
bounds[1] = bounds[1]+CoinMin(relaxation,1.0e-3); //
weaken</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
#if 1</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
//bounds[1] = bounds[1]+relaxation*fabs(rhs); // weaken</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
// may be better to thow away</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
if (relaxation>1.0e6)</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
{</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
goodCut=false;</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
}</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
#endif</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
}</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
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. <br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
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><font size=3 face="Times New Roman">
</font><font size=2 face="Arial"><br>
1. </font><font size=2 face="Calibri">The intuition
behind scaling the relaxation by the fabs(rhs) factor</font><font size=3 face="Times New Roman">
</font><font size=2 face="Arial"><br>
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><font size=3 face="Times New Roman">
</font><font size=2 face="Arial"><br>
3. </font><font size=2 face="Calibri">The intuition
behind triggering of culling logic only when “numberNonInteger” is >
0.</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
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”. <br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
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><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
There are many more details, but the intent is to start a discussion. Any
help is greatly appreciated on our end!</font><font size=3 face="Times New Roman">
</font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
Jean-Paul</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
--</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Arial"><br>
Dr. Jean-Paul Watson</font><font size=3 face="Times New Roman"> </font><font size=2 face="Arial"><br>
Discrete Math and Complex Systems Department</font><font size=3 face="Times New Roman">
</font><font size=2 face="Arial"><br>
Sandia National Laboratories</font><font size=3 face="Times New Roman">
</font><font size=2 face="Arial"><br>
P.O. Box 5800, MS 1318</font><font size=3 face="Times New Roman"> </font><font size=2 face="Arial"><br>
Albuquerque, NM 87185-1318 USA</font><font size=3 face="Times New Roman">
</font><font size=2 face="Arial"><br>
(505) 845-8887</font><font size=3 face="Times New Roman"> </font><font size=2 face="Arial"><br>
jwatson@sandia.gov</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=3 face="Times New Roman"> </font><font size=2 face="Calibri"><br>
</font><font size=2 face="Courier New">_______________________________________________<br>
Cgl mailing list<br>
Cgl@list.coin-or.org<br>
http://list.coin-or.org/mailman/listinfo/cgl[attachment "somecuts.mps"
deleted by John J Forrest/Watson/IBM] [attachment "cuttest.cpp"
deleted by John J Forrest/Watson/IBM] [attachment "nocuts.mps"
deleted by John J Forrest/Watson/IBM] </font>
<br>