[Cgl] Issue/potential bug with CglGomory cuts
John J Forrest
jjforre at us.ibm.com
Fri Feb 27 15:39:08 EST 2009
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/339fab0d/attachment.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 821 bytes
Desc: not available
Url : http://list.coin-or.org/pipermail/cgl/attachments/20090227/339fab0d/attachment.gif
More information about the Cgl
mailing list