[Cbc] Problem in CbcCompareUser/invalid heap
Torsten Fahle
Torsten.Fahle at inform-software.com
Tue Oct 23 09:07:00 EDT 2012
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 277. The code in CbcCompareUser looks the same also in older versions of Cbc (checked randomly down to version 2.3.0).
Best regards,
Torsten
--
Dr. Torsten Fahle
Aviation Division
INFORM GmbH, Pascalstr.23, 52076 Aachen, Germany
Tel. (+49) 24 08 - 94 56 3024 FAX: -94 56 25
e-mail: Torsten.Fahle at inform-software.com http://www.groundstar.de
INFORM Institut fuer Operations Research und Management GmbH
Registered AmtsG Aachen HRB1144 Gfhr.Adrian Weiler
More information about the Cbc
mailing list