<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>
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?<br>
<br>
John Forrest <br>
<br>
<br>
On 12/11/12 00:04, Haroldo Santos wrote:<br>
</div>
<blockquote
cite="mid:CACO7Fp2q1aWQy_Bj6h6LGR3LBcQQQKUvKOGjiEQbe0NbRu+TEw@mail.gmail.com"
type="cite">
<meta http-equiv="Context-Type" content="text/html;
charset=ISO-8859-1">
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. (+49) 24 08 - 94 56 3024 FAX: -94 56 25<br>
e-mail: <a moz-do-not-send="true"
href="mailto:Torsten.Fahle@inform-software.com">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">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 class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Cbc mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Cbc@list.coin-or.org">Cbc@list.coin-or.org</a>
<a class="moz-txt-link-freetext" href="http://list.coin-or.org/mailman/listinfo/cbc">http://list.coin-or.org/mailman/listinfo/cbc</a>
</pre>
</blockquote>
<br>
</body>
</html>