[Scip] implementation of Gomory cuts

[Marc Pfetsch]

Miles,

this is a follow-up on the email you wrote more than a month ago. In the 
meantime I have checked the issue. Well, there is somthing that you can 
all a bug or a feature in SCIP - depending on your viewpoint:

The issue is that your instances contains several ranged rows, i.e., 
inequalities lhs <= a^T x <= rhs, where lhs and rhs are finite numbers. 
In this case, text-book Gomory-cuts take the side that is active, if 
any. The implementation in SCIP uses a heuristic that tries to select 
the side depending on the sign of the corresponding weight in order to 
produce favorable sign for the slack variables. This heuristic fails in 
your instance such that no cuts are produced.

In the development version of SCIP, I have added the possibility to 
choose the side depending on the basis status only, i.e., the heuristic 
is deactivated. For your instance, this indeed produces (many) cuts. 
However, it does not help to produce "good" cuts, the solving behavior 
is not changed significantly. Indeed, on our testset this version 
performs slightly worse than the default. This option is therefore 
disabled by default, but will be available in one of the next SCIP releases.

Best

Marc




On 12.10.2012 20:02, Miles Lubin wrote:
> Sounds exactly like the implementation trick I was missing! I've
> attached a minimal example for anyone interested. The behavior can be
> observed by defining SCIP_DEBUG at the top of sepa_gomory.c with scip
> 3.0.0.
>
> Thanks,
> Miles
>
> On Fri, Oct 12, 2012 at 1:20 PM, Domenico Salvagnin <dominiqs at gmail.com> wrote:
>> Slacks are handled implicitly in substituteMIRRow (lp.c). so I don't
>> think that's the problem...
>>
>> Domenico
>>
>> On Fri, Oct 12, 2012 at 12:48 PM, Miles Lubin <miles.lubin at gmail.com> wrote:
>>> I may be entirely off here, but something seems strange with how the
>>> MIR routines are used to generate the Gomory cuts. Currently, rows
>>> from the constraint matrix A are combined by using weights from a row
>>> of the basis inverse. The constraint matrix is actually of the form [
>>> A -I ], where the identity part (slacks) is handled separately, but
>>> the MIR routines are only combining rows of A. I don't see a reason
>>> why the Gomory cut shouln't involve any of the slack variables, so by
>>> combining only rows of A, it's not possible in general to generate the
>>> Gomory cut.
>>>
>>> There could be an implementation trick that I'm missing. Any ideas?
>>> (Stefan, Tobias if you're reading this.)
>>>
>>> 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