[Cbc] Problem in CbcCompareUser/invalid heap
John Forrest
john.forrest at fastercoin.com
Wed Nov 14 15:43:04 EST 2012
Haroldo,
Are you in debug mode? Other problem is threads 6 is
non-deterministic. Can you reproduce in a deterministic way e.g. no
threads or threads>100?
I am running problem but over 4 million nodes no problem - memory used
is going up - may crash on memory in a few hours. I am using
gcc/Linux. If it was serial then I think I would use less memory and do
some different things.
John
On 14/11/12 20:18, Haroldo Santos wrote:
> 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 <mailto: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
>> <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
>> <tel:%28%2B49%29%2024%2008%20-%2094%2056%203024> 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 <mailto:Cbc at list.coin-or.org>
>> http://list.coin-or.org/mailman/listinfo/cbc
>
>
> _______________________________________________
> 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/>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20121114/f47106ec/attachment-0015.html>
More information about the Cbc
mailing list