[Scip] implementation of Gomory cuts

Miles Lubin miles.lubin at gmail.com
Thu Oct 11 02:32:39 MEST 2012


Hello,

I was looking into the effectiveness of Gomory cuts on a particular
(pure) 0-1 model, and with debugging output I discovered that most of
the cuts generated were not actually added because the row activity
was less than the upper bound (so the cut is not violated).

For example:
debug:  -> success=1: -0.666667 <= 4

I'm a bit confused by this, because I believe Gomory cuts are
guaranteed to cut off the current LP solution (even if not by much) if
based on any row of the tableau with a fractional value. I see that
the Gomory cuts are generated using the MIR routines, as described in
Proposition 8.5 (p. 106) of Tobias Achterberg's thesis, but these are
also guaranteed to cut off the current LP solution by inspecting the
formula on p.106.

The IP is pretty well-conditioned, so I don't believe that numerical
issues are to blame. Is there something important that I don't
understand, or could this be a bug?

Thanks!
Miles


More information about the Scip mailing list