[Cbc] Problem in CbcCompareUser/invalid heap

[Torsten Fahle]

John,

thanks for the quick reply.

Maybe my last mail was misleading. 
My intention was not to blame "weight_" for the problem.
weight_ is changed in newSolution and then a heap 
reordering is triggered - should be perfectly ok. 
The problem is depth() which switches the ordering strategy 
depending on node properties independently of any heap reorder. 
That  can cause problems like in the example you gave.

Indeed , in our application (where our NodeCompare is a copy of CbcCompareUser)
we had a problem with three nodes and we simply remove the depth() test to solve it.

My intention was to give that observation back to the cbc-list so that
the example code could be adapted accordingly.

Sorry for the confusion.

Best regards,
Torsten



>>> On Donnerstag, 25. Oktober 2012 at 11:56, in message
<50890CCE.7010300 at fastercoin.com>, John Forrest <john.forrest at fastercoin.com>
wrote:
> 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 
>>
>>
> 
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org 
> http://list.coin-or.org/mailman/listinfo/cbc