[BCP] Bug related to CoinSearchTreeBase::top()
Ted Ralphs
tkralphs at lehigh.edu
Sat Apr 4 13:22:27 EDT 2015
I made a new release 2.10.7 of CoinUtils with the suggested fix in it and a
release 1.4.1 of Bcp incorporating the CoinUtils release. The fix seemed to
be correct and did not break any tests. However, as I am not using Bcp
regularly, it would be great if anyone else who is out there and using Bcp
could test and report.
Thanks!
Ted
On Sat, Mar 21, 2015 at 3:38 PM, Ted Ralphs <tkralphs at lehigh.edu> wrote:
> 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
>
--
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/20150404/5cc7736b/attachment-0001.html>
More information about the BCP
mailing list