[Scip] implementation of Gomory cuts

[Miles Lubin]

Dear Marc,

It seems from sepa_gomory.c that the issue isn't scaling, because
typically there is no violation at all (by a significant margin). The
test that fails is SCIPisFeasGT(scip, cutact, cutrhs).

I'm not sure of how to easily check the lower bound. The code in
sepa_gomory.c appears to assume that only an upper bound is generated.

Thanks,
Miles

On Thu, Oct 11, 2012 at 6:02 AM, Marc Pfetsch
<pfetsch at mathematik.tu-darmstadt.de> wrote:
>
>
> Hallo Miles,
>
> just one additional comment: Gomory cuts are indeed guaranteed to cut
> off the fractional solution. In SCIP, however, the violation is scaled
> using the (some) norm of the row. It can thus be that the violation
> after scaling is not big enough (i.e. < 0.01 in the root) and the cuts
> are discarded. This often happens for very dense cuts with large
> coefficients.
>
> Please also check whether the activity violates the *lower* bound
> (MIR-rounding can produce cuts with lower bounds as well).
>
> Best
>
> Marc
>
>
>
>
> Am 11.10.2012 04:05, schrieb Miles Lubin:
>> Hi Domenico,
>>
>> No apparent change when I set USEVBDS to FALSE. I'll send you the
>> instance in private.
>>
>> Thanks!
>> Miles
>>
>> On Wed, Oct 10, 2012 at 9:46 PM, Domenico Salvagnin <dominiqs at gmail.com> wrote:
>>> I am not sure about what's happening in your instance, but the variable bound substitution may be the one to blame here (this is an heuristic that is applied after the generation of the tableau row but before the application of the GMI formula).
>>>
>>> Try setting USEVBDS to FALSE in sepa_gomory.c and see if the problem remains.
>>> In case, you can send me the instance.
>>>
>>> Domenico
>>>
>>> On Oct 10, 2012, at 8:32 PM, Miles Lubin wrote:
>>>
>>>> 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
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de
>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip