Opened 13 years ago

Closed 12 years ago

#3 closed defect (fixed)

pop heap asserts

Reported by: San Owned by: forrest
Priority: major Component: component1
Version: Keywords:
Cc:

Description

When I was debugging an optimisation on my problem without using any cut generator, heuristic etc, I get an assertion in the following method:

CbcNode * 
CbcTree::bestNode(double cutoff)
{
...
    pop_heap(nodes_.begin(), nodes_.end(), comparison_);
}

The vc++ error message was:

File: c:\program files(x86)\microsoft visual studio 8\vc\include\algorithm
Line: 1677
Expression: invalid heap

Here's a snipplet of the stack trace:

>	test.exe!std::_Debug_message(const wchar_t * message=0x00a6e1b8, const wchar_t * file=0x00a6e110, unsigned int line=1677)  Line 23	C++
 	test.exe!std::_Debug_heap<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x0448f610 {nodeInfo_=0x02318380 objectiveValue_=-2944444107.1021638 guessedObjectiveValue_=-2944444107.0968237 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0x0244ac58 {nodeInfo_=0xfeeefeee objectiveValue_=-2.6569842580370804e+303 guessedObjectiveValue_=-2.6569842580370804e+303 ...}, CbcCompare _Pred={...})  Line 1677 + 0x14 bytes	C++
 	test.exe!std::pop_heap<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x0233a7f0 {nodeInfo_=0x023da060 objectiveValue_=-3030148395.2399182 guessedObjectiveValue_=-3030148395.2327580 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0x0244ac58 {nodeInfo_=0xfeeefeee objectiveValue_=-2.6569842580370804e+303 guessedObjectiveValue_=-2.6569842580370804e+303 ...}, CbcCompare _Pred={...})  Line 1889 + 0x77 bytes	C++
 	test.exe!CbcTree::bestNode(double cutoff=1.0000000000000001e+050)  Line 109 + 0x86 bytes	C++
 	test.exe!CbcModel::branchAndBound(int doStatistics=1)  Line 1166 + 0x29 bytes	C++

Change History (11)

comment:1 Changed 13 years ago by forrest

  • Owner changed from somebody to forrest

This seems to be because Microsoft heap assumes the comparison of x an dy will always return same result. If their values were equal and because of the way comparisons were done it was possible for the result to be random.

Hopefully fixed on development branch

comment:2 Changed 13 years ago by forrest

  • Resolution set to fixed
  • Status changed from new to closed

comment:3 Changed 12 years ago by San

  • Resolution fixed deleted
  • Status changed from closed to reopened

The problem doesn't seem to be fixed in 1.1 stable as I've just encountered the same problem again.

comment:4 Changed 12 years ago by San

Also get invalid heap assertion when it's doing push_heap.

 	test.exe!std::_Debug_message(const wchar_t * message=0x00b441c0, const wchar_t * file=0x00b44118, unsigned int line=1677)  Line 23	C++
 	test.exe!std::_Debug_heap<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x024fdd80 {nodeInfo_=0x024a4d90 objectiveValue_=-93255431.631750330 guessedObjectiveValue_=-93255431.630390331 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0x024ffa78 {nodeInfo_=0x024ffae0 objectiveValue_=-93696590.744081780 guessedObjectiveValue_=-93696590.742651775 ...}, CbcCompare _Pred={...})  Line 1677 + 0x14 bytes	C++
 	test.exe!std::_Push_heap_0<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,int,CbcNode *,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x024f07e0 {nodeInfo_=0x034c7760 objectiveValue_=-93670296.859430090 guessedObjectiveValue_=-93670296.857440084 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0x024ffa78 {nodeInfo_=0x024ffae0 objectiveValue_=-93696590.744081780 guessedObjectiveValue_=-93696590.742651775 ...}, CbcCompare _Pred={...}, int * __formal=0x00000000, int * __formal=0x00000000)  Line 1765 + 0x77 bytes	C++
 	test.exe!std::push_heap<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x024f07e0 {nodeInfo_=0x034c7760 objectiveValue_=-93670296.859430090 guessedObjectiveValue_=-93670296.857440084 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0x024ffa78 {nodeInfo_=0x024ffae0 objectiveValue_=-93696590.744081780 guessedObjectiveValue_=-93696590.742651775 ...}, CbcCompare _Pred={...})  Line 1786 + 0xe2 bytes	C++
>	test.exe!CbcTree::push(CbcNode * x=0x024ffa78)  Line 53 + 0x86 bytes	C++
 	test.exe!CbcModel::branchAndBound(int doStatistics=0)  Line 1222 + 0x22 bytes	C++

comment:5 Changed 12 years ago by forrest

  • Resolution set to wontfix
  • Status changed from reopened to closed

I am sure it is fixed in branches/devel and pretty sure it is fixed in trunk. It seems rare and I do not want to mess with stable/1.1

Hopefully I will get around to a new stable release soon.

comment:6 Changed 12 years ago by San

  • Resolution wontfix deleted
  • Status changed from closed to reopened

