[Cgl] Issue/potential bug with CglGomory cuts
Watson, Jean-paul
jwatson at sandia.gov
Fri Feb 27 22:25:20 EST 2009
For list archival purposes, copy of an e-mail that I just sent John F. w/o the attachment.
Jean-Paul
From: Watson, Jean-paul
Sent: Friday, February 27, 2009 8:20 PM
To: 'John J Forrest'
Cc: Jonathan Eckstein; Phillips, Cynthia A
Subject: RE: [Cgl] Issue/potential bug with CglGomory cuts
Hi John,
Thanks for the suggestion - I had thought we were up-to-date, and spent time this PM making sure we were (after some code fixes due to deprecated COIN-related APIs). Specifically, I brought in the latest coin-cbc stable branch (2.2).
The fix did correct the PP08 problem, but there remain other instances where cuts are not generated. I'm attaching the smallest remaining one (out of about 15), which is derived from set1ch.
Given that you aren't filtering in the old style, I have even less of an idea why cuts would not be generated in this case.
I can send additional "break" instances if you want, but figured the current one-at-a-time paradigm is making for good progress thus far.
Jean-Paul
From: cgl-bounces at list.coin-or.org [mailto:cgl-bounces at list.coin-or.org] On Behalf Of John J Forrest
Sent: Friday, February 27, 2009 1:39 PM
Cc: Cgl at list.coin-or.org
Subject: Re: [Cgl] Issue/potential bug with CglGomory cuts
Jean-Paul,
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.
I am looking at relaxation in trunk - at present the code runs slower if I tighten too much.
John
RE: [Cgl] Issue/potential bug with CglGomory cuts
Watson, Jean-paul
to:
John J Forrest
02/27/2009 11:37 AM
Cc:
"Cgl at list.coin-or.org"
________________________________
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.
Jean-Paul
From: cgl-bounces at list.coin-or.org [mailto:cgl-bounces at list.coin-or.org] On Behalf Of John J Forrest
Sent: Friday, February 27, 2009 7:40 AM
Cc: Cgl at list.coin-or.org
Subject: Re: [Cgl] Issue/potential bug with CglGomory cuts
There was an accuracy issue with Gomory cuts. It is very likely that the correction was over drastic.
If you give me some code, I can try and correct the correction.
John Forrest
[Cgl] Issue/potential bug with CglGomory cuts
Watson, Jean-paul
to:
Cgl at list.coin-or.org
02/26/2009 10:37 PM
Sent by:
cgl-bounces at list.coin-or.org
Cc:
"Carr, Robert D", "Hart, William E"
________________________________
Dear CGL'ers:
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.
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.
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.
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:
if (number<limit||!numberNonInteger)
{
bool goodCut=true;
bounds[1]=rhs;
if (number>50&&numberNonInteger)
{
bounds[1] = bounds[1]+1.0e-6+1.0e-8*fabs(rhs); // weaken
}
if (number>5&&numberNonInteger&&relaxation>1.0e-20)
{
relaxation *= fabs(rhs);
//printf("relaxing rhs by %g\n",CoinMin(relaxation,1.0e-3));
bounds[1] = bounds[1]+CoinMin(relaxation,1.0e-3); // weaken
#if 1
//bounds[1] = bounds[1]+relaxation*fabs(rhs); // weaken
// may be better to thow away
if (relaxation>1.0e6)
{
goodCut=false;
}
#endif
}
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.
After some internal discussion, we realize we don't understand the logic behind this culling procedure. For example, we'd like some insight into:
1. The intuition behind scaling the relaxation by the fabs(rhs) factor
2. 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).
3. The intuition behind triggering of culling logic only when "numberNonInteger" is > 0.
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".
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.
There are many more details, but the intent is to start a discussion. Any help is greatly appreciated on our end!
Jean-Paul
--
Dr. Jean-Paul Watson
Discrete Math and Complex Systems Department
Sandia National Laboratories
P.O. Box 5800, MS 1318
Albuquerque, NM 87185-1318 USA
(505) 845-8887
jwatson at sandia.gov
_______________________________________________
Cgl mailing list
Cgl at list.coin-or.org
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]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/cgl/attachments/20090227/905e9f6e/attachment-0001.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 821 bytes
Desc: image001.gif
Url : http://list.coin-or.org/pipermail/cgl/attachments/20090227/905e9f6e/attachment-0001.gif
More information about the Cgl
mailing list