[Cgl] Issue/potential bug with CglGomory cuts

[Watson, Jean-paul]

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



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