I'm testing with the code on trunk and it is still asserting at push_heap on some problems.

 	performance_test.exe!std::_Debug_message(const wchar_t * message=0x0075729c, const wchar_t * file=0x00757210, unsigned int line=1681)  Line 23	C++
 	performance_test.exe!std::_Debug_heap<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x01f86c18 {nodeInfo_=0x020f8f40 objectiveValue_=-22291557071.093792 guessedObjectiveValue_=-22291557071.093483 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0x02033a90 {nodeInfo_=0x01f958c0 objectiveValue_=-22417249915.890549 guessedObjectiveValue_=-22417249915.889938 ...}, CbcCompare _Pred={...})  Line 1681 + 0x14 bytes	C++
 	performance_test.exe!std::_Push_heap_0<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,int,CbcNode *,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x01f86ca0 {nodeInfo_=0x01f9c120 objectiveValue_=-22332910639.662392 guessedObjectiveValue_=-22332910639.662300 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0x02033a90 {nodeInfo_=0x01f958c0 objectiveValue_=-22417249915.890549 guessedObjectiveValue_=-22417249915.889938 ...}, CbcCompare _Pred={...}, int * __formal=0x00000000, int * __formal=0x00000000)  Line 1765 + 0x77 bytes	C++
 	performance_test.exe!std::push_heap<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x01f86ca0 {nodeInfo_=0x01f9c120 objectiveValue_=-22332910639.662392 guessedObjectiveValue_=-22332910639.662300 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0x02033a90 {nodeInfo_=0x01f958c0 objectiveValue_=-22417249915.890549 guessedObjectiveValue_=-22417249915.889938 ...}, CbcCompare _Pred={...})  Line 1786 + 0xe2 bytes	C++
 	performance_test.exe!CbcTree::push(CbcNode * x=0x02033a90)  Line 53 + 0x86 bytes	C++
 	performance_test.exe!CbcTree::cleanTree(CbcModel * model=0x0012f4a4, double cutoff=-22199913644.033531, double & bestPossibleObjective=-22420711678.521683)  Line 153 + 0x33 bytes	C++
>	performance_test.exe!CbcModel::branchAndBound(int doStatistics=0)  Line 1128	C++

comment:7 Changed 12 years ago by San

If strong branching is set to 0, pop_heap asserts on some problems.

>	performance_test.exe!std::_Debug_message(const wchar_t * message=0x00757254, const wchar_t * file=0x007571c8, unsigned int line=1677)  Line 23	C++
 	performance_test.exe!std::_Debug_heap<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x01f9b850 {nodeInfo_=0x01f782f0 objectiveValue_=-63655024506.492882 guessedObjectiveValue_=-63655024506.492844 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0xfdfdfdfd {nodeInfo_=??? objectiveValue_=??? guessedObjectiveValue_=??? ...}, CbcCompare _Pred={...})  Line 1677 + 0x14 bytes	C++
 	performance_test.exe!std::pop_heap<std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> >,CbcCompare>(std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _First=0x01f862c0 {nodeInfo_=0x01f78be0 objectiveValue_=-63641573813.759636 guessedObjectiveValue_=-63641573813.759506 ...}, std::_Vector_iterator<CbcNode *,std::allocator<CbcNode *> > _Last=0xfdfdfdfd {nodeInfo_=??? objectiveValue_=??? guessedObjectiveValue_=??? ...}, CbcCompare _Pred={...})  Line 1889 + 0x77 bytes	C++
 	performance_test.exe!CbcTree::bestNode(double cutoff=1.0000000000000001e+050)  Line 109 + 0x86 bytes	C++
 	performance_test.exe!CbcModel::branchAndBound(int doStatistics=0)  Line 1197 + 0x29 bytes	C++

comment:8 Changed 12 years ago by San

The pop_heap and push_heap problems seemed to be fixed in branch/devel but I get a different heap problem now if I try to use CbcSimpleIntegerPseudoCost?. I get the following error when running the longthin example:

HEAP CORRUPTION DETECTED: before Normal block (#1741006) at 0x02021628.  CRT detected that the applicatoin wrote to memory before start of heap buffer.

>	coin.exe!_free_dbg_nolock(void * pUserData=0x00a1de48, int nBlockUse=1)  Line 1269 + 0x3b bytes	C++
 	coin.exe!_free_dbg(void * pUserData=0x00a1de48, int nBlockUse=1)  Line 1194 + 0xd bytes	C++
 	coin.exe!operator delete(void * pUserData=0x00a1de48)  Line 54 + 0x10 bytes	C++
 	coin.exe!operator delete[](void * p=0x00a1de48)  Line 21 + 0x9 bytes	C++
 	coin.exe!CbcModel::addObjects(int numberObjects=2, CbcObject * * objects=0x00a1db40)  Line 6083 + 0x15 bytes	C++

comment:9 Changed 12 years ago by San

Sorry my mistake, pop_heap and push_heap problems are still present in branches/devel.

comment:10 Changed 12 years ago by forrest

Lots of stuff has been changed. Will look at longthin though as something similar happens when I try.

comment:11 Changed 12 years ago by forrest

  • Resolution set to fixed
  • Status changed from reopened to closed

Fixed bug for longthin. Will close again unless I get something I can debug.

Note: See TracTickets for help on using tickets.