[Cbc] Fwd: Gomory or not Gomory, that is the question.

[John Forrest]

Yves,

Running the code with debug I get -

Cut with 3 coefficients, cuts off known solutions by 1.57182e-06, 
lo=-1.79769e+308, ub=22
( 315 , -1 ) ( 1266 , -1 ) ( 1406 , 2 )
Non zero solution values are
( 315 , 1 ) ( 1266 , 25 ) ( 1406 , 24 )

which looks impossible - however looking more closely the actual 
coefficients are

{-0.99999999999988898, -1, 2.0000001209088585}

I will think harder what to do, but I may find it difficult to fix 
elegantly.

My proposed immediate fix would be to add a bit of code, to be turned on 
at Cbc configuration time to weaken all cuts where coefficients are not 
integral and variables are not all 0-1.  I have coded it and tried it on 
your problem - so that cut gets weakened by 1.0e-7*(1+25+24).

If that solution will work for you, I will look at its effect on other 
problems and check code into trunk.  I would think it should fix all 
your problems and not make anything significantly slower.

John
On 03/03/15 19:06, Yves Touchard wrote:
> With the right reply address!
>
>
> -------- Message transféré --------
> Sujet : 	Gomory or not Gomory, that is the question.
> Date : 	Tue, 03 Mar 2015 20:03:03 +0100
> De : 	Yves Touchard <yves.touchard at sfr.fr>
> Pour : 	cbc at list.coin-or.org
>
>
>
> Hello,
>
> You will find here 
> (https://www.dropbox.com/s/ayo93hi4togpc9m/noGom.lp?dl=0) a constraint 
> file for which cbc founds a solution when Gomory cuts are removed or 
> for specific cutlength values.
>
> In other words, the following command leads to an infeasible problem:
> //soft/cbc-trunk-2149/bin/cbc noGom.lp branch printingOptions normal 
> solution noGom.sol/
>
> and with the following commands, cbc claims that there is a solution:
> //soft/cbc-trunk-2149/bin/cbc noGom.lp gomory off branch 
> printingOptions normal solution noGom.sol/
> //soft/cbc-trunk-2149/bin/cbc noGom.lp cutlength xx branch 
> printingOptions normal solution noGom.sol/ (with xx equal to -1, 0, 
> 10, 20... and different from 30...)
>
> Since our problems are dynamically generated, it is very painful to 
> try to solve them with different options, hoping that the right set is 
> in the list.
>
> So, is there a way to find this set of options.
> Or could you explain what are the rows that are difficult for cbc.
> And, does the change of the continuous variables into integer 
> variables help? (for our problems, it makes sense).
>
> Thanks and regards
>
> Yves
>
>
>
> ------------------------------------------------------------------------------
> 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é.
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20150304/9047adb1/attachment-0001.html>