[Cbc] Cbc Digest, Vol 88, Issue 10

[Yves Touchard]

Hello John,

Thanks for all.
Not sure i can help you for the fix... :-)

I will use now a cbc version compiled with gcc #4.9.0. It seems to be ok
for my NRT.

Regards,

Yves

On 10/31/2014 05:00 PM, cbc-request at list.coin-or.org wrote:
> Date: Fri, 31 Oct 2014 10:48:59 +0000
> From: John Forrest <john.forrest at fastercoin.com>
> To: cbc at list.coin-or.org
> Subject: [Cbc] Infeasible problem (bad cut)
> Message-ID: <5453691B.4020802 at fastercoin.com>
> Content-Type: text/plain; charset=windows-1252; format=flowed
>
> By changing compilers, I managed to reproduce Yves's infeasible problem.
>
> It was due to some loss of accuracy in Gomory cuts giving a cut
>
> -12.1428746880448486 >= -4.25000784432430034*x0 -12.1428733623240479*x1
> -12.1428733623240479*x2 -12.1428733623240479*x3 -11.1428733623240479*x4
>
> The optimal solution had x1 at 1.0 and the others at 0.0 so the cut was
> infeasible by 1.0e-6.
>
> Now if there had been continuous variables in that cut - or even two
> nonzero integer variables, then the code would probably be OK - but with
> just one fixed to 1.0 it is going to say infeasible.
>
> It seems to me that the answer is to test the ratios of elements in cut
> to rhs of cut and if they are very close to integral but just the wrong
> side of rhs - then make them exact.  So in this case three elements go
> exactly to the rhs value.
>
> It fixes problem and on some very limited tests reduces the time taken -
> maybe because the constraint is "cleaner".
>
> I may modify CglGomory in trunk, but I thought I would see if people
> agreed with my analysis.
>
> John Forrest
>
> I also found and fixed Yves' segFault.


------------------------------------------------------------------------------
This message and any attachments (the "message") are confidential and intended solely for the addressee(s). Any unauthorized use or dissemination is prohibited. E-mails are susceptible to alteration. Neither DxO Labs nor any of its subsidiaries or affiliates shall be liable for the message if altered, changed or falsified.
Ce message et toutes les pièces jointes (ci-après le "message") sont confidentiels et établis à l'intention exclusive de ses destinataires. Toute utilisation ou diffusion non autorisé est interdite. Tout message électronique est susceptible d'altération. DxO Labs et ses filiales déclinent toute responsabilité au titre de ce message s'il a été altéré, modifié ou falsifié.