[Cbc] [CBC] Solving partially fixed MIP problem iteratively do not converge to best

[John Forrest]

Marco,

On my first try, I was unable to reproduce the problem.  Trying slightly 
different versions and compiler optimization settings I could.  However 
by playing around I could also get a single solve to fail to get correct 
answer.

I think I have tracked down problem - in a cut generator - CglGomory.  
In some situations it was producing a bad cut - a long cut with small 
elements.

So -

a) try switching off Gomory cuts to see if it then gets correct answer.
b) use modified CglGomory.cpp which is now in Cbc/stable

Hope that fixes problem.

John Forrest

On 26/02/14 11:20, mg wrote:
> Hi John,
> thanks for the fast reply.
>
> Attached you can find a zip containing a piece of code that reproduce 
> the problem.
> Basically int the main function I load the problem from model.lp file 
> then apply the strategy described in the previous mail.
>
> The main assumptions for this strategy are:
>
> - I know a set of variables (variables2workon array in the code) that 
> I can set to 1 to get a feasible (even if not really good) solution.
> - Then, iteratively I try to set one of those variable to zero and 
> resolve the forced problem until I don't get any further improvement.
> - Since those variables are in the objective function with a quite 
> important cost, if we reduce the number of ones in this set, we arrive 
> really close to the optimum.
>
>
> If we solve it fully (i.e not iteratively, by setting fullsolve=true 
> in the code) we get an obj=381.86216, while with the iterative 
> approach we get obj=383.118855
>
> I hope I have been clear enough, anyway the code is commented and 
> should be pretty self-explanatory.
>
> The version of CBC is the release 2.8.9.
>
> Thanks,
>
> Marco
>
>
> 2014-02-26 12:10 GMT+01:00 mg <giunto.cardanico at gmail.com 
> <mailto:giunto.cardanico at gmail.com>>:
>
>     Hi John,
>     thanks for the fast reply.
>
>     Attached you can find a small piece of code that reproduce the
>     problem.
>     Basically int the main function I load the problem from model.lp
>     file then apply the strategy described in the previous mail.
>
>     The main assumptions for this strategy are:
>
>     - I know a set of variables (variables2workon array in the code)
>     that I can set to 1 to get a feasible (even if not really good)
>     solution.
>     - Then, iteratively I try to set one of those variable to zero and
>     resolve the forced problem until I don't get any further improvement.
>     - Since those variables are in the objective function with a quite
>     important cost, if we reduce the number of ones in this set, we
>     arrive really close to the optimum.
>
>
>     If we solve it fully (i.e not iteratively, by setting
>     fullsolve=true in the code) we get an obj=381.86216, while with
>     the iterative approach we get obj=383.118855
>
>     I hope I have been clear enough, anyway the code is commented and
>     should be pretty self-explanatory.
>
>     Thanks,
>
>     Marco
>
>
>
>
>     Anyway, the code should be commented enough.
>
>
>
>
>
>
>
>     2014-02-25 16:51 GMT+01:00 John Forrest
>     <john.forrest at fastercoin.com <mailto:john.forrest at fastercoin.com>>:
>
>         Marco,
>
>
>         On 25/02/14 14:22, mg wrote:
>>
>>
>>         I suspect that restoring only the column bounds between each
>>         intermediate solve is not enough to guarantee that the
>>         problem remains equal to the original...
>>         should I also remove the cuts added during the intermediate
>>         steps ?
>
>         Any cuts generated will be invalid - but they may be removed
>         anyway.
>>         Something else ?
>         Very likely.
>
>         I can try and code something to reproduce problem - if you
>         have some code you can send me then I would be more likely to
>         get around to checking things out.
>
>>         Thanks in advance,
>>         Marco
>>
>         John Forrest
>
>
>         _______________________________________________
>         Cbc mailing list
>         Cbc at list.coin-or.org <mailto: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/20140227/d111c984/attachment.html>