<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Haroldo,<br>
<br>
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? <br>
<br>
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.<br>
<br>
John<br>
<br>
<br>
<br>
On 14/11/12 20:18, Haroldo Santos wrote:<br>
</div>
<blockquote
cite="mid:CACO7Fp1sV=gj1EFfNzdfS8PjvqJEvzghKXX0p-g43m4ojacrJA@mail.gmail.com"
type="cite"><font face="arial,helvetica,sans-serif">Hi Forrest,</font>
<div><font face="arial,helvetica,sans-serif"><br>
</font></div>
<div><font face="arial,helvetica,sans-serif">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.</font></div>
<div><font face="arial,helvetica,sans-serif"><br>
</font></div>
<div><font face="arial,helvetica,sans-serif">The one I experienced
is:</font></div>
<div><font face="arial,helvetica,sans-serif">
<div><font color="#cc0000">cbc: CbcTree.cpp:457: virtual
CbcNode* CbcTree::bestNode(double): Assertion
`best->nodeInfo()->numberBranchesLeft()' failed.</font></div>
<div><br>
</div>
</font></div>
<div><font face="arial,helvetica,sans-serif">To reproduce just run
in this instance: </font></div>
<div><a moz-do-not-send="true"
href="http://miplib.zib.de/contrib/miplib2003-contrib/Markshare/markshare_6_4.mps.gz">http://miplib.zib.de/contrib/miplib2003-contrib/Markshare/markshare_6_4.mps.gz</a> <font
face="arial,helvetica,sans-serif"><br>
</font></div>
<div><font face="arial,helvetica,sans-serif"><br>
</font></div>
<div><font face="arial,helvetica,sans-serif">with options:</font></div>
<div><font face="arial,helvetica,sans-serif">
<div>cbc markshare_6_4.mps.gz dualS preprocess=off cuts=off
heur=off passF=0 threads=6 strong=0 trust=0 solve</div>
<div><br>
</div>
<div>and wait (820000 nodes in my case).</div>
</font></div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Wed, Nov 14, 2012 at 6:43 AM, John
Forrest <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:john.forrest@fastercoin.com" target="_blank">john.forrest@fastercoin.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>Haroldo,<br>
<br>
Using which compiler do you have problems with
CbcCompareDefault - or is it with CbcCompareUser?<br>
<br>
If it is gcc then I am totally mystified as I changed
CbcCompareDefault to do<br>
<br>
return (drand48()<0.5);<br>
<br>
and my runs were fine (not even much slower!).<br>
<br>
So is just with Windows or Intel?<span class="HOEnZb"><font
color="#888888"><br>
<br>
John Forrest <br>
</font></span>
<div>
<div class="h5"> <br>
<br>
On 12/11/12 00:04, Haroldo Santos wrote:<br>
</div>
</div>
</div>
<div>
<div class="h5">
<blockquote type="cite"> Hi All,
<div><br>
</div>
<div>I think that the problem discovered by <span>Torsten
is a really important one.</span></div>
<div>I've observed heap corruption when the solution
process creates many nodes (e.g. when running CBC
in parallel). This may explain those bugs.</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Tue, Oct 23, 2012 at
11:06 AM, Torsten Fahle <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:Torsten.Fahle@inform-software.com"
target="_blank">Torsten.Fahle@inform-software.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote">Hi,<br>
<br>
there seems to be a problem in
CbcCompareUser::test(...)<br>
We received an "invalid heap" message from
STL.<br>
STL was trying to insert a new B&B node
into the node tree and detected that the heap
was no longer correct<br>
It turned out that test(CbcNode*x, CbcNode* y)
in CbcCompareUser.cpp changes the node
ordering without re-ordering the heap.<br>
<br>
<br>
Here is our analysis and workaround. Any
comment or better solution is appreciated.<br>
<br>
In CbcCompareUser, test() is a methods that
compares two nodes from the node tree and
indicates which node is considered better.<br>
As the node tree is a heap, any change in the
compare strategy requires a heap
re-organization.<br>
Methods CbcCompareUser::newSolution() and
CbcCompareUser::every1000Nodes() request such
a re-organization by returning true.<br>
<br>
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).<br>
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.<br>
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<br>
CbcCompareUser::newSolution() and
CbcCompareUser::every1000Nodes().<br>
<br>
here is the code snippet from
CbcCompareUser.cpp as provided in the
CBC_277-release.<br>
<br>
188 // Returns true if y better than x<br>
189 bool<br>
190 CbcCompareUser::test (CbcNode * x,
CbcNode * y)<br>
191 {<br>
192 if
(weight_==-1.0&&(y->depth()>7||x->depth()>7))
{<br>
(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 )<br>
<br>
<br>
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".<br>
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),<br>
whereas the last comparison had been performed
in the "else "-part (weight_ = -1, either node
had deep <= 5).<br>
As there was no heap re-organization in
between, these evaluations were not compatible
and thus corrupted the heap.<br>
<br>
A quick solution is to remove the depth-test
from the if.<br>
Another would be to switch strategy in
::newSolution()/::every1000Node(), indicating
that via some enum and only evaluation that in
::test().<br>
<br>
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).<br>
<br>
Best regards,<br>
<br>
Torsten<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
--<br>
Dr. Torsten Fahle<br>
Aviation Division<br>
INFORM GmbH, Pascalstr.23, 52076 Aachen,
Germany<br>
Tel. <a moz-do-not-send="true"
href="tel:%28%2B49%29%2024%2008%20-%2094%2056%203024"
value="+49240894563024" target="_blank">(+49)
24 08 - 94 56 3024</a> FAX: -94 56 25<br>
e-mail: <a moz-do-not-send="true"
href="mailto:Torsten.Fahle@inform-software.com"
target="_blank">Torsten.Fahle@inform-software.com</a>
<a moz-do-not-send="true"
href="http://www.groundstar.de"
target="_blank">http://www.groundstar.de</a><br>
INFORM Institut fuer Operations Research und
Management GmbH<br>
Registered AmtsG Aachen HRB1144 Gfhr.Adrian
Weiler<br>
<br>
<br>
<br>
_______________________________________________<br>
Cbc mailing list<br>
<a moz-do-not-send="true"
href="mailto:Cbc@list.coin-or.org"
target="_blank">Cbc@list.coin-or.org</a><br>
<a moz-do-not-send="true"
href="http://list.coin-or.org/mailman/listinfo/cbc"
target="_blank">http://list.coin-or.org/mailman/listinfo/cbc</a><br>
</blockquote>
</div>
<br>
<br>
<div><br>
</div>
-- <br>
=============================================================<br>
Haroldo Gambini Santos<br>
Computing Department - Universidade Federal de
Ouro Preto - UFOP<br>
email: haroldo [at ] <a moz-do-not-send="true"
href="http://iceb.ufop.br" target="_blank">iceb.ufop.br</a><br>
home/research page: <a moz-do-not-send="true"
href="http://www.decom.ufop.br/haroldo/"
target="_blank">www.decom.ufop.br/haroldo/</a><br>
<br>
"Computer science is no more about computers than
astronomy <br>
is about telescopes." Edsger Dijkstra<br>
<br>
</div>
<br>
<fieldset></fieldset>
<br>
<pre>_______________________________________________
Cbc mailing list
<a moz-do-not-send="true" href="mailto:Cbc@list.coin-or.org" target="_blank">Cbc@list.coin-or.org</a>
<a moz-do-not-send="true" href="http://list.coin-or.org/mailman/listinfo/cbc" target="_blank">http://list.coin-or.org/mailman/listinfo/cbc</a>
</pre>
</blockquote>
<br>
</div>
</div>
</div>
<br>
_______________________________________________<br>
Cbc mailing list<br>
<a moz-do-not-send="true" href="mailto:Cbc@list.coin-or.org">Cbc@list.coin-or.org</a><br>
<a moz-do-not-send="true"
href="http://list.coin-or.org/mailman/listinfo/cbc"
target="_blank">http://list.coin-or.org/mailman/listinfo/cbc</a><br>
<br>
</blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
<span style="font-family:courier new,monospace">=============================================================<br>
Haroldo Gambini Santos<br>
Computing Department<br>
Universidade Federal de Ouro Preto - UFOP<br>
email: haroldo [at ] <a moz-do-not-send="true"
href="http://iceb.ufop.br" target="_blank">iceb.ufop.br</a><br>
home/research page: <a moz-do-not-send="true"
href="http://www.decom.ufop.br/haroldo/" target="_blank">www.decom.ufop.br/haroldo</a><br>
</span><br>
</div>
</blockquote>
<br>
</body>
</html>