[Cbc] Problem in CbcCompareUser/invalid heap

[Haroldo Santos]

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> 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   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
> 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
home/research page: www.decom.ufop.br/haroldo/

"Computer science is no more about computers than astronomy
is about telescopes." Edsger Dijkstra
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20121111/7188ab06/attachment.html>