<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<style>
<!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
tt
{mso-style-priority:99;
font-family:"Courier New";}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>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. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Jean-Paul<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in'>
<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span
style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>
cgl-bounces@list.coin-or.org [mailto:cgl-bounces@list.coin-or.org] <b>On Behalf
Of </b>John J Forrest<br>
<b>Sent:</b> Friday, February 27, 2009 7:40 AM<br>
<b>Cc:</b> Cgl@list.coin-or.org<br>
<b>Subject:</b> Re: [Cgl] Issue/potential bug with CglGomory cuts<o:p></o:p></span></p>
</div>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal style='margin-bottom:12.0pt'><br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>There was an
accuracy issue with Gomory cuts. It is very likely that the correction
was over drastic.</span> <br>
<br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>If you give me
some code, I can try and correct the correction.</span> <br>
<br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>John Forrest</span>
<br>
<br>
<o:p></o:p></p>
<table class=MsoNormalTable border=0 cellpadding=0 width="100%"
style='width:100.0%'>
<tr>
<td style='padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><img width=32 height=32 id="_x0000_i1025"
src="cid:_1_236707E823670400005094848525756A"><o:p></o:p></p>
</td>
<td width="100%" style='width:100.0%;padding:.75pt .75pt .75pt .75pt'>
<table class=MsoNormalTable border=0 cellpadding=0 width="100%"
style='width:100.0%'>
<tr>
<td width="100%" valign=top style='width:100.0%;padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>[Cgl]
Issue/potential bug with CglGomory cuts</span></b><o:p></o:p></p>
</td>
</tr>
</table>
<p class=MsoNormal><o:p> </o:p></p>
<table class=MsoNormalTable border=0 cellpadding=0 width="100%"
style='width:100.0%'>
<tr>
<td style='padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#E26200'>Watson, Jean-paul </span></b><o:p></o:p></p>
</td>
<td style='padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#8F8F8F'>to:</span> <o:p></o:p></p>
</td>
<td style='padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Cgl@list.coin-or.org</span>
<o:p></o:p></p>
</td>
<td style='padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal align=right style='text-align:right'><span
style='font-size:7.5pt;font-family:"Arial","sans-serif"'>02/26/2009 10:37
PM</span><o:p></o:p></p>
</td>
</tr>
</table>
<p class=MsoNormal><o:p> </o:p></p>
<table class=MsoNormalTable border=0 cellpadding=0 width="100%"
style='width:100.0%'>
<tr>
<td style='padding:.75pt .75pt .75pt .75pt'>
<table class=MsoNormalTable border=0 cellpadding=0 width="100%"
style='width:100.0%'>
<tr>
<td style='padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#8F8F8F'>Sent by:</span> <o:p></o:p></p>
</td>
<td width="100%" style='width:100.0%;padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#E26200'>cgl-bounces@list.coin-or.org</span></b> <o:p></o:p></p>
</td>
</tr>
<tr>
<td style='padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><span style='font-size:7.5pt;font-family:"Arial","sans-serif";
color:#8F8F8F'>Cc:</span> <o:p></o:p></p>
</td>
<td style='padding:.75pt .75pt .75pt .75pt'>
<p class=MsoNormal><span style='font-size:7.5pt;font-family:"Arial","sans-serif"'>"Carr,
Robert D", "Hart, William E"</span><o:p></o:p></p>
</td>
</tr>
</table>
</td>
<td style='padding:.75pt .75pt .75pt .75pt'></td>
</tr>
</table>
</td>
</tr>
</table>
<p class=MsoNormal style='margin-bottom:12.0pt'><o:p> </o:p></p>
<div class=MsoNormal align=center style='text-align:center'>
<hr size=2 width="100%" align=center>
</div>
<p class=MsoNormal style='margin-bottom:12.0pt'><br>
<br>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>Dear
CGL’ers:</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>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.</span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>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.</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>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.</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>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:</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
if
(number<limit||!numberNonInteger) </span><br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
{</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
bool
goodCut=true;</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
bounds[1]=rhs;</span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
if
(number>50&&numberNonInteger)</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
{</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
bounds[1] = bounds[1]+1.0e-6+1.0e-8*fabs(rhs); // weaken</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
}</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
if
(number>5&&numberNonInteger&&relaxation>1.0e-20) </span><br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
{</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
relaxation *= fabs(rhs);</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
//printf("relaxing rhs by %g\n",CoinMin(relaxation,1.0e-3));</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
bounds[1] = bounds[1]+CoinMin(relaxation,1.0e-3); // weaken</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>#if 1</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
//bounds[1] = bounds[1]+relaxation*fabs(rhs); // weaken</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
//
may be better to thow away</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
if
(relaxation>1.0e6)</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
{</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
goodCut=false;</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
}</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>#endif</span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>
}</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>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. </span><br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>After some
internal discussion, we realize we don’t understand the logic behind this
culling procedure. For example, we’d like some insight into:</span> <br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>1.
</span><span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>The
intuition behind scaling the relaxation by the fabs(rhs) factor</span> <br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>2.
</span><span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>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).</span> <br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>3.
</span><span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>The
intuition behind triggering of culling logic only when
“numberNonInteger” is > 0.</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>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”. </span><br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>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.</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>There are
many more details, but the intent is to start a discussion. Any help is greatly
appreciated on our end!</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>Jean-Paul</span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'>--</span> <br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Dr. Jean-Paul
Watson</span> <br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Discrete Math
and Complex Systems Department</span> <br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Sandia National
Laboratories</span> <br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>P.O. Box 5800,
MS 1318</span> <br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Albuquerque, NM
87185-1318 USA</span> <br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>(505) 845-8887</span>
<br>
<span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>jwatson@sandia.gov</span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span>
<br>
<span style='font-size:10.0pt;font-family:"Calibri","sans-serif"'> </span><tt><span
style='font-size:10.0pt'>_______________________________________________</span></tt><span
style='font-size:10.0pt;font-family:"Courier New"'><br>
<tt>Cgl mailing list</tt><br>
<tt>Cgl@list.coin-or.org</tt><br>
<tt>http://list.coin-or.org/mailman/listinfo/cgl</tt></span><o:p></o:p></p>
</div>
</body>
</html>