[Cbc] integer overflow in CglGomory.cpp

[Giacomo Nannicini]

CglGMI does not perform any integer rounding, and in fact it should be
numerically very safe, although not as optimized and tightly
integrated with the Branch-and-Cut algorithm as CglGomory.
This information is provided with no warranty :-) I haven't used
either cut generator in a long time.

Cheers

Giacomo

On Thu, May 18, 2017 at 9:41 AM, Haroldo Santos
<haroldo.santos at gmail.com> wrote:
> Hi,
>
> AFAIK, now there are two Gomory cut generators available in CBC (Cgl):
> CglGomory and CglGMI.  Does this overflow affects both versions ?
> Which version is recommended for general use now ?  Should we do some tests
> to determine that ?
>
>
>
> 2017-05-16 15:44 GMT-03:00 John Forrest <john.forrest at fastercoin.com>:
>>
>> Modified in trunk (can be copied to stable).  Just for now I have left it
>> as was unless GOMORY_LONG is defined in configure.  If anyone is interested
>> they could see what difference it makes (on my first test it was slower -
>> but then invalid cuts can be very powerful!).  There may be some connection
>> with queries about accuracy of Gomory cuts in 2015 (GOMORY_RELAX_NUMBER).
>>
>> John Forrest
>>
>>
>> On 16/05/17 10:47, Tobias Stengel wrote:
>>
>> Hi,
>>
>>
>>
>> I noticed an integer overflow in CglGomory.cpp / nearestRational(double,
>> int) lines 445 and 446. That specific MIP is solved correctly, but I have no
>> idea whether such an overflow can lead to wrong cuts that e.g. cut off the
>> optimal solution. Anyway integer overflow is undefined behaviour in C/C++
>> and the returned fractional is not „near“ the input…
>>
>>
>>
>> 2 parameter sets for nearestRational that lead to overflow can be found in
>> the attached test program. Does anyone know how nearestRational works and
>> how the overflow can be fixed properly?
>>
>>
>>
>> Thanks
>>
>>
>>
>> Tobias
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> _______________________________________________
>> Cbc mailing list
>> Cbc at list.coin-or.org
>>
>> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=js2M0T-3OIMIVDvokcKjokJbk0F8QOCd0mT4FsVFE88&m=L7AT776VDQX3BSKmHST7549RZsaJ2y94DaRP4TUG7Q4&s=nhL5_z_yBvb0pFHQ119ru9uHYjq2HWhTiD1goMhbxt8&e=
>>
>>
>>
>> _______________________________________________
>> Cbc mailing list
>> Cbc at list.coin-or.org
>>
>> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=pLOfVNEEHf-xhIqn1-uzYcZ6Q7UefG6Bg6rXCKTMiAA&m=gDrVYEcxW3vJRno33gHauuTWvszzplGzQ51Sj1KjdZ8&s=PapLwmuavMGxMxQgc3G5q_UgPp1PqK_OgG0StA88mIA&e=
>>
>
>
>
> --
> =============================================================
> Haroldo Gambini Santos
> Computing Department
> Universidade Federal de Ouro Preto - UFOP
> email: haroldo [at ] iceb.ufop.br
> home/research page: www.decom.ufop.br/haroldo
>
>
> It has long been an axiom of mine that the little things are infinitely
> the most important.
> -- Sir Arthur Conan Doyle, "A Case of Identity"
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://list.coin-or.org/mailman/listinfo/cbc
>