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

Ted Ralphs tkralphs at lehigh.edu
Sat Mar 21 15:38:37 EDT 2015 

I will try to take a look at this, but just so you know, BCP is not very
carefully maintained anymore. Depending on what you're doing, you might
want to try DIP (http://projects.coin-or.org/Dip/), which is more
user-friendly for many use cases, but does not have quite the power or BCP
yet. If you're not sure whether DIP is a good choice, feel free to e-mail
me off-line about what you're doing and I can try to advise you.

Cheers,

Ted

On Mon, Mar 16, 2015 at 12:54 PM, Vincent Bates <bates at in.tum.de> wrote:

> 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
>
>
> _______________________________________________
> BCP mailing list
> BCP at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/bcp
>
>


-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/bcp/attachments/20150321/b444f8e3/attachment-0001.html>

More information about the BCP mailing list