[Cbc] Problem in CbcCompareUser/invalid heap

[John Forrest]

Torsten,

CbcCompareUser is only an example and comes without any warranty.   I 
don't understand how weight_ can be changed without re-ordering heap.  
However I think you can get the problem with weight_ == -1.0 and four 
nodes A (depth 5), B(5),C(8),D(8) where A better than B ... but D better 
than A.

I think the best solution would be to remove the depth test at line 192

John Forrest



On 25/10/12 07:41, Torsten Fahle 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 271. The code in CbcCompareUser looks the same
> also in the latest release cbc 277 and older versions of Cbc (checked randomly
> down to version 2.3.0).
>   
> Best regards,
>
>      Torsten
>
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
>
>