[Coin-discuss] Removing Deadwood in Bcp

[Francois Margot]

Jonathan:

I have seen the numbers reported by top go up and down for the memory usage.
It is true that the down movement is usually quite small, so it might
be non significant. Nevertheless, I can run large Branch-and-Bound 
with Bcp in DFS on less than 1% of the memory. Running a Branch-and-Cut
with DFS sees the memory usage increases regularly.

Tracking down the creation and destruction of algorithmic cuts shows the
following:

LP level: Cuts are created by cut generation or unpacking. Cuts are destroyed
from BCP_lp_clean_up_node() and BCP_lp_delete_cols_and_rows().

TM level: Cuts are created by unpacking. Cuts are destroyed only
from ~BCP_tm_prob at the very end of the execution.

When deadwood is removed from the tree, it would be nice to remove the 
corresponding algorithmic cuts stored in BCP_tm_prob.

Francois


On Wed, 19 Apr 2006, Jonathan Eckstein wrote:

> Francois -- perhaps you know this already, but "top" reports the total memory 
> size of the process, including memory in the free pool.  Most programs don't 
> return freed memory to the operating system, but just keep it in their own 
> free pool.  In unix/linux, I think it is only possible to return memory to 
> the OS (via sbrk()) if it is at the end of the virtual address space.  Thus, 
> never seeing "top" return smaller memory amounts isn't necessarily a sign of 
> a memory problem.  However, if the memory reported by "top" always goes up 
> and never stabilizes, that might be a sign of a leak.
>
> -- Jonathan
>
>
> Francois Margot wrote:
>> Laci:
>> 
>> The RemoveExploredBranches does not create problems, apparently,
>> but its efficiency seems quite limited. I have never seen the
>> memory usage going down (as reported by top) even when running
>> large BC with depth first. Are the generated cuts corresponding
>> to deadwood removed from "cuts" in BCP_tm_prob? I can not see where this
>> is done. It should not be that hard to do, since it is possible
>> to store the index of the node where a cut was generated and remove the cut
>> when its "generating node" is removed.
>> 
>> Francois
>> 
>>> I have added code that removes the "deadwood" from the search tree, i.e.,
>>> immediately removes subtrees that are completely explored. I have done 
>>> some
>>> quick testing and it seems to work. However, by default it is turned off, 
>>> just
>>> to make sure that noone's code breaks. I wonder if people could give it a 
>>> try
>>> and let me know whether it works fine or not. I am interested in both 
>>> serial
>>> and parallel settings. To enable the feature add
>>>     BCP_RemoveExploredBranches 1
>>> to your parameter file.
>>> 
>>> --Laci
>> 
>> _______________________________________________
>> Coin-discuss mailing list
>> Coin-discuss at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/coin-discuss
>
>
>