[Cbc] Problem in CbcCompareUser/invalid heap

[Haroldo Santos]

Hi Forrest,

I don't know if the reported bug is related to the one I'm having problems
(since both occur when many nodes are created I just suspected) - looking
in detail again my bug appears to be another one.

The one I experienced is:
cbc: CbcTree.cpp:457: virtual CbcNode* CbcTree::bestNode(double): Assertion
`best->nodeInfo()->numberBranchesLeft()' failed.

To reproduce just run in this instance:
http://miplib.zib.de/contrib/miplib2003-contrib/Markshare/markshare_6_4.mps.gz


with options:
cbc markshare_6_4.mps.gz dualS preprocess=off cuts=off heur=off passF=0
threads=6 strong=0 trust=0 solve

and wait (820000 nodes in my case).


On Wed, Nov 14, 2012 at 6:43 AM, John Forrest
<john.forrest at fastercoin.com>wrote:

>  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> 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
>
>
>
> _______________________________________________
> Cbc mailing listCbc at list.coin-or.orghttp://list.coin-or.org/mailman/listinfo/cbc
>
>
>
> _______________________________________________
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20121114/b63a0b1f/attachment.html>