[Cbc] Problem in CbcCompareUser/invalid heap

[John Forrest]

Haroldo,

Using which compiler do you have problems with CbcCompareDefault - or is 
it with CbcCompareUser?

If it is gcc then I am totally mystified as I changed CbcCompareDefault 
to do

    return (drand48()<0.5);

and my runs were fine (not even much slower!).

So is just with Windows or Intel?

John Forrest


On 12/11/12 00:04, Haroldo Santos wrote:
> Hi All,
>
> I think that the problem discovered by Torsten is a really important one.
> I've observed heap corruption when the solution process creates many 
> nodes (e.g. when running CBC in parallel). This may explain those bugs.
>
>
> On Tue, Oct 23, 2012 at 11:06 AM, Torsten Fahle 
> <Torsten.Fahle at inform-software.com 
> <mailto:Torsten.Fahle at inform-software.com>> wrote:
>
>     Hi,
>
>     there seems to be a problem in CbcCompareUser::test(...)
>     We received an "invalid heap" message from STL.
>     STL was trying to insert a new B&B node into the node tree and
>     detected that the heap was no longer correct
>     It turned out that test(CbcNode*x, CbcNode* y) in
>      CbcCompareUser.cpp changes the node ordering without re-ordering
>     the heap.
>
>
>     Here is our analysis and workaround. Any comment or better
>     solution is appreciated.
>
>     In CbcCompareUser, test() is a methods that compares two nodes
>     from the node tree and indicates which node is considered better.
>     As the node tree is a heap, any change in the compare strategy
>     requires a heap re-organization.
>     Methods CbcCompareUser::newSolution() and
>     CbcCompareUser::every1000Nodes() request such a re-organization by
>     returning true.
>
>     In CbcCompareUser.cpp,  test() starts by selecting either a depth
>     oriented strategy (before a solution is found) or an objective
>     oriented strategy (after a solution is found).
>     That selection depends on weight_ which is manipulated in
>     CbcCompareUser::newSolution()  and any change to weight_ made in
>     CbcCompareUser::newSolution() also requests a heap reorganisation.
>     However, that selection also depends on x->depth()/y->depth().
>     Depth is a property of the node that is independent of any
>     decisions made in
>     CbcCompareUser::newSolution() and CbcCompareUser::every1000Nodes().
>
>     here is the code snippet from CbcCompareUser.cpp as provided in
>     the CBC_277-release.
>
>     188     // Returns true if y better than x
>     189     bool
>     190     CbcCompareUser::test (CbcNode * x, CbcNode * y)
>     191     {
>     192       if (weight_==-1.0&&(y->depth()>7||x->depth()>7)) {
>     (N.B.: there is another implementation of test() in that files,
>     starting at line 85 that does not use the "x->depth()...", but
>     that method is commented out )
>
>
>     At some point we had 3 nodes A, B, C where test() indicates: "A
>     better than B", "B better than C", and "C better than A".
>     The reason was that two of these three comparisons had been
>     conducted in the "if"-part (weight_ = 1 and at least one node was
>     deeper than 7),
>     whereas the last comparison had been performed in the "else "-part
>     (weight_ = -1, either node had deep <= 5).
>     As there was no heap re-organization in between, these evaluations
>     were not compatible and thus corrupted the heap.
>
>     A quick solution is to remove the depth-test from the if.
>     Another would be to switch strategy in
>     ::newSolution()/::every1000Node(), indicating that via some enum
>     and only evaluation that in ::test().
>
>     The problem exists in cbc 277. The code in CbcCompareUser looks
>     the same also in older versions of Cbc (checked randomly down to
>     version 2.3.0).
>
>     Best regards,
>
>        Torsten
>
>
>
>
>
>
>
>     --
>     Dr. Torsten Fahle
>     Aviation Division
>     INFORM GmbH, Pascalstr.23, 52076 Aachen, Germany
>     Tel. (+49) 24 08 - 94 56 3024  FAX: -94 56 25
>     e-mail: Torsten.Fahle at inform-software.com
>     <mailto:Torsten.Fahle at inform-software.com> http://www.groundstar.de
>     INFORM Institut fuer Operations Research und Management GmbH
>     Registered AmtsG Aachen HRB1144 Gfhr.Adrian Weiler
>
>
>
>     _______________________________________________
>     Cbc mailing list
>     Cbc at list.coin-or.org <mailto:Cbc at list.coin-or.org>
>     http://list.coin-or.org/mailman/listinfo/cbc
>
>
>
>
> -- 
> =============================================================
> Haroldo Gambini Santos
> Computing Department - Universidade Federal de Ouro Preto - UFOP
> email: haroldo [at ] iceb.ufop.br <http://iceb.ufop.br>
> home/research page: www.decom.ufop.br/haroldo/ 
> <http://www.decom.ufop.br/haroldo/>
>
> "Computer science is no more about computers than astronomy
> is about telescopes." Edsger Dijkstra
>
>
>
> _______________________________________________
> 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/20121114/509f990f/attachment.html>