<font face="arial,helvetica,sans-serif">Hi All,</font><div><font face="arial,helvetica,sans-serif"><br></font></div><div><font face="arial,helvetica,sans-serif">I think that the problem discovered by </font><span style="font-family:arial,sans-serif;font-size:12.727272033691406px">Torsten is a really important one.</span></div>
<div><font face="arial, sans-serif">I've observed heap corruption when the solution process creates many nodes (e.g. when running CBC in parallel). This may explain those bugs.</font></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" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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. (+49) 24 08 - 94 56 3024 FAX: -94 56 25<br>
e-mail: <a href="mailto:Torsten.Fahle@inform-software.com">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">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 clear="all"><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>