[Cbc] Problem in CbcCompareUser/invalid heap

[Torsten Fahle]

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