[Cgl] Issue/potential bug with CglGomory cuts
Watson, Jean-paul
jwatson at sandia.gov
Fri Feb 27 11:36:43 EST 2009
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
[cid:_1_236707E823670400005094848525756A]
[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/cgl/attachments/20090227/90b9a2f7/attachment-0001.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: somecuts.mps
Type: application/octet-stream
Size: 27552 bytes
Desc: somecuts.mps
Url : http://list.coin-or.org/pipermail/cgl/attachments/20090227/90b9a2f7/attachment-0002.obj
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: cuttest.cpp
Url: http://list.coin-or.org/pipermail/cgl/attachments/20090227/90b9a2f7/attachment-0001.pl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nocuts.mps
Type: application/octet-stream
Size: 23408 bytes
Desc: nocuts.mps
Url : http://list.coin-or.org/pipermail/cgl/attachments/20090227/90b9a2f7/attachment-0003.obj
More information about the Cgl
mailing list