<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 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 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 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 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 href="mailto:Torsten.Fahle@inform-software.com" target="_blank">Torsten.Fahle@inform-software.com</a>
<a 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 href="mailto:Cbc@list.coin-or.org" target="_blank">Cbc@list.coin-or.org</a><br>
<a 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 href="http://iceb.ufop.br" target="_blank">iceb.ufop.br</a><br>
home/research page: <a 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 href="mailto:Cbc@list.coin-or.org" target="_blank">Cbc@list.coin-or.org</a>
<a 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 href="mailto:Cbc@list.coin-or.org">Cbc@list.coin-or.org</a><br>
<a 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 href="http://iceb.ufop.br" target="_blank">iceb.ufop.br</a><br>home/research page: <a href="http://www.decom.ufop.br/haroldo/" target="_blank">www.decom.ufop.br/haroldo</a><br>
</span><br>
</div>