[BCP] Bug related to CoinSearchTreeBase::top()

[Vincent Bates]

Hello,

I am currently working on a branch-and-price algorithm in BCP-1.3.8

I have come across a segmentation fault that looks exactly like this bug reported in December 2009:
http://list.coin-or.org/pipermail/bcp/2009-December/000257.html

Unfortunately, my knowledge of BCP and especially the deeper CoinTree classes is not very thorough. Can someone please assess whether the bugfix suggested in the linked mail would work? I have checked the latest BCP-1.4.0 release, the "CoinTreeNode* top()" method has not been changed.

Currently I am unsure whether this really is a bug in BCP, or whether I have made a mistake in my implementation. I have attached some valgrind output for reference.

Thank you and best regards,
Vincent Bates



LP: *** Starting iteration 1 ***
LP: Default prepare_for_optimization() executed.
Clp0006I 0  Obj 0 Primal inf 6.9999993 (7)
Clp0006I 7  Obj 283.7
Clp0000I Optimal - objective value 283.7
LP:   Matrix size: 55 vars x 18 cuts
LP:   Solution value: 283.7000 / 2 , 7 
LP: Default pack_feasible_solution() executed.
 TM: Default unpack_feasible_solution() executed.
TM: Solution found at 191.835 sec.
TM 197.681: Sol from proc: 1  val: 283.700000 (prev best: 284.600000)  tree size/procd: 9/8  cand list ins/size: 5/4
==24909== Invalid read of size 4
==24909==    at 0x5AD32C: CoinTreeSiblings::currentNode() const (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x5AC747: CoinSearchTreeBase::top() const (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x57C036: CoinSearchTreeManager::newSolution(double) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x40439: BCP_tm_user::change_candidate_heap(CoinSearchTreeManager&, bool) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x42CCD: BCP_tm_prob::process_message() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B8B8: BCP_single_environment::send(int, BCP_message_tag, BCP_buffer const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1AE90: BCP_lp_user::send_feasible_solution(BCP_solution const*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1640E: BCP_lp_test_feasibility(BCP_lp_prob&, BCP_lp_result const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x17FAE: BCP_lp_main_loop(BCP_lp_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1A18C: BCP_lp_prob::process_message() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B8B8: BCP_single_environment::send(int, BCP_message_tag, BCP_buffer const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x38443: BCP_tm_node_to_send::send() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==  Address 0x1020f7c60 is 0 bytes inside a block of size 16 free'd
==24909==    at 0x6AF7: free (in /usr/local/Cellar/valgrind/3.10.1/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==24909==    by 0x79EF6: CoinSearchTreeBase::pop() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x791C8: CoinSearchTreeManager::pop() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x43D8C: BCP_tm_start_one_node(BCP_tm_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x43BC3: BCP_tm_start_new_nodes(BCP_tm_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B53D: BCP_single_environment::register_process(USER_initialize*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x4470A: bcp_main(int, char**, USER_initialize*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1000014F5: main (HHCRSP.cpp:16)
==24909== 
==24909== Invalid read of size 8
==24909==    at 0x5AD32F: CoinTreeSiblings::currentNode() const (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x5AC747: CoinSearchTreeBase::top() const (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x57C036: CoinSearchTreeManager::newSolution(double) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x40439: BCP_tm_user::change_candidate_heap(CoinSearchTreeManager&, bool) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x42CCD: BCP_tm_prob::process_message() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B8B8: BCP_single_environment::send(int, BCP_message_tag, BCP_buffer const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1AE90: BCP_lp_user::send_feasible_solution(BCP_solution const*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1640E: BCP_lp_test_feasibility(BCP_lp_prob&, BCP_lp_result const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x17FAE: BCP_lp_main_loop(BCP_lp_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1A18C: BCP_lp_prob::process_message() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B8B8: BCP_single_environment::send(int, BCP_message_tag, BCP_buffer const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x38443: BCP_tm_node_to_send::send() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==  Address 0x1020f7c68 is 8 bytes inside a block of size 16 free'd
==24909==    at 0x6AF7: free (in /usr/local/Cellar/valgrind/3.10.1/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==24909==    by 0x79EF6: CoinSearchTreeBase::pop() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x791C8: CoinSearchTreeManager::pop() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x43D8C: BCP_tm_start_one_node(BCP_tm_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x43BC3: BCP_tm_start_new_nodes(BCP_tm_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B53D: BCP_single_environment::register_process(USER_initialize*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x4470A: bcp_main(int, char**, USER_initialize*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1000014F5: main (HHCRSP.cpp:16)
==24909== 
==24909== Invalid read of size 8
==24909==    at 0x5AD333: CoinTreeSiblings::currentNode() const (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x5AC747: CoinSearchTreeBase::top() const (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x57C036: CoinSearchTreeManager::newSolution(double) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x40439: BCP_tm_user::change_candidate_heap(CoinSearchTreeManager&, bool) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x42CCD: BCP_tm_prob::process_message() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B8B8: BCP_single_environment::send(int, BCP_message_tag, BCP_buffer const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1AE90: BCP_lp_user::send_feasible_solution(BCP_solution const*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1640E: BCP_lp_test_feasibility(BCP_lp_prob&, BCP_lp_result const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x17FAE: BCP_lp_main_loop(BCP_lp_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1A18C: BCP_lp_prob::process_message() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B8B8: BCP_single_environment::send(int, BCP_message_tag, BCP_buffer const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x38443: BCP_tm_node_to_send::send() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==  Address 0x1020f7cc0 is 0 bytes after a block of size 16 free'd
==24909==    at 0x6AF7: free (in /usr/local/Cellar/valgrind/3.10.1/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==24909==    by 0x7A000: CoinTreeSiblings::~CoinTreeSiblings() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x79FC4: CoinTreeSiblings::~CoinTreeSiblings() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x79EE5: CoinSearchTreeBase::pop() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x791C8: CoinSearchTreeManager::pop() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x43D8C: BCP_tm_start_one_node(BCP_tm_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x43BC3: BCP_tm_start_new_nodes(BCP_tm_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B53D: BCP_single_environment::register_process(USER_initialize*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x4470A: bcp_main(int, char**, USER_initialize*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1000014F5: main (HHCRSP.cpp:16)
==24909== 
==24909== Invalid read of size 8
==24909==    at 0x5AC76C: CoinTreeNode::getQuality() const (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x57C051: CoinSearchTreeManager::newSolution(double) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libCoinUtils.3.9.11.dylib)
==24909==    by 0x40439: BCP_tm_user::change_candidate_heap(CoinSearchTreeManager&, bool) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x42CCD: BCP_tm_prob::process_message() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B8B8: BCP_single_environment::send(int, BCP_message_tag, BCP_buffer const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1AE90: BCP_lp_user::send_feasible_solution(BCP_solution const*) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1640E: BCP_lp_test_feasibility(BCP_lp_prob&, BCP_lp_result const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x17FAE: BCP_lp_main_loop(BCP_lp_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x1A18C: BCP_lp_prob::process_message() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x5B8B8: BCP_single_environment::send(int, BCP_message_tag, BCP_buffer const&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x38443: BCP_tm_node_to_send::send() (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==    by 0x440AE: BCP_tm_start_one_node(BCP_tm_prob&) (in /Users/vincent_bates/Documents/Xcode/bcp-1.3.8/build/lib/libBcp.1.3.8.dylib)
==24909==  Address 0x3fa99999999999aa is not stack'd, malloc'd or (recently) free'd
==24909== 
==24909== Signal 11 being dropped from thread 0's queue
==24909== Signal 11 being dropped from thread 0's queue
==24909== Signal 11 being dropped from thread 0's queue
==24909== Signal 11 being dropped from thread 0's queue
==24909== Signal 11 being dropped from thread 0's queue
==24909== Signal 11 being dropped from thread 0's queue
==24909== Signal 11 being dropped from thread 0's queue

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/bcp/attachments/20150316/555a567a/attachment-0001.html>