[Cgl] Issue/potential bug with CglGomory cuts

[John J Forrest]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/cgl/attachments/20090227/adf86f9e/attachment-0001.html